Discussion :

[biozaxx]

Bonjour a tous,

je suis en train de manipuler des graph (grace aux librairies Jgraph et JgraphT) et je rencontre le probleme suivant:
une fois mes noeuds et arretes construis il faut les organiser pour ne pas avoir un tas immonde et informe a l'ecran 8)
il y a donc une methode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
positionVertexAt(x,y)

qui permet de dire ou on veut positionner les noeuds...

ma question est la suivante : quelqu'un connait il un algorithme permettant de construire dynamiquement (attribuer les positions) en fonction du nombre de noeud dans le graph ?

merci pour vos renseignements , lien ....

@+

[Alec6]

C'est un peu chaud comme question.

En générale les librairy JGraph fournissent les layouts pour cela, mais c'est très difficile de généraliser.

Si cela ne convient alors bien venue en recherche opérationnelles, car il faudrait recherche les classes du graphe et les noyaux pour effectuer un layout à la main.

En tout cas, je suis preneur

[sebus]

Tu veux un graphe déssiné de manière à ce qu'il remplisse toute la fenetre?

[biozaxx]

oui ,
en fait ce que je ne veux pas (et je ne peux pas vu que le graph est dynamique) c'est avoir a placer les noeuds manuellement en specifiant moi meme les coordonnées.
je cherche donc une implementation d'un algo qui permette d'afficher le dit graph sur une taille que j'aurai defini (ca peut etre toute la fenetre)

j'ai trouvé quelques publications sur les algo les plus utilisés :
Fruchterman-reingold
kamada kawai
Spring Layout ...

mais en fait ca depace mes competances mathematique et l'ideal serai effectivement une librairie permettant de faire ca. (quitte a utiliser autre chose que JGraph)

[sebus]

Ca m'est arrivé une fois de participe à un projet ou on dessiné des arbres que l'on pouvais modifier directement en cliquant dessus, ce qui faisait augmenter et diminuer le nombre de noeuds.

Or (d'après mes connaissances d'algo) un arbre est un type particulier de graphe(en gros c'est un graphe avec les arrêtes "inutiles" en moins)

Donc la méthode utilisé peut être reprise.Mais on calculé tous nous même, c'est à dire qu'on n'utilisait pas de package deja existant mais bon ca peut te donner une idéé.

Tu comptes combien tu as de noeuds dans ton graphe.
Tu divises ta surface utilie par le nombre de noeuds.
Tu obtiens donc un quadrillage
Chaque noeud est centré dans sa case
Tu obtiens donc ses coordonnées
Tu traces tes arrêtes en fonction de ces coordonnées.

Idée reprenable ou pas? (on connaissait pas tous les packages disponibles on n'avait donc fait une version "maison" du dessin")

[biozaxx]

bein ca pourrait etre effectivement une solution, sauf que le probleme que j'imagine tt de suite avec cette solution est que ca risque de ne pas etre tres lisible pour visualiser les cycles (car j'ai bien un graph et pas forcement un arbre) de plus comme je suis dans un graph je n'ai pas d'information sur le niveau de mon noeud donc 2 noeuds l'uin a coté de l'autre a l'affichage risque d'etre eloigné d'un point de vue parentage car je suppose que les noeuds sont dessinés de facon aleatoire ...
en tout cas merci pour ta proposition je vais qd mm tester rapidement pour voir ce que ca donne

@+

[sebus]

POur un arbre la parenté doit etre prise en compte, mais pour ca fo rajoute un truc en plus de ce que je t'es filé.

Tu utilises un graphe donc normalement la parenté on s'en fou!!!!!
Un de t'es noeud ne doit pas etre plus proche d'un ou des autres!!!c'est pas grave si une arrète "traverse l'écran"!!(suaf si elle passe sur un noeud...)

Idéé: tu tri tes noeuds en fonction du nombre de liaisons qu'ils ont.
Plus un noeud à de liaisons plus tu le dessines au milieu de ta page(en moyenne ca devrait raccourcir la longueur des arrêtes peut être)
POur savoir ou mettre un noeud tu peux te débrouiller assez facilement en faisant une disposition en escargot en partant du milieu

Ensuite si tes graphes ont des formes ou caractéristiques particulières faut essayer d'en tirer profits(sans le savoir tes graphes sont peut être des DAG ou ARBRES)

[biozaxx]

sans le savoir tes graphes sont peut être des DAG ou ARBRES

Bein justement jusqu'a present j'affichais des DAG donc l'utilisation de JTree etait suffisante, mais je commence a avoir des models ou j'ai des cycles qui se forment, donc le DAG n'est plus suffisant, d'ou la necessite de passer a des 'vrais' graph.
En tout cas je te remercie te tes conseils , je suis en train de tester tout ca

[sebus]

Jme rappel plus très précisément de mes cours d'algo mais un DAG ca peut pas comporter de cycles?(un DAG c'est pas un graphe qui peut contenir des cycles mais ou on ne peut pas revenir en arrière?)

Si tu connais les DAG c'est que t'as du faire un minimum d'algorithmie!!

Voici peut etre d'autre piste plus illustre du coup:
Recherche du coté des sous graphes complet, des cliques et des graphes bipolaire
Cela pourrait surement t'aider dans des cas ou il y a des graphes chiant à afficher clairement(genre beaucoup de cycles)

Le probleme c'est qu'on se dirige vers une étude pour afficher un graphe de facon correct, ce qui n'est peut etre pas ton but dans ton application...