¿Hay algún tipo de datos de Gráfico Acíclico Dirigido (DAG) en Java, y debería usarlo?

Question

Estoy modelando un subsistema de energía en Java. Una base de datos SQLite simple contiene un conjunto de unidades reemplazables por línea (LRU) y las conexiones entre ellas. Estoy escribiendo una API de Power Model para simplificar las consultas del almacén de datos, usando patrones y repositorios de DDD.

Buscando a una colección Java adecuada para modelar los resultados de la consulta. Hay algunos casos especiales en una corriente de conexión LRU que tienen que ser modelada:

1. Inicialmente, hay una unidad de distribución de energía (PDU) con múltiples puertos (< = 16) que alimenta de energía a aguas abajo LRU.
2. conexiones típicas en una corriente de energía implican un único LRU fuente donde se origina de potencia y un solo Sink LRU donde se drena de energía.
3. Sin embargo, en sentido descendente podría haber una única fuente LRU conectada a múltiples LRU de receptor.
4. No hay ciclos en un flujo de potencia.

La inclusión del n. ° 3 anterior me ha llevado a pensar en devolver los resultados de la consulta de la API como un árbol. Pero el único árbol que he encontrado en java.util es un árbol rojo-negro emparejado con valor-clave TreeMap, que no parece apropiado (o no puedo pensar en una abstracción apropiada para modelar flujos de energía con él). También he estado considerando un LinkedHashSet, pero no estoy seguro de que sea apropiado tampoco. No tengo claro cómo un nodo en esta estructura apuntaría a los nodos descendentes.

no estoy preocupado por la eficiencia en el tiempo o en el espacio en este punto. Mi API solo tiene que funcionar al suministrar información de conexión de alimentación a clientes externos (es decir, el Nivel de presentación de una aplicación de control & Control de energía basada en Java). Tampoco hay restricciones en el uso de tipos de datos/bibliotecas de código abierto.

En el lenguaje de la informática en general, lo que realmente estoy buscando es una Dirigida-acíclica-Graph (DAG).

¿Hay una aplicación de esa para Java? ¿Estoy en lo correcto si un DAG es apropiado para mi caso?

Answer 1

Para este problema en particular. Decidí usar un LinkedListMultimap from Guava.

Answer 2

Como se puede ver si con respecto a las cuestiones "relacionadas", ya se hicieron preguntas similares. Y no, Java does not have a general-purpose graph/tree/DAG data type (si no contamos el TreeModel de Swing).

Haga que su propio.

---

Aquí es un ejemplo (sólo lectura) Interfaz:

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

A continuación, tendría

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

(o clases en su lugar).

Answer 3

No sé si puede ayudar pero eche un vistazo a JGraphT.

Answer 4

FWIW si alguien quiere una solución estándar de solo bibliotecas, un mapa de conjuntos o un mapa de otras colecciones también podría hacer el trabajo, aunque no tan bien.