add cycle detection

3 files changed, 85 insertions, 0 deletions

diff --git a/Node.lua b/Node.lua
index 1f83c18..5114495 100644
--- a/Node.lua
+++ b/Node.lua
@@ -103,3 +103,44 @@ function Node:bfs(func)
       node.marked = false
    end
 end
+
+function Node:hasCycle()
+
+   local hascycle = false
+   local explorednodes = {}
+
+   local function pre(node)
+      -- if someone found a cycle, just back up
+      if hascycle then return hascycle end
+      -- if this node was marked during dfs, then
+      -- it is still being explored, which means we hit a cycle.
+      if node.marked then
+         -- at this point set visited to true so that Node:visit() does
+         -- not explore this node again
+         node.visited = true
+         hascycle = true
+         return hascycle
+      end
+      node.marked = true
+   end
+
+   local function post(node)
+      -- we are done with this node, so just remove marked info
+      node.marked = false
+      -- set visited to true flagging that this node is done.
+      -- we might hit it in the future through a separate path, but 
+      -- at that point we should not explore it, the Node:visit()
+      -- will avoid visiting any visited node.
+      node.visited = true
+      explorednodes[node] = true
+   end
+
+   self:visit(pre, post)
+
+   -- now clean-up all the nodes
+   for node, _ in pairs(explorednodes) do
+      node.visited = false
+   end
+
+   return hascycle
+end
diff --git a/init.lua b/init.lua
index f3f25dd..339345a 100644
--- a/init.lua
+++ b/init.lua
@@ -86,6 +86,21 @@ function Graph:reverse()
    return rg,mapnodes
 end
 
+function Graph:hasCycle()
+
+   local roots = self:roots()
+   if #roots == 0 then
+      return true
+   end
+
+   for i, root in ipairs(roots) do
+      if root:hasCycle() then
+         return true
+      end
+   end
+   return false
+end
+
 --[[
 Topological Sort
 ** This is not finished. OK for graphs with single root.
diff --git a/test/test_graph.lua b/test/test_graph.lua
index 3ae9e16..3967a85 100644
--- a/test/test_graph.lua
+++ b/test/test_graph.lua
@@ -134,4 +134,33 @@ function tests.test_bfs()
    end
 end
 
+function tests.test_cycle()
+   local n1 = graph.Node(1)
+   local n2 = graph.Node(2)
+   local n3 = graph.Node(3)
+   local n4 = graph.Node(4)
+   local cycle = graph.Graph()
+   cycle:add(graph.Edge(n1, n2))
+   cycle:add(graph.Edge(n1, n3))
+   cycle:add(graph.Edge(n2, n3))
+   cycle:add(graph.Edge(n3, n2))
+   cycle:add(graph.Edge(n2, n4))
+   cycle:add(graph.Edge(n3, n4))
+
+   tester:asserteq(cycle:hasCycle(), true, 'Graph is supposed to have cycle')
+
+   local n1 = graph.Node(1)
+   local n2 = graph.Node(2)
+   local n3 = graph.Node(3)
+   local n4 = graph.Node(4)
+   local nocycle = graph.Graph()
+   nocycle:add(graph.Edge(n1, n2))
+   nocycle:add(graph.Edge(n1, n3))
+   nocycle:add(graph.Edge(n2, n3))
+   nocycle:add(graph.Edge(n2, n4))
+   nocycle:add(graph.Edge(n3, n4))
+
+   tester:asserteq(nocycle:hasCycle(), false, 'Graph is not supposed to have cycle')
+end
+
 return tester:add(tests):run()