在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模式和存储库。

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

1. 最初，有一个配电单元


2. 电源流中的典型连接涉及电源发生的单源LRU和电源耗尽的单一Sink LRU。 / li>
   
3. 但是，下游可以有单个源LRU连接到多个宿LRU。


4. 电源流中没有循环。

包含上面的＃3让我想到从树返回API的查询结果。但是我在java.util中找到的唯一一个树是 TreeMap 键值配对的红黑树，这似乎不合适（或者我不能想到一个适当的抽象用于建模功率流。）我也一直在考虑一个< a href =http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashSet.html =nofollow> LinkedHashSet ，但我不相信它也是适当的。我不清楚这个结构中的一个节点如何指向下游节点。

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

在一般的计算机科学中，我真正寻求的是一个Direct-Acyclic-Graph（DAG）。

有没有Java的实现？
我确定DAG适合我的场景吗？

解决方案

我决定使用 Guava的LinkedListMultimap 。

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.

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. Initially, there's a Power Distribution Unit (PDU) with multiple ports (<=16) that feeds power to downstream LRUs.
2. Typical connections in a power stream involve a single source LRU where power originates and a single Sink LRU where power is drained.
3. However, downstream there could be a single source LRU connected to multiple sink LRUs.
4. There are no cycles in a power stream.

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.

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.

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

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

解决方案

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

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