Discussion :

[haraelendil]

Bonjour bonjour.

Voila, je suis récemment face à un soucis, j'aimerai faire un petit moteur de dessin de graphe, mais avec quelques spécificités, et je me demandais si il existait des algos ou des principes qui pourraient m'aider.

En fait j'ai un graphe à dessiner avec des contraintes dans une dimension pour les nœuds (certains sont fixés, d'autre doivent être après leurs nœuds en amont et après leurs nœuds en aval).

Donc j'ai fait deux trois tests assez rapide, en plaçant au mieux horizontalement les nœud et en ajustant leur position en verticale pour éviter les chevauchements, mais bien évidemment, ça tourne vite à la cata dès qu'il y a plus de cinq nœud, car je ne prend pas en compte les croisement arête/nœud et arête/arête.

Donc avant de ma lancer dans des trucs très tordus, je voulais savoir si il y a des aglos "classiques" qui pourrai m'aider, ou qui font des trucs un peu dans ce gout la.

Merci

[bretus]

Bonjour,

Je n'ai jamais testé ce genre de méthode (en principe, mes sommets ont une position), mais tu peux peut-être chercher là dedans s'il y a quelque chose qui t'inspire :

Positionnement itératif basé sur des forces (les arcs sont des ressorts) :
http://fr.wikipedia.org/wiki/Force-based_layout

Dans les logiciels existants et OpenSource :
http://en.wikipedia.org/wiki/Graph_drawing

Ou encore dans la rubrique de boost::graph (grosse bibliothèque de graphe c++) sur les graphes planaires :
http://www.boost.org/doc/libs/1_36_0...ar_graphs.html

Sinon, mes mots clés suivant on l'air de renvoyer vers des pages interessante : graph layout, graph drawing, graph vertex placement, etc.