Mercurial > projects > dil

comparison trunk/src/cmd/ImportGraph.d @ 699:4c0ea78a7f8b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed cycle detection algorithm.
author Aziz K?ksal <aziz.koeksal@gmail.com>
date Sat, 26 Jan 2008 20:59:27 +0100
parents 1564e41f454e
children e10838e0b182
comparison
equal deleted inserted replaced
698:1564e41f454e 699:4c0ea78a7f8b
69 69
70 /// Walks the graph and marks cyclic vertices and edges. 70 /// Walks the graph and marks cyclic vertices and edges.
71 void detectCycles() 71 void detectCycles()
72 { // Cycles could also be detected in the GraphBuilder, 72 { // Cycles could also be detected in the GraphBuilder,
73 // but having the code here makes things much clearer. 73 // but having the code here makes things much clearer.
74 void visit(Vertex vertex) 74 bool visit(Vertex vertex)
75 { 75 {
76 if (vertex.status == Vertex.Status.Visiting) 76 if (vertex.status == Vertex.Status.Visiting)
77 { 77 {
78 vertex.isCyclic = true; 78 vertex.isCyclic = true;
79 return; 79 return true;
80 } 80 }
81 if (vertex.status == Vertex.Status.Visited)
82 return false;
83 // Flag as visiting.
81 vertex.status = Vertex.Status.Visiting; 84 vertex.status = Vertex.Status.Visiting;
85 // Visit successors.
82 foreach (outVertex; vertex.outgoing) 86 foreach (outVertex; vertex.outgoing)
83 visit(outVertex); 87 vertex.isCyclic |= visit(outVertex);
88 // Flag as visited.
84 vertex.status = Vertex.Status.Visited; 89 vertex.status = Vertex.Status.Visited;
90 return false;
85 } 91 }
86 // Start visiting vertices. 92 // Start visiting vertices.
87 visit(vertices[0]); 93 visit(vertices[0]);
88 94
89 foreach (edge; edges) 95 foreach (edge; edges)