"Process functions" in iterative and recursive depth-first search 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?
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.