La structure de graphe est très fréquemment utilisée en informatique. Ses applications vont des réseaux (routiers, informatiques, etc.) à la représentation des relations entres concepts de connaissance. Les graphes peuvent être très larges et leur visualisation pose un réel problème. Il faut être capable de distribuer les noeuds dans le plan de façon à ce que les arêtes ne s'enchevêtrent pas trop. Un graphe planaire peut se représenter dans le plan sans que deux arêtes ne se croisent, mais les graphes planaires sont rares.

example-graph.png

De plus, le problème de la visualisation est compliqué par le fait que d'une part les noeuds ne sont pas des points mais sont nommés et que leur nom occupe un certain espace, d'autre part que les arêtes sont étiquetées et que les étiquettes doivent rester lisibles.

La première étape consistera à faire une étude bibliographique et à vous familiariser avec les algorithmes qui existent : Sugiyama, Kamada-Kawai, AGLO, etc.

Pour satisfaire aux objectifs, le programme que vous réaliserez devra :

  • Permettre de lire des graphes dans un fichier au format DOT (documenté ici : http://www.graphviz.org/doc/info/lang.html,
  • Proposer une disposition des noeuds dans le plan et tracer les arêtes entre les noeuds,
  • Permettre d'ajuster manuellement la disposition si l'utilisateur le souhaite.