Java中是否有有向无环图（DAG）数据类型，我应该使用它吗？

Question

我正在用Java建模电源子系统。一个简单的SQLite数据库包含一组可替换线路元件（LRUs）及其之间的连接。我正在编写一个Power Model API来简化数据存储的查询，使用DDD模式和存储库。

我正在寻找适当的Java集合来建模查询结果。在LRU连接流中有一些特殊情况需要建模：

1. 最初有一个功率分配单元（PDU），具有多个端口（<=16），向下游LRU提供电力。
2. 电源流中的典型连接涉及单个源LRU，其中电力起源，以及单个汇LRU，其中电力被排出。
3. 然而，在下游可能有一个单一源LRU连接到多个汇LRU。
4. 电源流中没有循环。

包括上面所述的第3点让我开始考虑将API返回的查询结果作为一棵树。但是我在java.util中找到的唯一的树是TreeMap键值对红黑树，这似乎不太合适（或者我无法想到一个适当的抽象来模拟电源流）。我也考虑过LinkedHashSet，但我并不确信它是否合适。对我来说，这个结构中的节点如何指向下游节点还不清楚。

目前我不关心时间或空间效率。我的API只需通过向外部客户端（即基于Java的电力监控和控制应用程序的表示层）提供电力连接信息即可工作。对于使用开源数据类型/库也没有限制。

通常在计算机科学术语中，我真正寻求的是有向无环图（DAG）。

Java中是否有其实现？我是否正确认为DAG适用于我的情况？

- retrodrone

Answer 1

我不知道是否有帮助，但看一下JGraphT。

- patapizza

Answer 2

从“相关”的问题中可以看出，已经有类似的问题被问过了。如果不算Swing的TreeModel，Java没有通用的图/树/DAG数据类型。

自己创建一个。

---

这里是一个只读接口示例：

interface Node<N extends Node<N,E>, E extends Edge<N,E>> {
    public Set<E> outgoingEdges();
    public Set<E> ingoingEdges();
}

interface Edge<N extends Node<N,E>, E extends Edge<N,E>> {
    public E source();
    public E sink();
}

你将会拥有

interface LRU implements Node<LRU, Line> { ... }
interface Line implements Edge<LRU, Line> { ... }

（或者使用类代替）。

- Paŭlo Ebermann

---

好的，但是这种语言中是否有其他符合我的需求的数据类型呢？我当然可以自己编写DAG，但我更愿意使用经过大型社区使用/测试的成熟实现。在这个问题上，我时间紧迫，也不想重新发明轮子，强迫我的客户在长期内维护更多的代码。 - retrodrone

我不知道有什么，我会使用自己的...但让我们看看其他人可以在这里推荐什么。 - Paŭlo Ebermann

记住 Swing 的 TreeModel 是一个连接的 DAG。有些 DAG 是不连通的，因此无法使用 TreeModel 表示。 - Ogen

Answer 3

针对这个特定问题，我决定使用Guava的LinkedListMultimap。

- retrodrone

---

每个节点一个地图，还是整个图只有一个地图？ - Paŭlo Ebermann

Answer 4

如果有人想要一个仅使用标准库的解决方案，那么一张集合图或其他集合的图也可能能够胜任，尽管效果不如前者。

- trutheality