2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Why do you think that lack of tail recursion might be wrong? $\endgroup$ – Rick Decker Mar 16 at 23:27
  • $\begingroup$ In general, turning recursive procedures into iterative ones is as simple as using a stack explicitly. Then simply run a while (not empty stack), pop at the beginning of the body and push at the end, and there you go ... ! $\endgroup$ – Carlos Linares López Mar 16 at 23:28
  • 1
    $\begingroup$ @CarlosLinaresLópez That approach works but I'm not quire sure I agree on "is as simple as". In general, the recursive calls might happen in the middle of the parent function, and their parameters could even depend on the results of the previous calls. This requires storing the position and the state (i.e., local variables) of the parent call in the stack as well, in order to resume its execution (in a way you are simulating jumping to the return address of the caller). $\endgroup$ – Steven Mar 16 at 23:36
  • $\begingroup$ @Steven: that is absolutely true in the general case, but the basic form of depth-first search is implemented with tail recursion which significantly simplifies the implementation with a simple stack $\endgroup$ – Carlos Linares López Mar 17 at 11:21
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.