Iterative Depth First Search for cycle detection on directed graphs

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?

Answer 1

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.

Answer 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