Parcours d'un graphe en parallème à l'aide de Thread
Bonjour,
Dans le cadre d'un exercice, il m'est demandé de parcourir un graphe en parallèle à l'aide de Thread.
J'ai créer une méthode me permettant de faire le parcours en largeur de mon graphe depuis un sommet initial donné (par paramètre). Celle-ci gère les éventuels cycles et m'affiche correctement l'ordre des sommets visités.
Ce que j'aimerais bien pouvoir faire maintenant, c'est de lancer un thread pour chaque sommet successeurs du sommet courant et donc que le parcours se fasse en parallèle via ces threads. Et je ne vois pas trop comment m'y prendre en fait. C'est entre ma méthode 'parcoursLargeur' et run() de la classe thread que je ne sais pas trop quoi faire.
Voici ma méthode qui me permet de faire le parcours en largeur avec l'explication.
Explication : J'ai créer une classe Node & Graph pour pouvoir représenter un graph tout simplement.
La méthode comment par créer un ArrayList de Node qui contient en premier lieu le node initial. Ensuite tant que cette liste n'est pas vide, je vais boucler sur les sommets successeurs du premier Node dans la liste et les ajouter dans cette liste pour ensuite retirer le node qui a été traité. Rien de bien sorcier, j'espère cependant avoir fait ça correctement. :P
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void parcoursLargeur(Graph graph, Node initialNode){
ArrayList<Node> list = new ArrayList<Node>();
list.add(initialNode);
initialNode.visited();
System.out.println(initialNode);
while (list.size() > 0){
for (Node node : list.get(0).getSuccessorList()) {
if (!list.contains(node) && !node.isVisited()) {
node.visited();
System.out.println(node);
list.add(node);
}
}
list.remove(0);
}
} |
Et ce qu'il reste juste à faire c'est que pour chaque sommet successeur du sommet courant, c'est lancer un thread pour que le parcours se fasse en parallèle. Auriez-vous une idée ou pourriez-vous m'orienter sur la façon dont je pourrais m'y prendre ?
Bien à vous,
Renaud.
