Java Bibliothèque ou algorithme pour calculer les coordonnées des nœuds d'arbre/dessin

Question

Je cherche une bibliothèque qui me donnerait les coordonnées exactes de chaque nœud dans un arbre (n'importe quel arbre, pas seulement des arbres binaires).

Disons que je l'arbre définir la notation suivante

(() (() (()()())) 

Et une bibliothèque me donne les coordonnées comme ceci:

[500 0]([200 50]() [600 50]([500 100]() [750 100]([600 150]() [700 150]() [800 150]())) 

ou toute autre notation qui représente un arbre unique.

Ce type de bibliothèque permettrait un dessin d'arbres économe en espace et résoudrait également le problème du chevauchement des nœuds et des liaisons. Par exemple, si une arborescence est une liste en fait, j'aimerais que cette bibliothèque prenne cela en compte et arrange les nœuds dans une seule colonne ou rangée, pour économiser de l'espace.

Si rien de semblable n'existe, un algorithme serait également utile, à condition qu'il puisse être mis en œuvre relativement facilement.

Answer 1

Je pense que le modèle Nested Set peut vous aider.

L'algorithme est assez simple et très efficace pour les lectures, bien que les mises à jour de l'arborescence soient un peu plus coûteuses, car les limites des nœuds doivent être mises à jour en cascade. Here is the algorithm implemented in SQL.