Tree (directed acyclic graph) implementation

Question

I require a tree / directed acyclic graph implementation something like this:

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

• There is no sorting of any kind.
• The TreeNode is just a wrapper around the key and a possible value (nodes don't have to have values set).
• I require links to both the parent and the children.

Is there anything out there in the standard APIs or Commons etc that will do this for me?

I don't mind writing it myself (and I'm certainly not asking you folks to) I just don't want to re-invent the wheel.

Answer 1

There's also http://www.jgrapht.org, which has software licensed under the LGPL. I have to warn you though, implementing your own is fraught with danger. If you plan on using recursion on your structure (which is a graph), you'll have to ensure that it's acyclic, or you'll run into infinite loop problems. Better to use third party code where they've already dealt with the issues.

Answer 2

There doesn't seem to be anything of the kind. I asked a similar question last week and ended up implementing my own tree. My implementation was very similar to what you're proposing:

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

You will have to add a link back to the parent(s).

Answer 3

I'd say it's better to roll out your own implementation (besides, you've already got the interface nicely thought out). What are the operations you are planning to perform on this tree anyway? You'd probably want to design your API around the things you want... direct access to individual nodes by key/value? types of traversals? add/remove operations?