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

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

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

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

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

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

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

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

Источник

4 ответа

Решение

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

Источник

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

Источник

Как вы можете видеть, если в отношении "связанных" вопросов подобные вопросы уже задавались. И нет, в Java нет общего типа данных graph/tree/DAG (если мы не считаем Swing 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> { ... }

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

Источник

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

Источник
Другие вопросы по тегам