Iterative Depth First Search for cycle detection on directed graphs
-
29-09-2020 - |
Question
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:
L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
if n has a temporary mark then
stop (not a DAG)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
remove temporary mark from n
mark n with a permanent mark
add n to head of L
I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.
How should I approach this?
Solution 2
Using the same logic as the recursive algorithm, I added on the stack a pos
value which keeps track of the position of the last descendant currently processing.
This was necessary for the "backtrack" steps of the algorithm.
from typing import List
UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1
def is_acyclic(graph: List[list], vertex_count: int) -> bool:
state = [UNDISCOVERED] * vertex_count
for vertex in range(vertex_count):
if not dfs(graph, vertex, state):
return False
return True
def dfs(graph: List[list], v: int, state: list) -> bool:
stack = [(v, 0)]
while stack:
curr, pos = stack[-1]
if state[curr] == PROCESSED:
stack.pop()
continue
if state[curr] == DISCOVERED and pos == 0:
return False
if pos == 0:
state[curr] = DISCOVERED
for i in range(pos, len(graph[curr])):
stack[-1] = curr, pos + 1
descendant = graph[curr][i]
stack.append((descendant, 0))
break
else:
state[curr] = PROCESSED
return True
OTHER TIPS
You could add "colors" to the nodes similar to the method done for recursive DFS found in CLRS, for example. When you instantiate each node (assuming they are objects) put a color field such that every node initially has node.color
$\xleftarrow{}$ white.
The following is your pseudocode modified that I believe would help:
L ← Empty list of all nodes, where node.color ← black (once placed here)
while exists nodes such that node.color is white do
select a node n such that n.color is white
visit(n)
function visit(node n)
if n.color is black then:
return
if n.color is gray then:
stop (back edge is found indicates cycle exists)
mark n.color as gray
for each node m with an edge from n to m do
visit(m)
mark n.color as black
add n to head of L
The idea is that all "unvisited" nodes begin colored "white". Then, when we encounter a node, we visit it and color it "grey" while exploring it. When we are done exploring this node, we color it "black". We only call DFS on nodes with "white" color.
Also regarding implementation, in addition to the stack, you could make L
a set and just do a check on the size (since you know only distinct nodes will get added to this set) and once the size is equal to the number of nodes you know you've visited all the nodes of the graph, but as is if you use the coloring eventually it'll be the case that there is no node, n
such that n.color == white
.