Discussion :

[Molos]

Bonjour tout le monde.
Actuellement, je suis à la recherche d'un algo qui me permetterais de parcourir un arbre N-Aire, en me couvrant tout les chemins possible d'un point A à un point B.
A l'origine, je pensais utiliser un parcour en profondeur, mais cela ne répond pas à mes besoins.

Voici un exemple de ce que j'ai :

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
 
		<routes>
		<route src="D1">
			<dst condition="MA_COND" etape="E1" label="MON_LABEL" />
			<dst condition="MA_COND2" etape="R2" label="MON_LABEL2" />
		</route>
		<route src="E1">
			<dst condition="MA_COND" etape="R1" label="MON_LABEL" />
		</route>
		<route src="R2">
			<dst condition="MA_COND" etape="E3" label="MON_LABEL" />
		</route>
		<route src="R1">
			<dst condition="MA_COND" etape="end1" label="MON_LABEL" />
		</route>
		<route src="E3">
			<dst condition="MA_COND" etape="end2" label="MON_LABEL" />
		</route>
	</routes>

Et le résultat de sortie attendu :

D1-E1-R1-END1
D1-R2-E3-END2

Avez vous une piste pour un algo qui pourrait répondre en partie à mes besoins ?

PS : Je n'ai pas besoin d'avoir le chemin le plus court

Merci d'avance.

[Sylvain Togni]

En quoi le parcours en profondeur ne répond pas à tes besoins ? Cela semble pourtant être la solution la plus simple à ton problème.

[Molos]

Le problème c'est pour l'affichage

Car en faites, je ne vois pas comment faire pour le stockage des informations entre les différentes branches (routes) possible.

J'avais penser à utiliser une pile, et à chaque fois que l'on remonte, on supprime le dernier élément que l'on a ajouté à la pile, mais je n'arrive pas à voir comment faire pour l'implémenter.

Voila un essai de ce que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
    public ArrayList<Object> parse(Node pSource){  	
    	ArrayList<Object> result = new ArrayList<Object>();
    	result.add(pSource.getLabel());
    	Map<String, Node> children = pSource.getChildren();
    	for (Iterator<Node> child = children.values().iterator() ; child.hasNext() ;){
    		result.add(parse(child.next()));
    	}
    	return result;
    }

[Sylvain Togni]

C'est presque ça

A part que le chemin (result) ne doit pas être une valeur de retour mais un paramètre de la fonction, par exemple :

Code :

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

1
2
3
4
5
fonction parcourir(Noeud noeud, Chemin chemin)
    Si noeud final
        afficher chemin
    Pour tout enfant de noeud
        parcourir(enfant, chemin + enfant)

Le premier appel à parcourir se fera avec un chemin vide. Et dans les appels suivants chemin contiendra les noeuds visités pour atteindre le noeud courant.

[Molos]

Ok, j'ai donc essayé en modifiant mon code

Donc, maintenant ça ressemble à ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
    //Rajouter des conditions pour ajouter les informations
    public void parse(Node pSource, ArrayList<String> pChemin){  	
    	Map<String, Node> children = pSource.getChildren();
    	if(children.size() == 0){
    		pChemin.add(pSource.getLabel());
    		System.out.println(pChemin.toString());
    	}else{
    		pChemin.add(pSource.getLabel());
    		for (Iterator<Node> child = children.values().iterator() ; child.hasNext() ;){
    			parse(child.next(),pChemin);
    		}
    	}
    }

Et mon arbre source est :

Root
/ \
T1 R1
/ / \
T2 E1 E2
/
E3

Hors le résultat que j'obtient en sortie est le suivant :

[Root, R1, E2]
[Root, R1, E2, E1, E3]
[Root, R1, E2, E1, E3, T1, T2]

Pour l'apple, je fait ça :

Code :

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

1
2
3
 
ArrayList<String> chemin = new ArrayList<String>();
arbre.parse(arbre.getRoot(), chemin);

Mais j'ai donc mon problème lorsque l'on remonte, il garde en mémoire tout le chemin déjà parcouru, donc théoriquement, à chaque fois qu'il remonte, je doit supprimer un élément. Mais je vois pas comment le faire :s

Merci d'avance

[Sylvain Togni]

Ah oui, avec un langage à sémantique de référence comme Java, il faut soit faire une copie du chemin soit supprimer le dernier élément en remontant

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
    //Rajouter des conditions pour ajouter les informations
    public void parse(Node pSource, ArrayList<String> pChemin){  	
    	pChemin.add(pSource.getLabel());
    	Map<String, Node> children = pSource.getChildren();
    	if(children.size() == 0){
    		System.out.println(pChemin.toString());
    	}else{
    		for (Iterator<Node> child = children.values().iterator() ; child.hasNext() ;){
    			parse(child.next(),pChemin);
    		}
    	}
    	pChemin.remove(pChemin.size() - 1);
    }

[Molos]

Rohlalala

Vraiment, un super gros merci, car je voyais vraiment pas comment arriver à cette solution

Je me prenais la tête pour rien, car à l'origine j'avais même fait un test, en rajoutant un attribut à mes nodes, pour y mettre leur profondeur, ensuite faire un test de différences entre deux profondeurs, et ensuite faire une boucle de suppréssion sur cette différence (tout ça ne marchais pas :p )

Encore un gros merci