Существует ли тип данных ориентированного ациклического графа (DAG) в Java и должен ли я его использовать?

Question

Я моделирую подсистему питания в Java. Простая база данных SQLite содержит набор линейных заменяемых блоков (LRU) и связи между ними. Я пишу API Power Model для упрощения запросов к хранилищу данных, используя шаблоны DDD и репозитории.

Я ищу подходящую коллекцию Java для моделирования результатов запроса. В потоке соединений LRU есть несколько особых случаев, которые необходимо смоделировать:

1. Первоначально, есть блок распределения питания (PDU) с несколькими портами (<= 16), который подает питание на нижестоящие LRU. </li>
2. Типичные соединения в потоке энергии включают в себя один LRU источника, откуда происходит питание, и один LRU приемника, где питание истощается.
3. Однако в нисходящем направлении может быть один источник LRU, подключенный к нескольким приемникам LRU.
4. В потоке мощности нет циклов.

Включение # 3 выше заставило меня задуматься о возврате результатов запроса из API в виде дерева. Но единственное дерево, которое я нашел в java.util, - это парное красно-черное дерево TreeMap со значением ключа, которое кажется неподходящим (или я не могу придумать подходящую абстракцию для мощи моделирования). потоки с ним.) Я также рассматривал LinkedHashSet , но я не уверен, что это также уместно. Мне не ясно, как узел в этой структуре будет указывать на нисходящие узлы.

В данный момент меня не интересует эффективность во времени или пространстве. Мой API просто должен работать, предоставляя информацию о подключении питания внешним клиентам (т. Е. Уровню представления приложения на основе мониторинга и управления питанием на основе Java). Также нет никаких ограничений на использование типов / библиотек данных с открытым исходным кодом.

В общем, на языке информатики, я действительно ищу направленный ациклический граф (DAG).

Есть ли реализация этого для Java? Я правильно понимаю, что DAG подходит для моего сценария?

Answer 1

Я не знаю, может ли это помочь, но взгляните на JGraphT .

Answer 2

Как вы можете видеть, если в отношении "связанных" вопросов подобные вопросы уже задавались.И нет, У Java нет общего типа данных graph / tree / DAG (если мы не считаем Swing's TreeModel).

Создайте свой собственный.

---

Вот пример (только для чтения) интерфейса:

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

В таком случае вы получите

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

(или классы вместо этого).

Answer 3

Для этой конкретной проблемы. Я решил использовать LinkedListMultimap из Гуавы .

Answer 4

FWIW, если кто-то хочет решение только со стандартными библиотеками, карта наборов или карта других коллекций также могут выполнить эту работу, хотя и не так хорошо.