Implementación del árbol (grafo acíclico dirigido).

Question

Necesito una implementación de gráfico acíclico de árbol / dirigido algo como esto:

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

• No hay clasificación de ningún tipo.
• El TreeNode es solo un ajuste alrededor de la clave y un valor posible (los nodos no tienen que tener valores establecidos).
• Requiero enlaces tanto para los padres como para los hijos.

¿Hay algo en las API estándar o en Commons, etc., que haga esto por mí?

No me importa escribirlo yo mismo (y ciertamente no pidiéndole a la gente que lo haga) Simplemente no quiero reinventar la rueda.

Answer 1

No parece haber nada de eso. Le hice a una pregunta similar la semana pasada y terminé implementando mi propio árbol. Mi implementación fue muy similar a lo que estás proponiendo:

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

Tendrá que agregar un enlace a los padres.

Answer 2

También hay http://www.jgrapht.org , que tiene un software bajo la licencia LGPL. Sin embargo, debo advertirte que implementar el tuyo está lleno de peligros. Si planea usar la recursión en su estructura (que es un gráfico), tendrá que asegurarse de que sea acíclico o se encontrará con problemas de bucle infinito. Es mejor utilizar el código de terceros donde ya se han ocupado de los problemas.

Answer 3

Yo diría que es mejor implementar su propia implementación (además, ya tiene la interfaz muy bien pensada). ¿Cuáles son las operaciones que planea realizar en este árbol de todos modos? Probablemente querrá diseñar su API en función de las cosas que desea ... ¿acceso directo a nodos individuales por clave / valor? tipos de travesías? añadir / eliminar operaciones?

Answer 4

Si está buscando capacidades gráficas adicionales, JDigraph 's Digraph la clase debe ajustarse a la factura.