Java 中是否有有向无环图 (DAG) 数据类型，我应该使用它吗? [英] Is there a Directed Acyclic Graph (DAG) data type in Java, and should I use it?

问题描述

我正在用 Java 对电源子系统进行建模.一个简单的 SQLite 数据库包含一组线路可更换单元 (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. 最初，有一个带有多个端口 (<=16) 的配电单元 (PDU)，可为下游 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.

这篇关于Java 中是否有有向无环图 (DAG) 数据类型，我应该使用它吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！