Cherche algo pour le layout graphique

**Alec6** · 18/02/2008, 16h23

Hello

je voudrai représenter dans un premier temps une arborescence sous forme d'arbre genre généalogique. Je cherche, je cherche mais je trouve pas.

Une piste SVP

**pseudocode** · 21/02/2008, 11h42

Bonjour,

Ta structure d'arbre de départ à des propriétés particulières (binaire, équilibrée, ...) ?

Invité · 21/02/2008, 12h11

Bonjour,
si tu veux un algo tout fait, il faut déjà savoir sous quel langage tu travailles pour savoir si tu peux récupérer l'algo dans une librairie par exemple (Boost est très bien en matière de graphe, d'arbre).
Ensuite que veux-tu faire de ton arborescence? l'optimiser, trouver un parcours (utiliser l'algo de Kruskal, Dijkstra, si mes souvenirs sont bons).
Quelles sont tes données initiales :

as-tu un ensemble de noeuds et d'arcs et ensuite à toi de créé ton arbre?

as-tu un arbre initial que tu dois modifier, coder?

Je veux bien aider mais il faudrait un peu plus d'infos
Bonne journée

**Alec6** · 21/02/2008, 16h27

En fait c'est tout simple (entre guillemet).

J'ai une structure arborescente (en java le DefaultMutableTreeNode) d'objet graphique (des labels ou des boutons), que je connais. L'arbre n'a pas de propriété particulière.

Je veux pas faire de calcul dessus est c'est pas non plus un graphe.
Je veux juste faire un affichage graphique des éléments (labels) de l'arbre, sous une forme similaire à un arbre généalogique. Donc la racine en haut et les enfants en bas. (on pourrai imaginer d'autres direction avec la racine en bas, ou à droite...)

Je connais pour chaque noeud (label), la taille de l'objet graphique. Ce qui me manque c'est le calcul de la position de chacun de ces éléments sur le panel d'affichage. Donc les coordonnées x,y pour chaque noeud.

Je pense que c'est pas tout jeune comme problème et pourtant je ne trouve pas une référence sur laquelle m'appuyer.

Merci pour votre aide

**pseudocode** · 21/02/2008, 17h28

Je commencerais par calculer la taille nécessaire pour afficher un noeud (en tenant compte de ses descendants). Ca peut se faire recursivement ou itérativement:

Taille( N ) = Max( N.labelsize , Somme[ Taille( fils de N ) ] )

Une fois qu'on connait la taille necessaire pour chaque noeud, il suffit d'afficher le label au centre de sa zone.

en haut: l'arbre de départ. En rouge la valeur de Taille(N)
en bas: les zones reservées pour l'affichage

**Alec6** · 21/02/2008, 19h19

C'est une première solution, j'ai pensé à un algo comme cela.

Mais dans cette présentation on a:

Code :

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

1
2
3
4
5
6
7
8
 
                         A
 
    B                   G                     H
 
C  D  E  F           m                   I  J  K  L
 
                 n o p q r s t u v

Tout est très espacé, ca ne permet pas d'avoir une visualisation bien concise pour des arbres un peu grand (en plus dans mon cas les composants graphiques on un taille inconnu).

J'aimerai réussir à avoir:

Code :

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

1
2
3
4
5
6
7
8
 
                    A
 
    B             G         H
 
C  D  E  F     m       I  J  K  L
 
          n o p q r s t u v

Pour le noeud G (qui est déployé ici) on voit que l'espace nécessaire pour G selon ton algo pseudocode chevauche les espaces de B et H, mais on a pas pour autant des labels (noeud) qui se chevauchent graphiquement. C'est cet algo que je voudrais réussir à implémenter. C'est déjà plus tordu.

**Alec6** · 21/02/2008, 19h34

Zut il m'a pas garder les espaces dans mon post; j'espère être compréhensible quand même

http://www.jvisio.com/tensite/en/tec...reeLayout.html

je voudrais un layout comme celui en haut à gauche. C'est dingue j'arrive pas à trouver un doc là dessus, pourtant sur les graphes il y a une envolée lyrique incompréhensible.

**pseudocode** · 21/02/2008, 19h46

Ah, effectivement ca va etre plus dur.

Je commencerais par chercher l'étage le plus large, c'est à dire la profondeur "P" pour laquelle la somme des largeurs des labels est maximale. Ensuite il faut calculer la position de leurs noeuds parents/enfants. Le problème c'est que les "liens" entre les labels risquent d'être cachés.

Peut-etre par programmation dynamique... je vais y réfléchir

**Alec6** · 21/02/2008, 19h59

Je sais pas ce qu'est la programmation dynamique; surtout ce qui est difficile je pense c'est de faire un algo léger.

Je pensais à fonctionner par étape:
1/ Je calcule la position de chaque noeuds sans me soucier des chevauchements, et à chaque noeud je conserve la largeur prise par les noeuds enfants (x max et x min), appelons ca un range

2/ Je parcours l'arbre et à chaque noeud j'opère un décalage si les enfants de ce noeud (le range donc) chevauche ce du noeud frère précédent.

Dans le genre en tout cas.

**pseudocode** · 21/02/2008, 20h00

Envoyé par Alec6

Je sais pas ce qu'est la programmation dynamique; surtout ce qui est difficile je pense c'est de faire un algo léger.

Je pensais à fonctionner par étape:
1/ Je calcule la position de chaque noeuds sans me soucier des chevauchements, et à chaque noeud je conserve la largeur prise par les noeuds enfants (x max et x min), appelons ca un range

2/ Je parcours l'arbre et à chaque noeud j'opère un décalage si les enfants de ce noeud (le range donc) chevauche ce du noeud frère précédent.

Dans le genre en tout cas.

C'est exactement cela de la programmation dynamique.

**millie** · 21/02/2008, 22h43

Il y a une méthode que j'avais utilisé dans une appli web pour visualiser des graphes.

J'utilisais l'outil GraphViz et son format DOT. Je générais un fichier dot (qui correspond grosso modo à l'ensemble des arêtes entre les sommets), je passais GraphViz dessus et j'obtenais une image (png etc...) que je mettais sur le navigateur du client.

http://www.graphviz.org/

**souviron34** · 22/02/2008, 01h03

Envoyé par Alec6

Zut il m'a pas garder les espaces dans mon post; j'espère être compréhensible quand même

http://www.jvisio.com/tensite/en/tec...reeLayout.html

je voudrais un layout comme celui en haut à gauche. C'est dingue j'arrive pas à trouver un doc là dessus, pourtant sur les graphes il y a une envolée lyrique incompréhensible.

j'ai une tite idee que je creuserais ce soir ou ce we..

Mais par contre, je pense que les dessins pointes par ton lien sont "ajustes" soit a la main, soit avec des "espaces" elastiques, car les epaces ne sont pas coherents... Sans doute un ajustement "apres coup"...

**millie** · 22/02/2008, 09h58

Envoyé par pseudocode

http://www.developpez.net/forums/sho...4&postcount=25

Oui, je l'ai dit au moins 10 fois sur developpez

**marchand_de_sable** · 22/02/2008, 10h51

Salut.

J'avais fait un programme Java qui faisait exactement ce que tu cherches.
Avec un peu de chance, j'arriverais à remettre la main dessus.
Mais :
1) je crois me souvenir qu'il n'était pas parfait;
2) c'est un de mes 1er développement en Java, et je crains fort que le code soit affreux et non réutilisable

Envoyé par pseudocode

Je commencerais par chercher l'étage le plus large, c'est à dire la profondeur "P" pour laquelle la somme des largeurs des labels est maximale. Ensuite il faut calculer la position de leurs noeuds parents/enfants.

Je commençais comme ça.

Envoyé par pseudocode

Peut-etre par programmation dynamique... je vais y réfléchir

Et je continuais comme ça

**Alec6** · 22/02/2008, 12h50

Je suis en train d'envisager une solution en presque une passe récursive.

en tout cas je crois qu'il faut que dans un premier temps je positionne les enfants relativement aux parents. En faite je cherche la position relative des enfants par rapport aux parents.

En dernier je calcul la position absolue pour mon média.

**marchand_de_sable** · 22/02/2008, 13h15

Les parents, comment les places-tu dans un 1er temps ?
(il faut bien qu'ils aient une position pour calculer celles des enfants)

**Alec6** · 22/02/2008, 13h56

Je prend un noeud

1/Je calcule le range de ses fils (largeur occupée par les fils espaces compris)
(ca me fait une première itération sur les fils)

2/Pour chaque fils:
- 2.1/je calcule la position X, c'est la somme des widths des composants graphiques qui le précède avec les espaces - range/2 pour une décalage sur le repère. On parle d'un repère locale on père qui se trouve en (0,0). Je fais ici une deuxième itération (snif c'est moche).
- 2.2/j'en appel à la récursivité (et à un miracle) et pour que le fils courant calcul à son tour la position de ses fils. Donc je rappel la fonction. Donc je parcours tout l'arbre en profondeur et de gauche à droite si on peut dire.

3/Au retour des appels récursif je dispose pour le noeud courant du range de ses enfants mais également du range des déscendants. Je dois donc pouvoir faire un calcul sur les décalages à opérer pour éviter les chevauchement.
J'ai peut etre pas besoin de calculer en faite la position dans l'étape 2.1, ca peut se faire ici ?

On progresse on progresse

**millie** · 11/03/2008, 16h42

Envoyé par millie

Il y a une méthode que j'avais utilisé dans une appli web pour visualiser des graphes.

J'utilisais l'outil GraphViz et son format DOT. Je générais un fichier dot (qui correspond grosso modo à l'ensemble des arêtes entre les sommets), je passais GraphViz dessus et j'obtenais une image (png etc...) que je mettais sur le navigateur du client.

http://www.graphviz.org/

Je viens de le refaire

Choix d'un projet dans le navigateur web, récuperation des sources via svn ou cvs automatiquement, parsing des fichiers pom.xml de maven, génération des dépendances, génération du graphe au format gif avec conflit et lecture de l'image via le browser du client.