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

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

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 и т.д., которые сделают это для меня?

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

Ответ 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;
    }
}

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

Ответ 2

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

Ответ 3

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

Ответ 4

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