Discussion :

[pmartin8]

Bonjour,

J'utilise la librairie JGraphT pour gèrer un graphe orienté acyclique.

Maintenant, je tente de trouver tous les chemins possibles à partir d'un sommet. Est-ce que quelqu'un peut me dire comment faire?

Merci

[dazz_x]

[Mode Algo Bourrin On] throw PriseDAspirineException
Je pense que
1- je créerais une classe chemin qui contiendrait une ArrayList de Vertex
2- je maintiendrais une ArrayList de chemins dans la classe qui demande l'opération, et je l'initialise avec un chemin réduit au Vertex de départ v0
Ensuite je créerais une méthode récursive genre getPaths(Chemin c) qui chercherais en arrivant sur un Vertex les Vertex qu'elle peut atteindre (soit à l'aide d'une méthode directe qui existe peut être mais que je ne connais pas, soit en récupérant les arêtes incidentes et en trouvant leur vertex cible) : exemple on est en v0 et on peut atteindre v1 et v2
- j'ajouterais le chemin entré (c) à ma liste de chemins, je créerais autant de nouveaux chemins que de sommets à atteindre (c1= c+V1,c2= c+v2) et on relance récursivement la fonction sur tous ces chemins, tant qu'il y a des sommets à atteindre (condition d'arrêt obligatoirement remplie si ton graphe est bien orienté et acyclique !! )
[Mode Algo Bourrin Off]

[dazz_x]

bon allez, j'ai deux minutes...

classe Test

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
import java.util.ArrayList;
 
public class Test {
 
	//liste des chemins
	ArrayList<Path> aPathList;
 
	public Test(){
		aPathList=new ArrayList<Path>();
	}
 
	public void getPath(Path p,Object vertex){
 
		//on ajoute le nouveau chemin à la liste des chemins
		aPathList.add(p);
		//on récupère les vertex qu'on peut atteindre
		ArrayList<Object> aReachableVerticesList=getReachableVertices(vertex);
		for(Object vert:aReachableVerticesList){
			//on crée les nouveaux chemins
			Path pi=new Path(p,vert);
			//et c'est reparti pour un tour !!!
			getPath(pi,vert);
		}
	}
 
 
	private ArrayList<Object> getReachableVertices(Object vertex) {
		/*
		 *  A toi de remplir ce code !!!!! ;-)
		 */
		return null;
	}
 
	/**
         * @param args
         */
	public static void main(String[] args) {
 
		Path p=new Path();
		//c'est pour le preier sommet dont on veut partir
		Object SommetRoot=new Object();
		p.add(SommetRoot);
		Test test=new Test();
		test.getPath(p,SommetRoot);
	}
 
}

Classe Path

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
23
24
 
import java.util.ArrayList;
 
 
 
public class Path {
 
	ArrayList<Object> aVerticesList;
	public Path(){
	 aVerticesList=new ArrayList<Object>();
	}
 
	public Path(Path p,Object vertex){
		aVerticesList=new ArrayList<Object>();
		for (Object vert : p.aVerticesList){
			this.aVerticesList.add(vert);
		}
		this.aVerticesList.add(vertex);
	}
 
	public void add(Object vertex){
		aVerticesList.add(vertex);
	}
}

Bon, voilà, j'ai pas fait de test, mais ça doit être à peu près dans ce genre là mon idée !!
Le test d'arrêt, qui n'est pas mis ici, c'est quand la liste des vertex accessibles est vide....

[pmartin8]

merci

j'essaye ca!