TD 7 - Planar parameterization and spectral drawing
Introduction:
Dans ce TD nous allons implanter et tester un certain nombre de
méthodes pour dessiner des graphes (planaires) en 2D. Pour
faciliter votre travail, un certain nombres de primitives pour la
manipulation et visualisation de graphes ont été fournies à la
librairie Jcg.
Avant de commencer
La
documentation de la bibliothèque Jcg est consultable ici
Comment représenter un graphe avec Jcg: vous trouverez
quelques suggestions ici.
Librairies et fichiers à installer/télécharger pour le TD
d'aujourd'hui:
|
- Vous avez ici
quelques examples de graphes planaires.
- Téléchargez
les classes suivantes (à compléter et tester): src.zip
- Téléchargez les librairies necessaires: lib.zip
|
Pour tester les méthodes de dessin, vous pourrez utiliser la classe
TestSpectralDrawing et TestTutteDrawing.
Par exemple, si le graphe CubeGraph_0-1-2-3.txt en entrée est stoqué dans
un repertoire /data,
vous pourrez utiliser les commandes:
- TestSpectralDrawing data/CubeGraph.txt 3
- TestTutteDrawing data/CubeGraph_0-1-2-3.txt 0 1 2 3.
Remarque: dans le cas de la méthode de Tutte, il faut
spécifier au programme:
- la liste des indices de la face externe (exemple: "0 12 15", si
la face externe est triangulaire et définie par [0, 12, 15])
2. Spectral graph drawing 2D:
on utilise la matrice laplacienne pour dessiner dans le plan