Реализация дерева (направленного ациклического графа)

Question

Мне требуется реализация дерева / ориентированного ациклического графа примерно так:

public class TreeNode<K, V> {
    private K key; // 'key' for this node, always present
    private V value; // 'value' for this node, doesn't have to be set

    private TreeNode<K, V> parent;
    private Set<TreeNode<K, V>> children; 
}

• Нет сортировки.
• TreeNode - это просто обертка вокруг ключа и возможного значения (узлы не должны иметь установленные значения).
• Мне нужны ссылки как на родителей, так и на детей.

Есть ли что-нибудь в стандартных API, Commons и т. Д., Которые сделают это для меня?

Я не против написать это сам (и я конечно не прошу вас, ребята) Я просто не хочу заново изобретать колесо.

Answer 1

Кажется, ничего подобного нет. Я задал аналогичный вопрос на прошлой неделе и в итоге реализовал собственное дерево. Моя реализация была очень похожа на то, что вы предлагаете:

public class TreeNode<T>
{
    private LinkedList<TreeNode<T>> children = new LinkedList<TreeNode<T>>();
    public T value { get; set; }

    public TreeNode(T value)
    {
        this.value = value;
    }
    public LinkedList<TreeNode<T>> GetChildren()
    {
        return children;
    }
}

Вам нужно будет добавить ссылку на родителя (ей).

Answer 2

Существует также http://www.jgrapht.org,, программное обеспечение которого лицензировано по лицензии LGPL. Я должен предупредить вас, однако, реализация вашего собственного таит в себе опасность. Если вы планируете использовать рекурсию в своей структуре (которая представляет собой график), вам нужно убедиться, что она является ациклической, иначе вы столкнетесь с проблемами бесконечного цикла. Лучше использовать сторонний код там, где они уже справились с проблемами.

Answer 3

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

Answer 4

Если вы ищете дополнительные графические возможности, класс JDigraph Digraph должен соответствовать всем требованиям.