Algorithme Tarjan défectueux

Bonjour,

On m'a conseillé ce forum, je viens donc faire appel à votre aide pour un problème sur un algorithme Tarjan de détection de composantes fortement connexes dans un graphe orienté.

Pour les curieux qui éventuellement ne connaitraient pas, voici le wiki très bien expliqué des composantes fortement connexes :

http://fr.wikipedia.org/wiki/Composa...tement_connexe

Donc voilà, un algorithme existe pour repérer ses composantes : L'algorithme de Tarjan. J'ai essayé de le coder moi-même, mais il semblerait que j'aie quelques soucis :

Voici donc mon algorithme commenté. J'espère que quelqu'un sera en mesure de m'aider.
Code:

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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 // Applies Tarjan Algorithm on Graph : this. public void TarjanAlgorithm() { this.index = 0; stack.clear(); if (this != null) { if(this.SetOfVertices != null) { for(Vertex V : SetOfVertices) { tarjan(V); } } } } // Tarjan Function public void tarjan(Vertex v) { v.setIndex(index); // System.out.println("index de "+v.getNumber()+" : "+v.getIndex()); v.setLowLink(index); // System.out.println("lowlink de "+v.getNumber()+" : "+v.getLowLink()); // add to the stack stack.add(v); // if(stack.contains(v)) System.out.println(v.getNumber()+" a bien été empilé"); index++; // for each w of Adjacent Vertex of v for(Vertex w : v.getAdjacentVertices()) { // System.out.println("passage dans les points adjacents au point "+v.getNumber()+" : "+w.getNumber()); // if w.index is undefined if(w.getIndex() == -1) { tarjan(w); v.setLowLink(Math.min(v.getLowLink(), w.getLowLink())); } else { // System.out.println("index de "+w.getNumber()+" : non nul"); if(stack.contains(w)) { v.setLowLink(Math.min(v.getLowLink(), w.getIndex())); // System.out.println("La pile contient "+w.getNumber()); } } } // SCC found if(v.getIndex() == v.getLowLink()) { ArrayList<Vertex> new_scc = new ArrayList<Vertex>(); // pop the stack Vertex w = new Vertex() ; // Pop stack and push scc while( (w.getNumber() != v.getNumber()) && stack.size() != 0) { int x = stack.size() -1; w = stack.remove(x); new_scc.add(w); } SCC scc = new SCC(new_scc); Sccs.add(scc); stack.clear(); } }
J'ai laissé les lignes de debug, elles pourront peut-être vous être utiles...

Quelques informations utiles :

- Cet algorithme est une méthode de la classe Graphe
- Ils existent des classes Vertex, Edge, et SCC (Strongly Connected Component ou Composante Fortement Connexe)

Tu n'explique pas quel est le problème et quel est le résultat attendu ;)

Si tu veux avoir des réponses, le mieux, c'est de poster le code complet d'un exemple ou avec des données en entrée et un affichage de résultat qui ne fonctionne pas. Ca evitera a ceux qui veulent t'aider de devoir se farcir le cours complet et de se prendre la tete a faire fonctionner ton code ;)

Oops désolé, je ne suis pas un habitué des forums :oops:

Voilà le code complet : http://dl.free.fr/mcV7SwruJ (Il faut laisser "data" dans le même rep que "src" )

Code:

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
49
50
51
52
 
public class Edge {
 
	private Vertex nodeFrom;
	private Vertex nodeTo;
 
	private Integer cost;
 
	////////-------------------
 
 
	// Creates Edge without cost equal to 0
	public Edge(Vertex node_FROM, Vertex node_TO) {
		this.nodeFrom = node_FROM;
		this.nodeTo   = node_TO;
		this.cost     = 0;
 
		// Increments degree of vertices
		this.nodeFrom.setDegree(this.nodeFrom.getDegree()+1);
		this.nodeTo.setDegree(this.nodeTo.getDegree()+1);
	}
 
	public Edge(Vertex node_FROM, Vertex node_TO, Integer cost) {
		this.nodeFrom = node_FROM;
		this.nodeTo   = node_TO;
		this.cost     = cost;
 
		// Increments degree of vertices
		this.nodeFrom.setDegree(this.nodeFrom.getDegree()+1);
		this.nodeTo.setDegree(this.nodeTo.getDegree()+1);
	}
 
 
	////////-------------------
 
	public void print(){
		System.out.print("("+this.nodeFrom.getNumber()+","+this.nodeTo.getNumber()+")");
	}
 
	public Vertex getNodeFrom() {
		return nodeFrom;
	}
 
 
	public Vertex getNodeTo() {
		return nodeTo;
	}
 
	public Integer getCost(){
	    return cost;
	}
}

Code:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
 
public class Graph {
 
	private ArrayList<Vertex> SetOfVertices  = new ArrayList<Vertex>(); // All Vertices of this
	private ArrayList<Edge> SetOfEdges = new ArrayList<Edge>();			// ALl Edges of this
	private ArrayList<SCC> Sccs = new ArrayList<SCC>();					// SCC of this (when they are detected)
 
	private int NrVertices;
	private int NrEdges;
 
	// Used for Tarjan Algorithm only
	private ArrayList<Vertex> stack = new ArrayList<Vertex>();
	private int index;
 
	public Graph(String namefile) throws IOException 
	{
		NrVertices = 0;
		NrEdges    = 0;
 
		// Get data from file
		int data[][] = ReadFile(namefile);
 
		// Creates NrVertices vertices
		for(int i=1; i<=NrVertices;i++)
			SetOfVertices.add(new Vertex(i));
 
		// Creates edges from data
		for(int j=0; j<NrVertices; j++)
		{
			for(int k=0; k<NrVertices; k++)
			{
				if(data[j][k] == 1)
				{
					SetOfEdges.add(new Edge(SetOfVertices.get(j),SetOfVertices.get(k)));
					SetOfVertices.get(j).addAdjacentVertex(SetOfVertices.get(k));
 
					NrEdges ++;
				}
			}
		}
	}
 
 
 
	// Constructor
	public int[][] ReadFile(String namefile) throws IOException
	{
			InputStream my_INStream = new FileInputStream(namefile); 
			InputStreamReader my_INStream_Reader = new InputStreamReader(my_INStream);
			BufferedReader br=new BufferedReader(my_INStream_Reader);
 
			// recover dimension in file beginning
 			NrVertices = Integer.parseInt(br.readLine());
 
 			// Creates returned table with values
 			int values[][] = new int[NrVertices][NrVertices];
 
 			// used to recover each line
 			String line;
 
 			// iterator to the line
 			int numOfLines = 0;
 
 			// While we have still lines
			while ( (line = br.readLine()) != null)
			{
 
				StringTokenizer lineTokenized = new StringTokenizer(line);
 
				int numOfTokens = 0;
 
				// Get data and store in a 2D table
				while (lineTokenized.hasMoreTokens()) {
					values[numOfLines][numOfTokens] = Integer.parseInt(lineTokenized.nextToken());
					numOfTokens++;
				}
 
				numOfLines++;
			}
			br.close();
 
			return values;
	}
 
	// Applies Tarjan Algorithm on Graph : this.
	public void TarjanAlgorithm() {
 
		this.index = 0;
		stack.clear();
 
		if (this != null)
		{
			if(this.SetOfVertices != null)
			{
				for(Vertex V : SetOfVertices)
				{
					// just if V isnt already in a SCC
					if( V.isinSCC() == false )
					{
// System.out.println("Passage Tarjan général pour le poitn : "+V.getNumber());
						tarjan(V);
					}
				}
			}
		}
	}
 
	// Tarjan Function
	public void tarjan(Vertex v) {
 
		v.setIndex(index);
// System.out.println("index de "+v.getNumber()+" : "+v.getIndex());
		v.setLowLink(index);
// System.out.println("lowlink de "+v.getNumber()+" : "+v.getLowLink());
 
		// add to the stack
		stack.add(v);
 
// if(stack.contains(v)) System.out.println(v.getNumber()+" a bien été empilé");
 
		index++;
 
		// for each w of Adjacent Vertex of v
		for(Vertex w : v.getAdjacentVertices()) 
		{
// System.out.println("passage dans les points adjacents au point "+v.getNumber()+" : "+w.getNumber());
 
			// if w.index is undefined
			if(w.getIndex() == -1)
			{
				tarjan(w);
				v.setLowLink(Math.min(v.getLowLink(), w.getLowLink()));
			}
			else 
			{
// System.out.println("index de "+w.getNumber()+" : non nul");
				if(stack.contains(w))
				{
					v.setLowLink(Math.min(v.getLowLink(), w.getIndex()));
// System.out.println("La pile contient "+w.getNumber());
				}
			}
		}
 
		// SCC found
		if(v.getIndex() == v.getLowLink())
		{
// System.out.println("new SCC");			
 
			SCC new_scc = new SCC();
 
			// pop the stack
			Vertex w = new Vertex() ;
 
			// Pop stack and push scc
			while( (w.getNumber() != v.getNumber()) && stack.size() != 0) {
				int x = stack.size() -1;
				w = stack.remove(x);
				new_scc.add(w);
				// update isinSCC param
				w.setinSCC(true);
			}
			// add to the list of SCC
			Sccs.add(new_scc);
 
			new_scc.print();
 
			// clear the stack
			stack.clear();
		}
	}
 
	public ArrayList<Edge> getEdges() {
		return SetOfEdges;
	}
 
	public ArrayList<Vertex> getVertices() {
		return SetOfVertices;
	}
 
	public ArrayList<SCC> getSCCs() {
		return this.Sccs;
	}
 
	public void printEdges() {
		for(int i=0 ; i<NrEdges ; i++)
		{
			SetOfEdges.get(i).print();
			System.out.print(" , ");
		}
	}
}

Code:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
import java.util.ArrayList;
 
 
public class Vertex {
 
    private int Number;      
 
    private ArrayList<Edge> outGoingEdges = new ArrayList<Edge>();
	private ArrayList<Vertex> AdjacentVertices = new ArrayList<Vertex>();
	private Integer Degree;
 
	// used for Tarjan Algorithms
	private Integer Index;
	private Integer Lowlink;
    private boolean inSCC;
 
	// Default construtor
    public Vertex(){
        this.init();
        this.Degree = 0;
        this.Index = -1;
    }
 
	// Construtor
    public Vertex(int i){
        this.Number = i;
        this.Index= -1;
        this.Degree = 0;
    	this.init();
    }
 
    // Copy Constructor
    public Vertex(Vertex v) {
    	this.Number = v.getNumber();
    	this.Index = v.getIndex();
    	this.Degree = v.getDegree();
    	this.Lowlink = v.getLowLink();
    	this.outGoingEdges = v.getOutGoingEdges();
    	this.AdjacentVertices = v.getAdjacentVertices();
    	this.inSCC = v.isinSCC ();
    }
 
    // Add Vertex to Adjacent List of Vertices
    public void addAdjacentVertex (Vertex v) {
    	this.AdjacentVertices.add(v);
    }
 
    public int getNumberOfAdjacentVertices() {
 	   return AdjacentVertices.size();
    }
 
    public ArrayList<Vertex> getAdjacentVertices() {
    	return this.AdjacentVertices;
    }
 
    public int getNumber() {
    	return Number;
    }
 
	// intialize the argument visited to false
    private void init(){
        this.inSCC = false;
    }
 
	// inSCC Accessors 
	public boolean isinSCC (){
		return this.inSCC;
	}
 
    public void setinSCC(boolean b) {
        this.inSCC = b;
    }
 
	// return OutGoingEdges
    public ArrayList<Edge> getOutGoingEdges() {
        return outGoingEdges;
    }
 
	// Degree Accessors
	public Integer getDegree() {
		return this.Degree;
	}
 
	public void setDegree(Integer d) {
		this.Degree = d;
	}
 
	public Integer getIndex() {
		return this.Index;
	}
 
	public void setIndex(Integer i) {
		this.Index = i;
	}
 
	public Integer getLowLink() {
		return this.Lowlink;
	}
 
	public void setLowLink(Integer l) {
		this.Lowlink = l;
	}
 
	public void print() {
		System.out.println("Vertex n° "+ this.Number);
	}
 
}

Code:

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
import java.util.ArrayList;
 
 
public class SCC {
 
	private ArrayList<Vertex> SetOfVertices = new ArrayList<Vertex>();
 
	public SCC () {
	}
 
	public SCC (ArrayList<Vertex> v) {
		SetOfVertices = v;
	}
 
	public ArrayList<Vertex> getSCC() {
		return this.SetOfVertices;
	}
 
	public void print() {
		System.out.print("{");
		for(int i=0 ; i<this.SetOfVertices.size() ; i++){
			System.out.print(this.SetOfVertices.get(i).getNumber()+",");
		}
		System.out.println("}");
	}
 
	public int getSize() {
		return this.SetOfVertices.size();
	}
 
	public void add(Vertex x) {
		SetOfVertices.add(x);
	}
}

Code:

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
import java.io.IOException;
 
public class Main {
 
	public static void main (String [] args) throws IOException
	{
		String file = "mat2.txt";
		String path = "./data/"+file;
 
		Graph G1 = new Graph(path);
 
		// Print G1's edges
		System.out.println("Edges :");
		G1.printEdges();
 
		System.out.println("\n \nDetection of Strongly Connected Component :");
 
		G1.TarjanAlgorithm();
		/*
		for(SCC scc : G1.getSCCs()) {
			scc.print();
		}
		*/	
	}
}

Le problème en question :

L'algorithme détecte certaines composantes, mais pas toutes. Dans un Graphe simple (une composante fortement connexe), il n'y a pas de problème, mais sur un graphe plus gros, il en oublie voir n'en trouve pas.

Dans la version actuelle, il en trouve 2 sur 4 :

L'algortithme sort :

Code:

1
2
3
4
5
6
7
8
9
10
11
{13,12,11,10,}
{}
{9,8,}
{}
{}
{2,}
{3,}
{4,}
{5,}
{6,}
{7,}

Alors qu'il devrait trouver :

Code:

1
2
3
4
{13,12,11,10,}
{9,8,}
{5,6,7,}
{1,2,3,4,}

Voici le schéma du graphe dont les composantes fortement connexes sont représentées en bleu (Vive Paint :aie:) :

http://img11.hostingpics.net/pics/96...madugraphe.jpg

On peut essayer d'autres fichiers (dans le rep data) en modifiant l'attribut file en début de main.

Bonjour,

Je n'ai pas encore tout regardé, mais déjà deux remarques :

- Dans la classe Graph.java, il est inutile de faire le faire if (this != null), car ce dernier sera toujours vrai ;
- Dans cette même classe, j'ai l'impression que index n'est jamais initialisé ;

Je ne sais pas si cela est une cause de tes problèmes par contre...

Mako.

Bonjour,

Merci de prendre le temps de te pencher sur mon problème, ce n'est pas une tâche simple.

Citation:

Dans cette même classe, j'ai l'impression que index n'est jamais initialisé ;

En fait si, il est initialisé plus bas, en première ligne de la méthode : TarjanAlgorithm() , c'est vrai que je l'ai omis dans le constructeur, enfin surtout parce que cet attribut sert uniquement pour l'algorithme Tarjan, (on l'incrémente et on attribut le nouvel index à l'attribut index propre à chaque Vertex.)

La classe graph est la plus importante en fait, les autres ne sont là que pour structurer le graphe. Si tu as besoin de commentaires sur certains points et/ou lignes de codes, n'hésites pas à demander !

Avant de remettre en doute ton algorithme, assure-toi que les données en entrées sont correctes.
Classe Graph, méthode tarjan, dernière instruction : tu es sûr de devoir vider ta stack ?
Il me semblait qu'il fallait faire tourner l'algo tant que la stack contient des noeuds.

:O Quelle erreur de ma part !

Voilà une erreur idiote qui m'a fait perdre beaucoup de temps, et à toi aussi (et peut-être d'autre)

Lorsque je vide pas la pile l'algo tourne à merveille !

Je crois que j'ai mal abordé mon problème et mon débogage, cela me servira de leçon !

Merci beaucoup !

Bonjour,

S'il vous plait, quel est le contenu du fichier mat2.txt ?

Merci.