Structure de donnée de type arbre en Java ?

Version imprimable

25/08/2006, 09h28
joseph_p

Structure de donnée de type arbre en Java ?

Bonjour

J'ai besoin de faire une structure de donnée de type arbre en java. Comment faut il faire ?

Mon besoin de façon plus détailler est qu'un objet feuille puisse accéder à l'objet feuille supérieur (avec une relation 1-n entre la feuille au dessus et celles en dessous).

Afin de compliquer la chose, il y a des conditions sous lesquelles l'objet "fils" essaie de contacter l'objet "père" (genre le fils autorise t il l'héritage et le père la propagation).

J'ai bien des idées, genre de faire un objet "Feuille" ayant un attribut Feuille feuillePere et une méthode public FeuillePere getFeuillePere() mais je ne suis pas sûr que ce soit la meilleure approche.

Merci d'avance ^^
ZedroS

EDIT : en fait la source de données est un fichier xml avec des noeuds qui font référence à leur noeuds père.

Du coup, lors du parsing, je pense passer par une map pour avoir les identifiants des noeuds père et ainsi pouvoir initialiser correctement dans une Feuille l'attribut "Feuille feuillePere".

En effet, à part :
- stocker la correspondance entre l'id et l'objet dans une map
ou
- faire un tableau avec toutes mes feuilles et le parcourir pour retrouver l'objet dont un id est un attribut
je ne vois pas non plus trop comment récupérer mon objet à partir de son id pour l'insérer dans la feuille "fille".

Hum... J'espère ne pas trop être confus :oops: Mais j'aime bien savoir si mes idées "ogrish" sont bonnes ou si on peut faire mieux et plus simple
25/08/2006, 09h55
had35

Si ta source est un fichier xml, utilise le parser DOM. Il modélise déjà les données sous forme d'arbre.
25/08/2006, 10h02
joseph_p

J'utilise déjà DOM/XPATH pour le parcourir, c'est plutot pour la suite et le stockage des données extraites pour laquelle j'ai besoin d'un arbre.

En effet, je dois stocker les données extraites puis permettre à d'autres classes d'y accéder par des méthodes des feuilles "terminales" (mais qui ont besoin de remonter l'arbre pour retourner l'ensemble de données nécessaires).
25/08/2006, 12h05
had35

Tu veux dire que tu veux sérialiser ton arbre ?

Tu pourrais reprendre l'interface javax.swing.tree.TreeNode. Elle a été définie pour être utilisée avec JTree mais elle semble convenir à ce que tu veux faire.
25/08/2006, 12h55
joseph_p

En fait j'pensais de prendre une les noeuds du fichier xml avec seulement une partie de leur attributs/données.

Puis ensuite, à partir des données extraites, je dois manipuler le tout.

En gros mon fichier XML a cette structure :

Noeud A
pere : Aucun
droits définis sur ce noeud : Tous les utilisateurs
héritage : autorisé
propagation : autorisée
données : aucune
Noeud R
pere : Noeud A
droits définis sur ce noeud : utilisateur XYZ
héritage : non autorisé
propagation : autorisée
données : aucune
Noeud X
pere : Noeud R
droits définis sur ce noeud : groupe AZE
héritage : non autorisé
propagation : autorisée
données : document 1
Noeud Y
pere : Noeud R
droits définis sur ce noeud : groupe AAA
héritage : autorisé
propagation : autorisée
données : document 2
Noeud Z
pere : Noeud R
droits définis sur ce noeud : utilisarteur XYW
héritage : non autorisé
propagation : non autorisé
données : document 3
Noeud G
pere : Noeud 1
droits définis sur ce noeud : Aucun
héritage : autorisé
propagation : non autorisé
données : document 4

Pour le document 1, le groupe AZE a le droit de le voir.
Pour le document 2, l'utilisateur XYZ et le groupe AAA y ont accès.
Pour le document 3, l'utilisateur XYW y a accès.
Pour le document 4, tous les utilisateurs y ont droit.

Bien sûr, on me demande de donner les droits pour un document (une donnée) précise...
25/08/2006, 15h18
had35

Si j'ai bien compris, la représentation de ton arborescence avec DOM ou JDom ne te satisfait pas. Compte tenu de l'utilisation que tu veux en faire, les classes Element défini peut être trop de méthode pour toi et tu voudrais en rajouter de spécifiques à ton problème.

Dans ce cas, soit tu pourrais utiliser SAX et construire toi-même ton arbre avec l'interface de classe que tu auras toi-même défini (je pense que ce n'ai pas la définition de l'interface qui te pose problème), soit tu pourrais garder ton parser dom et ajouter à ta Node un constructeur par copie. Il te suffirait de faire une récursion pour parcourir ton arbre.

Est-ce que c'est sur des points techniques que tu bloques ou bien est-ce que c'est juste la vision d'ensemble qui est brouillée ?
28/08/2006, 17h58
joseph_p

Hum, en fait on se comprend mal. Je vais tenter d'éclaircir la chose.

Les données dans mon fichier XML forment en fait un arbre.

Ma question était donc la suivante : y a t il un objet Java afin de facilement faire des arbres ?

En effet, côté parsing pas de soucis, par contre pour le stockage objet c'est moins évident. La solution que j'ai retenue et de stocker dans chaque objet fils l'objet père, puis d'implémenter moi même toute la logique d'arbre.

Ceci dit, je me demandais s'il y avait quelque chose en Java de plus dédié pour faire des arbres (genre un objet TreeList avec des méthodes du type addChild(Object o ) voir même addChildren(Collection o)). J'ai fait quelques recherches mais rien de probant n'en est sorti.
29/08/2006, 09h34
had35

Mis à part dans le cadre d'implémentations spécifiques, comme dom ou jdom, je ne crois pas que ce soit prévu dans l'api Java. En fait, c'est surtout qu'un arbre est relativement simple, et apparemment tu l'as déjà crée. N'oublie pas qu'en Java, les objets sont uniquement référencés, ils ne sont pas imbriqués les uns dans les autres, ils se référencent les uns les autres.

Le seul problème que tu pourrais avoir est que si tu veux gérer des droits d'accès, fais attention de ne pas te retrouver dans quelques années avec des millions de noeuds et donc d'objets à charger en mémoire car le nombre de noeuds augmente plus vite que le nombre de feuilles.

ZedroS, tu parle du parsing de ton fichier/flux XML avec DOM/XPATH.
Je crois que ce que veux te dire had35 (et moi... :)), c'est que tu peux créer un document JDOM reprennant la structure exacte de ton document XML initial.
Ensuite, libre à toi de te ballader dans ce document JDOM, de le modifier, d'ajouter des attributs à des noeuds, des enfants à des des noeuds ou des feuilles, rechercher un parent etc...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public org.jdom.Document getSiteDocument(){
        if(siteDocument==null){
            org.jdom.input.SAXBuilder builder = new SAXBuilder();
            try{
                siteDocument = builder.build(getSiteFile());
            }catch(JDOMException e){
                e.printStackTrace();
            }
        }
 
        return siteDocument;
    }
 
    public File getSiteFile(){
        if(siteFile==null){
            siteFile = new File("resources/sites.xml");
        }
 
        return siteFile;
    }

Avec un bout de code similaire à celui-ci, tu te crée en 2-2 un Document JDOM, sous forme d'arbre et dans lequel tu peux te ballader facilement.
Par exemple, ci-dessous je parcours mon arborescence...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public HashMap getSiteNamesAndPaths(){
        if(siteNamesAndPaths==null){
            siteNamesAndPaths = new HashMap();
 
            Element root = getSiteDocument().getRootElement();
 
            //Retrieve sites information
            List children = root.getChildren();
            for(int i=0;i<children.size();i++){
                siteNamesAndPaths.put(((Element)children.get(i)).getAttributeValue("name"), 
                        ((Element)children.get(i)).getAttributeValue("path"));
            };
        }
 
        return siteNamesAndPaths;
    }

Mais rien ne m'empêchait d'écrire également dans ce document...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
       //Create the Declaration element
      Element declarations = new Element(DECLARATIONS);
 
      //Creating every attributeDecl attributes
      //First one for Naming the cells
      Element attributeDecl = new Element(ATTRIBUTE_DECL);
      Attribute name = new Attribute(NAME,NAME);
      attributeDecl.setAttribute(name);
      Attribute type = new Attribute(TYPE,STRING);
      attributeDecl.setAttribute(type);
      //and adding them to the declaration attribute
      declarations.addContent(attributeDecl);

Est-ce que ça répond mieux à ta question ou ce n'est toujours pas ce type d'arbre que tu veux ?

PS : Pour définir des droits d'héritage/propagation... il te suffit dans cette arborescence de "jouer" avec les enfants ou les attributs des noeuds !

29/08/2006, 10h54
joseph_p

Pas taper, pas taper, moi parler mal, moi pas méchant ;)

Plus sérieusement, j'ai déjà fait un arbre DOM pour parcourir le tout avec XPath.

Après, par contre, j'ai fait ma propre structure d'objet, mais c'est peut être là que j'ai mal fait, car du coup j'y ait fait mon propre arbre (via des attributs "FeuillePere" et des méthodes du genre "getDroitsFromPere()").

Il aurait peut être été plus simple de conserver une structure DOM. Toutefois, le ficheir XML parsé contenait bien plus d'info que les quelques une m'intéressant, du coup il aurait fallu faire du nettoyage dans le DOM, ce que je ne sais pas faire.

De plus, les noms des attributs/balises sont loin d'être explicites, du coup bonjour la relecture du code.

Ceci dit, en passant à ma propre structure, j'ai dû "réimplémenter" une structure d'arbre et du coup je me demandais si je n'avais pas réinventé la roue (genre peut être qu'il existe quelque chose pour faire ça bien, même si je n'avais rien trouvé dans les List/Set/Map de la jdk).

:oops:
29/08/2006, 15h39
had35
Ok, je crois que je vois ce que tu veux dire. En fait il n'existe pas d'objet de type arbre. Pour former une collection, les éléments doivent être référencés dans un objet unique. Pour former un arbre, les éléments doivent être des noeuds qui référencent eux-même un noeud parent, sauf le root. Bon, c'est un peu court mais l'idée est là : il suffit de créer des noeuds pour former un arbre.

Si tu veux lire ton arborescence en partant des éléments finaux plutôt qu'à partir du root, le mieux est d'utiliser une HashMap comme le propose leminipouce. Et si les éléments de dom sont trop complexes, tu peux recopier la structure de l'arborescence en ne gardant que les paramètres qui t'intéressent, là encore en recopiant chaque noeud.
Code:

1 2 3 4 5 6 public class Noeud { public Noeud(org.w3c.Node nod) { [...] } }
30/08/2006, 10h25
benratti

Citation:

Envoyé par ZedroS

Ceci dit, en passant à ma propre structure, j'ai dû "réimplémenter" une structure d'arbre et du coup je me demandais si je n'avais pas réinventé la roue (genre peut être qu'il existe quelque chose pour faire ça bien, même si je n'avais rien trouvé dans les List/Set/Map de la jdk).

Il existe une API qui fourni un certain nombre d'implementation de structures dont les arbres : JDSL. Par contre, je ne l'ai jamais utilisé, donc je ne peux pas trop te dire ce que ca veut, mais ca a l'air pas mal.

Elle est référencé dans la liste des API Java de ce site.
31/08/2006, 17h48
joseph_p

Merci de l'info. Je n'ai pas encore eu le temps de regarder de plus près mais je le ferai. :)
13/09/2006, 15h56
TonioLeRital

Je pense que la réponse à ta question est le design pattern composite, c'est le pattern de structure qui est le plus utilisé en génie logiciel pour la représentation de structures arborescentes (et recursives), tu verras c'est très simple!

bon courage
13/09/2006, 17h34
White Rabbit

Tu peux aussi utiliser un tableau(array).
15/09/2006, 14h17
billynirvana

Si tu regardes du coté de Castor, tu peux peut mettre ton xml dans des objets JAVA. C'est pratique, ca ne résoud pas ton problème, mais tu auras fais un grand pas.

Salut,

Si les implémentations d'arbres sont rares, c'est qu'elles sont vraiment simples à réaliser. Lorsque tu parles de réinventer la roue, tu ne le fais pas vraiment puisque tu utilises des structures algorithmiques que tu adaptes à tes besoins.

Un truc du genre :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class Node { Node parentNode; List childs; List autorisations; // ... public Node(Node parentNode) { this.parentNode = parentNode; } // getParentNode() // addChild(Node child) // addAutorisation(Autorisation autorisation) // ... }
C'est quand meme assez facile et c'est la meilleure solution pour toi car tu auras juste ce dont tu as besoin.

Tu peux faire une classe Root qui hérite de Node dont le père renvoit null et qui peut proposer des attributs supplémentaires comuns à tout ton arbre.

Là ou ca devient problématique, c'est quand tu veux implémenter des fonctions plus complexe de clone, de fusion ou de filtres.

16/09/2006, 15h20
joseph_p

Oui, je suis parti sur une structure d'arbre maison et finalement ça tourne bien.

Ceci dit, le thread a été intéressant, j'y ai appris plein de choses, merci à tous ! :)