Implémentation d'arbre (graphe acyclique dirigé)

Question

J'ai besoin d'une implémentation de graphe acyclique dirigé par arbre, quelque chose comme ceci:

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

• Il n'y a pas de tri d'aucune sorte.
• Le TreeNode est simplement un wrapper autour de la clé et une valeur possible (il n'est pas nécessaire que des valeurs soient définies pour les nœuds).
• J'ai besoin de liens vers le parent et les enfants.

Existe-t-il quelque chose dans les API standard ou dans les Commons, etc., qui le fera pour moi?

Cela ne me dérange pas de l'écrire moi-même (et je certainement pas de vous le demander), je ne veux tout simplement pas réinventer la roue.

Answer 1

Il ne semble y avoir rien de tel. J'ai posé une question similaire la semaine dernière et j'ai fini par implémenter mon propre arbre. Mon implémentation était très similaire à ce que vous proposez:

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

Vous devrez ajouter un lien au (x) parent (s).

Answer 2

Il existe également http://www.jgrapht.org , un logiciel sous licence LGPL. Je dois toutefois vous avertir que la mise en œuvre de la vôtre est lourde de dangers. Si vous envisagez d'utiliser la récursivité sur votre structure (qui est un graphique), vous devrez vous assurer qu'elle est acyclique, sinon vous rencontrerez des problèmes de boucle infinie. Mieux vaut utiliser du code tiers lorsque les problèmes ont déjà été résolus.

Answer 3

Je dirais qu'il vaut mieux déployer votre propre implémentation (en plus, vous avez déjà l'interface bien pensée). Quelles sont les opérations que vous envisagez d'effectuer sur cet arbre de toute façon? Vous voudrez probablement concevoir votre API autour de ce que vous voulez ... un accès direct à des nœuds individuels par clé / valeur? types de traversées? ajouter / supprimer des opérations?

Answer 4

Si vous recherchez des fonctionnalités graphiques supplémentaires, JDigraph 's La classe Digraph devrait convenir.