Applet
GRAPH LAYOUT
 
 
PRESENTATION
 

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 .

 
EXEMPLE
 

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.

Cliquez pour relancer.
 
 
CODE SOURCE
 

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

 
TELECHARGEMENT
 

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