Is there a Directed Acyclic Graph (DAG) data type in Java, and should I use it?

Question

I am modeling a strong subsystem in Java. A simple SQLite database contains a set of replaceable rows (LRUs) and the connections between them. I am writing a Power Model API to simplify data warehouse queries using DDD templates and repositories.

I am looking for a suitable Java collection for modeling query results. There are some special cases in the LRU connection stream that need to be modeled:

• Initially, there is a Power Distribution Unit (PDU) with multiple ports (<= 16) that supplies power to the downstream LRUs.
• Typical connections in a power stream include one LRU source where power is supplied, and one Sink LRU where power is low.
• However, in the downstream, there may be one LRU source connected to multiple LRUs.
• There are no cycles in the power stream.

Inclusion # 3 above led me to think of returning the results of an API request as a tree. But the only tree I found in java.util is the TreeMap key value, a paired red-black tree that doesn't seem (or I can't come up with an appropriate abstraction to model power flows with it.) I also consider LinkedHashSet , but I not sure if this is appropriate. I don’t understand how the node in this structure will point to the nodes downstream.

At the moment, I'm not interested in efficiency in time or space. My API just needs to work by delivering network connectivity information to external clients (i.e. the presentation layer of a Java-based monitoring and power management application). There are also no restrictions on the use of open source types / libraries.

In the common language of computer science, what I'm really looking for is Directed-Acyclic-Graph (DAG).

Is there an implementation for Java? Am I assuming DAG is suitable for my scenario?

Answer 1

For this specific task. I decided to use LinkedListMultimap from Guava .

Answer 2

I don't know if this might help, but take a look at JGraphT .

Answer 3

As you can see if the “related” questions are related, similar questions have already been asked. And no, Java does not have a common graph / tree / DAG data type (unless we take Swing TreeModel into account).

Make your own.

---

Here is an example (read-only):

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(); } 

Then you will have

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

(or classes instead).

Answer 4

FWIW, if someone wants a solution only for standard libraries, a map of sets or a map of other collections can do the job, although not so.