Mercurial > projects > dil
changeset 699:4c0ea78a7f8b
Fixed cycle detection algorithm.
author | Aziz K?ksal <aziz.koeksal@gmail.com> |
---|---|
date | Sat, 26 Jan 2008 20:59:27 +0100 |
parents | 1564e41f454e |
children | 8e252b7c1459 |
files | trunk/src/cmd/ImportGraph.d |
diffstat | 1 files changed, 9 insertions(+), 3 deletions(-) [+] |
line wrap: on
line diff
--- a/trunk/src/cmd/ImportGraph.d Sat Jan 26 20:08:03 2008 +0100 +++ b/trunk/src/cmd/ImportGraph.d Sat Jan 26 20:59:27 2008 +0100 @@ -71,17 +71,23 @@ void detectCycles() { // Cycles could also be detected in the GraphBuilder, // but having the code here makes things much clearer. - void visit(Vertex vertex) + bool visit(Vertex vertex) { if (vertex.status == Vertex.Status.Visiting) { vertex.isCyclic = true; - return; + return true; } + if (vertex.status == Vertex.Status.Visited) + return false; + // Flag as visiting. vertex.status = Vertex.Status.Visiting; + // Visit successors. foreach (outVertex; vertex.outgoing) - visit(outVertex); + vertex.isCyclic |= visit(outVertex); + // Flag as visited. vertex.status = Vertex.Status.Visited; + return false; } // Start visiting vertices. visit(vertices[0]);