Java 中是否存在有向无环图 (DAG) 数据类型，我应该使用它吗?

2022-01-17 00:00:00 set hashtable tree collections java

我正在用 Java 对电源子系统进行建模.一个简单的 SQLite 数据库包含一组 Line Replaceable Units (LRU) 和它们之间的连接.我正在编写一个 Power Model API 来简化对数据存储的查询，使用 DDD 模式和存储库.

I am modeling a power subsystem in Java. A simple SQLite database contains a set of Line Replaceable Units (LRUs) and the connections between them. I am writing a Power Model API to simplify queries of the data store, using DDD patterns and repositories.

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

I am seeking an appropriate Java collection to model the query results. There are some special cases in a LRU connection stream that have to be modeled:

  1. 最初，有一个配电单元 (PDU) 具有多个端口 (<=16)，可为下游 LRU 供电.
  2. 电源流中的典型连接涉及产生电源的单个源 LRU 和消耗电源的单个 Sink LRU.
  3. 但是，下游可能有一个源 LRU 连接到多个接收器 LRU.
  4. 电源流中没有循环.

上面 #3 的包含使我想到从 API 中返回查询结果作为树.但我在 java.util 中找到的唯一树是 TreeMap 键值配对红黑树，这似乎不合适(或者我想不出用它来建模功率流的适当抽象.)我也一直在考虑 LinkedHashSet，但我不相信也是合适的.我不清楚这个结构中的节点如何指向下游节点.

The inclusion of #3 above has led me to think about returning query results from the API as a tree. But the only tree I've found in java.util is a TreeMap key-value paired red-black tree, which doesn't seem appropriate (or I can't think of an appropriate abstraction for modeling power streams with it.) I've also been considering a LinkedHashSet, but I'm not convinced it is appropriate either. It's not clear to me how a node in this structure would point to downstream nodes.

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

I'm not concerned about efficiency in time or space at this point. My API just has to work by supplying power connection information to external clients (i.e., the Presentation Tier of a Java-based Power Monitoring & Control app.) There are also no restrictions on the use of open source data types/libraries.

按照一般计算机科学的说法，我真正想要的是有向无环图 (DAG).

In general computer science parlance, what I'm really seeking is a Directed-Acyclic-Graph (DAG).

是否有针对 Java 的实现?我是否正确地认为 DAG 适合我的场景?

Is there an implementation of that for Java? Am I correct that a DAG is appropriate for my scenario?

推荐答案

针对这个特殊问题.我决定使用来自 Guava 的 LinkedListMultimap.

For this particular problem. I've decided to use a LinkedListMultimap from Guava.

相关文章