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
Version imprimable
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
Bonjour,
Ta structure d'arbre de départ à des propriétés particulières (binaire, équilibrée, ...) ?
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
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
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.
http://xray.club.fr/dvpimg/treelayout.png
en haut: l'arbre de départ. En rouge la valeur de Taille(N)
en bas: les zones reservées pour l'affichage
C'est une première solution, j'ai pensé à un algo comme cela.
Mais dans cette présentation on a:
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).Code:
2
3
4
5
6
7
8A B G H C D E F m I J K L n o p q r s t u v
J'aimerai réussir à avoir:
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.Code:
2
3
4
5
6
7
8A B G H C D E F m I J K L n o p q r s t u v
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.
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 :roll:
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. :king:Citation:
Envoyé par Alec6
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/
j'ai une tite idee que je creuserais ce soir ou ce we..Citation:
Envoyé par Alec6
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"...
Oui, je l'ai dit au moins 10 fois sur developpez 8OCitation:
Envoyé par pseudocode
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 :aie:
Je commençais comme ça.Citation:
Envoyé par pseudocode
Et je continuais comme ça ;)Citation:
Envoyé par pseudocode
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.
Les parents, comment les places-tu dans un 1er temps ?
(il faut bien qu'ils aient une position pour calculer celles des enfants)
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
Je viens de le refaire :aie: 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.Citation:
Envoyé par millie
J'ai testé moi aussi cette méthode sur mon serveur de gestion de sources. Ca marche très bien... :king:
De mon côté, ça ne sert juste qu'à indiquer des erreurs de dépendances/versions lors de la compilation de projet via une appli Web. :aie:Citation:
Envoyé par pseudocode
Et moi ca affiche l'antériorité des versions des modules de code sur l'interface web de mon SCM fait maison.Citation:
Envoyé par millie