Algorithme d'espacement des graphes

Question

Je cherche un algorithme qui serait utile pour déterminer les coordonnées x y pour un nombre d'objets à afficher à l'écran. Chaque objet peut être lié à un autre objet et il peut y avoir n'importe quel nombre de relations et il peut y avoir un nombre quelconque de ces objets.

Il n'y a aucune restriction sur la taille globale de la zone sur laquelle afficher ces objets. J'écris ceci en php et je chercherais à stocker les coordonnées dans un tableau.

Answer 1

Une façon de le faire est d'utiliser un modèle de pseudo-physique. Vos objets ont une force répulsive et une force attractive s'ils sont attachés. Vous déplacez les objets en fonction de la somme des forces qui leur sont appliquées: à chaque étape, calculez la somme des forces appliquées à un objet et déplacez-le dans la direction de la force.

Dans le code pseudo, une itération serait:

for each object o1 
    force[o1] = 0 
    for each object o2 
     if o1 and o2 are linked 
     force[o1] += attraction_force(o1, o2) 
     else 
     force[o1] += repulsion_force(o1, o2) 

for each object o1 
    move(o1, force[o1]) 

Et arrêter les itérations lorsque les objets ont atteint un état stable.

Vous aurez probablement besoin d'expérimenter différentes lois de force. En particulier, vous voulez que les objets adjacents atteignent rapidement un équilibre. J'expérimenter avec une force d'intensité linéaire à la distance (comme un ressort) ou quadratique (gravition/attraction électrique)

Aussi, vous aurez probablement besoin de déplacer les objets au hasard pour éviter que des parties du graphique de rester stucked. La quantité de mouvement aléatoire devrait être grande pour les premières itérations et diminuer avec le temps.

Answer 2

Les noms traditionnels pour ce que vous voulez faire sont une présentation graphique et graph drawing. Ce n'est généralement pas un problème facile. Les diagrammes vont seulement bien paraître s'ils sont planar ou presque plans.