Árvore (dirigido gráfico acíclico) aplicação

Question

Eu exijo uma árvore / dirigido implementação gráfico acíclico algo como isto:

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

• Não há nenhuma classificação de qualquer tipo.
• O TreeNode é apenas um invólucro em torno da chave e um valor possível (nós não tem que ter valores set).
• I exigem links para ambos os pais e as crianças.

Existe alguma coisa lá fora, nas APIs padrão ou Commons etc que vai fazer isso por mim?

Eu não me importo de escrevê-lo eu mesmo (e eu sou certamente não lhe pedindo pessoas para) Eu só não quero re-inventar a roda.

Answer 1

Há não parece ser qualquer coisa do tipo. Perguntei uma pergunta semelhante na semana passada e acabou implementar minha própria árvore. Minha implementação foi muito semelhante ao que você está propondo:

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

Você terá que adicionar um link de volta para o pai (s).

Answer 2

Há também http://www.jgrapht.org é, que tem software licenciado sob a LGPL. Eu tenho que avisá-lo embora, implementando seu próprio país é repleto de perigo. Se você planeja usar a recursividade em sua estrutura (que é um gráfico), você terá que garantir que ele é acíclico, ou você vai correr em problemas de loop infinito. Melhor usar código de terceiros onde já lidou com as questões.

Answer 3

Eu diria que é melhor para a implantação de sua própria implementação (além disso, você já tem a interface bem pensado). Quais são as operações que estão planejando realizar neste mesmo assim árvore? Você provavelmente gostaria de projetar seu API em torno das coisas que você quer ... acesso directo à nós individuais de chave / valor? tipos de percursos? adicionar / operações remove?

Answer 4

Se você está à procura de capacidades de gráficos adicionais, JDigraph 's Digraphs classe deve caber a conta.