"Process functions" in iterative and recursive depth-first search

Question

I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-first search:

DFS(G,u)
    state[u] = "discovered"
    process_vertex_early(u)
    entry[u] = time
    time = time + 1
    for every vertex v adjacent to u
        if state[v] = "undiscovered"
            parent[v] = u
            process_edge(u,v)
            DFS(G,v)
        else if state[v] != "processed" or G is directed
            process_edge(u,v)
    state[u] = "processed"
    exit[u] = time
    process_vertex_late(u)
    time = time + 1

Notice the use of the process_vertex_early, process_edge, and process_vertex_late functions.

I am attempting to implement an iterative version of depth-first search to avoid a stack overflow with larger graphs. Here is the pseudocode for my attempt:

DFS(G)
    mark every vertex in G as "undiscovered"
    mark the start and finish time for every vertex in G as (0, 0)
    time = 0
    for every vertex vrtx in G
        create empty stack S
        if vrtx is "undiscovered"
            S.push(vrtx)
        while S is not empty
            time = time + 1
            u = S.top
            if u is "undiscovered"
                u.start_time = time
                mark u as "discovered"
                process_vertex_early(u)
            done = true
            for every vertex v adjacent to u
                if v is "undiscovered"
                    done = false
                    v.parent = u
                    process_edge(u,v)
                    S.push(v)
                else if v is not "processed" or G is directed
                    process_edge(u,v)
            if done
                S.pop
                mark u as "processed"
                u.finish_time = time
                process_vertex_late(orig)

I ran both versions of the code for a sample graph of 10 vertices and generated the following data:

Iterative data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       18      -1
1       1       1       1       14      14      5
2       1       1       1       13      13      5
3       1       3       1       5       11      7
4       1       3       1       2       17      0
5       1       6       1       3       16      4
6       1       3       1       6       10      3
7       1       3       1       4       12      5
8       1       3       2       8       8       9
9       1       3       1       7       9       6


Recursive data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       20      -1
1       1       1       1       14      15      5
2       1       1       1       16      17      5
3       1       2       1       7       10      6
4       1       2       1       2       19      0
5       1       4       1       3       18      4
6       1       2       1       6       11      9
7       1       2       1       8       9       3
8       1       2       1       4       13      5
9       1       2       1       5       12      8

Here is the adjacency list for the graph I used:

0 : 4
1 : 5
2 : 5
3 : 6,7
4 : 0,5
5 : 1,2,4,7,8
6 : 3,9
7 : 3,5
8 : 5,9
9 : 6,8

I know that the vertices will be visited in different orders for the recursive and iterative implementations and that neither order is right or wrong, which is why the values for s_time, f_time and parent are different. The early and late columns represent the number of times each function was called for each vertex, while the edge column represents the number of times the process_edge function was called for each vertex as the u vertex. I feel like these values should be the same for both implementations or at least more similar than they are.

My question is: have I preserved the semantics of the original algorithm with my iterative translation? What changes, if any, should I make?

Answer 1

Here is an iterative algorithm which preserves the behavior of the original recursive algorithm. The idea is to let each vertex to keep track of its next child to visit.

Iterative DFS on G starting at vertex v
    mark every vertex in G as "undiscovered"
    create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
    S.push([v,0])
    state[v] = "discovered"
    process_vertex_early(v)

    while S is not empty
        let [v, i] be the top element of S
        if i is less than the number of neighbours of v
            update that element to [v, i+1]
            let w be the i-th neighbour of v
            if w is marked "undiscovered"
                state[w] = "discovered"
                process_vertex_early(w)
                parent[w] = v
                S.push([w, 0])
                process_edge(v, w)
            else if state[w] is not "processed" or G is directed
                process_edge(v,w)
        else
            pop S
            process_vertex_late(v)
            state[v] = "processed"

There are general strategies that convert recursive algorithm/functions to iterative algorithm/functions. You can search "recursion and iteration" for more information if you have not done it yet.

Answer 2

I accepted the answer by @Apass.Jack because it did allow me to exactly replicate the behavior of the original algorithm, albeit with some modifications. I wanted to get the start and finish times for each vertex, so I modified it to get those. I also modified it so that it does not allow the user to provide a start vertex and instead iterates through all the vertices, as in CLRS. I had forgotten to mention this when I asked the question.

Updated pseudocode:

DFS(G)
    mark every vertex in G as "undiscovered"
    set the start and finish time for every vertex in G to (0,0)
    set the parent for every vertex in G to -1
    time = 0
    for every vertex u in G
        create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
        if u is "undiscovered"
            S.push([u,0])
        while S is not empty
            let [v,i] be the top element of S
            if v is "undiscovered"
                time = time + 1
                v.start_time = time
                mark v as "discovered"
                process_vertex_early(v)
            if i is less than the number of neighbors of v
                update that element to [v,i+1]
                let w be the i-th neighbour of v
                if w is marked "undiscovered"
                    parent[w] = v
                    process_edge(v,w)
                    S.push([w,0])
                else if state[w] is not "processed" or G is directed
                    process_edge(v,w)
            else
                time = time + 1
                pop S
                state[v] = "processed"
                process_vertex_late(v)
                v.finish_time = time

This new algorithm generates the same exact data as the recursive pseudocode presented in the original question, both for directed and undirected graphs.