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

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's Диграф класс должен соответствовать всем требованиям.