java - notacion - grafo mixto

Implementación de árbol(gráfico acíclico dirigido)

Question

Requiero una implementación de gráfico acíclico á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 envoltorio alrededor de la clave y un posible valor (no es necesario que los nodos tengan valores establecidos).
• Necesito enlaces tanto para el padre como para los hijos.

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

No me importa escribirlo yo mismo (y ciertamente no les estoy pidiendo que lo hagan). Simplemente no quiero volver a inventar la rueda.

Answer 1

Diría que es mejor implementar su propia implementación (además, ya tiene la interfaz bien pensada). ¿Cuáles son las operaciones que planea realizar en este árbol de todos modos? Probablemente quiera diseñar su API alrededor de las cosas que quiere ... acceso directo a nodos individuales por clave / valor? tipos de cruces? agregar / eliminar operaciones?

Answer 2

Si está buscando capacidades gráficas adicionales, la clase Digraph de JDigraph debe cumplir con la ley.

Answer 3

También está http://www.jgrapht.org , que tiene software licenciado bajo LGPL. Sin embargo, tengo que advertirte que implementar tu propio juego está lleno de peligros. Si planeas utilizar la recursividad en tu estructura (que es un gráfico), tendrás que asegurarte de que sea acíclica, o te encontrarás con problemas de bucle infinito. Es mejor usar un código de terceros donde ya hayan tratado los problemas.

Answer 4

No parece haber nada de eso. Hice una pregunta similar la semana pasada y terminé implementando mi propio árbol. Mi implementación fue muy similar a lo que está 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;
    }
}

Deberá agregar un enlace a los padres.