Discussion :

[decembre_2006]

bonjour,

quelqu'un sait comment je peux sauver un arbre dans un fichier de façon simple?

merci

[millie]

bonjour,

quelqu'un sait comment je peux sauver un arbre dans un fichier de façon simple?

merci

Ton arbre a-til des propriétés particulières (genre arbre binaire, dans ce cas, c'est facile, c'est comme l'implémentation d'un tas par un tableau) ? En quel langage comptes-tu le réaliser ? (par exemple, java intégre la sérialisation ce qui rendra extremement simple la chose pour tous les types d'arbre)

[PRomu@ld]

Pour m'être posé la question sur un arbre binaire, la solution la plus simple était le parenthésage de l'arbre : tu met entre parenthèse chacun des sous arbres.

Par exemple pour un arbre binaire de l'expression 2+(3*4) ça donne quelque chose comme ça :

Code :

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

1
2
 
(+ 2 (* 3 4))

Le premier élement est donc la racine de ton arbre, le deuxième le sous arbre gauche et le troisième le sous arbre droit.

[FrancisSourd]

Pour m'être posé la question sur un arbre binaire, la solution la plus simple était le parenthésage de l'arbre.

Cette idée de parenthésage marche encore pour les arbres qui ne sont pas binaire. En effet, le parenthésage represente simplement le parcours en profondeur (la parenthèse ouvrante dit de descendre, la parenthèse ouvrante de remonter. On peut imaginer différentes grammaire pour cela du genre:

(Racine,[arbre,arbre,......])

Ainsi, l'arbre

Code :

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

1
2
3
4
5
6
7
 
a--b--c--d
|  |  |
|  |  e
f  g--h
   |\
   i j

se stocke par la chaîne (a,[(f),(b,[(g,[(i),(j),(h)]),(c,[(e),(d)])))

Si nécessaire, un fichier xml peut être tout à fait utile. En effet, tout fichier xml correspond à une organisation arborescente des données. Les tags remplacent alors les parenthèses et les crochets.

[Graffito]

Bonjour,

le langage XML est une bonne solution si le langage utilisé comporte des composants dédiés XML.

[decembre_2006]

Je crois que j'aurais dû être un peu plus juste dans ma demande. Je me suis un peu emmelé les pinceaux.

J'ai un graphe non orienté pondéré que je dois sauvegarder dans un fichier. Pondéré veut dire que sur chacune des arête de mon arbre, j'ai un poids qui lui est associé.

Pour la sérialisation en Java, je n'aime pas cette solution. La classe doit exister pour pouvoir relire les informations sauvegardées dans le fichier. Et si je donne mon fichier à une autre personne qui n'utilise pas Java, il sera incapable de le lire. De plus, je ne pense pas que la réalisation sera en Java, mais en C ou Cplus-plus.

Pour le format XML, je préfère d'abord voir les options de simples fichiers textes.

La solution utilisant les parenthèses proposée m'a l'air intéressante. Mais comment y placer un poids sur les différentes arêtes ?

Merci!

[benratti]

Bonjour,

je sais que c'est à la monde, mais je te conseillerais XML, comme te le conseille Graffito.

Il y a plusieurs raisons à cela :
- le format XML est un format standard ;
- XML est facile a lire par un humain, ce qui implique que même si tu ne documentes pas la maniere dont tu stockes ton graphe ( ce que je te déconseilles ), il serait plus facile de savoir comment il se structure ;
- il existe de nombreuses librairies et API quelque soit le langage qui manipule du XML. Cela permettra de gagner du temps en developpement, ce qui n'est pas négligeale, surtout s'il y a plusieurs applis qui lise ton fichier.

[PRomu@ld]

La solution utilisant les parenthèses proposée m'a l'air intéressante. Mais comment y placer un poids sur les différentes arêtes ?

On peut y placer un poids avec un tag spécial, par exemple pour un arbre binaire (désolé FrancisSourd ) tu peux faire quelque chose dans ce genre :

Code :

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

1
2
 
( racine ( sous_arbre_gauche ):poids ( sous_arbre_droit ):poids )

C'est une solution peut être un peu lourde. Pour le XML, ça s'avère être une solution plus simple, mais pas efficace d'un point de vu stockage (si on ne fait pas de compression derrière). En gros ton XMML peut se structurer ainsi :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
<GRAPH>
     <VERTEXS>
          <VERTEX>
               <DATA>nom</DATA>
               <ID>numero</ID>
          </VERTEX>
 
          ...
 
     </VERTEXS>
     <EDGES>
          <EDGE>
               <SOURCE> Id_vertex </SOURCE>
               <WEIGHT> weight </WEIGHT>
               <TARGET>  Id_vertex </TARGET>
          </EDGE>
 
          ...
 
     </EDGES>
</GRAPH>

Ainsi, ton graphe sera : une liste de sommets et une liste d'arrête (j'ai mis source et target mais si ça n'est pas orienté, tu peux trouver d'autres noms...)

L'avantage est que tu pourras facilement passer ton XML à quelqu'un d'autre, du moment que tu fixes la structure. Une écriture assez simple et une lecture tout aussi simple (soit en utilisant des parsers tout fait soit en passant par une petite analyse lexicale).

Le principal inconvénient comme je l'ai dis précédement c'est un espace mémoire assez conséquent.

Cette idée de parenthésage marche encore pour les arbres qui ne sont pas binaire. En effet, le parenthésage represente simplement le parcours en profondeur (la parenthèse ouvrante dit de descendre, la parenthèse ouvrante de remonter. On peut imaginer différentes grammaire pour cela du genre:

Ce type de représentation fonctionne bien pour les arbres n-aires mais surtout pour des forêts. Cependant, je ne crois pas qu'une solution comme celle que nous proposons puisse fonctionner, en effet s'il y a un cycle le graphe n'est plus un arbre, de même si le graphe n'est plus connexe (mais là ta représentation pourra fonctionner).

[FrancisSourd]

La solution utilisant les parenthèses proposée m'a l'air intéressante. Mais comment y placer un poids sur les différentes arêtes ?

Si cela te facilite la vie, tu peux utiliser le fait qu'un arbre à n-1 arêtes. Une fois défini une racine arbitraire, tu as une bijection entre les arêtes et les noeuds autres que la racine (pour chaque noeud, tu prends l'arête qui le relie à son père.

Si tu veux quelquechose de très compact sans parenthèses, tu peux coder
le parcours en profondeur par la suite des poids des arêtes rencontrées et par un signe quelconque ("-" par exemple) pour les parcours en sens inverse.

Ainsi pour l'exemple:

Code :

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

1
2
3
4
5
6
7
 
a--b--c--d
|  |  |
|  |  e
f  g--h
   |\
   i j

on a: af - ab bg gi - gj - gh - - bc ce - cd - - -
où af représente l'entier correspondant au poids de l'arête af.
En pratique, si tous les arcs valent 1 sauf gh qui vaut 2, cela donne la chaîne
1 - 1 1 1 - 1 - 2 - - 1 1 - 1 - - -

Clairement cette représentation perd les infos relatives aux noeuds. Mais on peut bien sûr les ajouter même sans tag:
a 1 f - 1 b 1 g 1 i - 1 j - 2 h - - 1 c 1 e - 1 d - - -
Ici, on donne en premier la racine puis chaque info sur l'arête visitée est suivie par le noeud d'arrivée.
Pour construire l'arbre à partir de cette chaîne, tu lis a, c'est la racine. Ensuite vient le "1". Tu construis une arête qui par de "a" avec un poids 1 le "f" qui vient ensuite donne le nom du noeud d'arrivée. Le "-" ensuite te dit de remonter dans l'arbre, tu te retrouves en "a" le "1" suivant te dit de repartir avec une arête de poids 1 et "b" te donne l'arrivée. Le "1" te fait partir de ce noeud (b) avec une arête de poids 1 qui va vers le "g" indiqué à la suite... et ainsi de suite

Si ton arbre n'a pas de racine naturelle, tu peux la choisir arbitrairement.

C'est nettement moins lisible que le XML (qui n'est d'ailleurs pas toujours très lisible...)

Comme le dit PRomu@ld, il faut que cela soit effectivement un arbre (sans cycle)

[decembre_2006]

merci PRomu@ld.
je vais essayer comme tu as dit.