Applet GRAPH LAYOUT

Cette applet illustre une méthode qui tente d'améliorer la disposition des noeuds dans un graphe. Cette applet est fortement inspirée de l'applet de démonstration appelée GraphLayout dans Java 2 SDK de Sun Microsystems. L'idée principale de l'algorithme est de démarrer avec des coordonnées aléatoires pour les noeuds et de simuler des forces entre ces noeuds dans le but d'obtenir un équilibre qui est supposé fournir un bon arrangement du graphe. Le résultat est assez bon pour de petits graphes, mais la méthode est généralement inefficace pour de grands graphes. En bref, chaque arc du graphe crée une force d'attraction entre ses extrémités qui augmente avec sa longueur. A l'opposé, entre toute paire de noeuds existe une force de répulsion qui augmente quand la distance entre les noeuds diminue.

Si vous êtes intéressés par cette applet, regardez la page .

Pour utiliser cette applet, vous devez indiquer la taille disponible pour l'arrangement et décrire la structure du graphe.

La structure du graphe est spécifiée par une chaîne de caractères dans le paramètre graph. Elle liste simplement les arcs du graphe. Par exemple, le graphe ci-dessus sera spécifié comme suit.

1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-1,3-5,
5-7,5-9,0-1,0-2,0-3,0-4,0-5,0-6,0-7,0-8

Faites attention de bien numéroter les noeuds à partir de 0 et d'éviter les sauts dans la numérotation. Ensuite, l'applet peut tenter de trouver un bon arrangement du graphe.

Voici le code source de l'applet: GraphLayout.java.

Cliquez ici pour télécharger l'applet et son code source.