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]);