Discussion :

[Alec6]

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]

Bonjour,

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

[Invité]

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]

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]

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]

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]

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]

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