Iterative DFS on graph with post-visit ordering

Question

I'm currently trying to implement the Kosaraju's algorithm on directed graph to find all strongly connected components.

I understand quite well how this algorithm works, but I have some issues when getting the post-visit order of the DFS result.

For now, the pseudo code of my DFS implementation is the following :

[EDIT] : I finally got a DFS version with the post visit order as output. I thought about increment a number representing the "lock" of a node each time this node push a neighbour on the DFS stack. Then when a node's visit is ended (no more neighbours to push), I notice the one which pushed it that the DFS from this child is ended (I decrement its lock). If this notification ends the visit of the preceding too, I go up to the previous preceding node to notice it, etc...

dfs(G, s):
    for all v in vertices :
        mark[v] = false
        blocked[v] = 0
        preceding[v] = -1
    mark[s] = true
    create a stack P
    P.push(s)
    while P not empty:
        v = P.pop
        for all t neighbours of v:
            if mark[t] = false:
                mark[t] = true
                blocked[v]++
                preceding[t] = v
                P.push(t)
        if no neighbours added to the stack:
            while(blocked[v] == 0):
                result.push(v);
                v = (preceding[v] == -1) ? preceding[v] : v 
                blocked[v]--

But I'm not sure that this kind of implementation outputs the right post order for Kosaraju's algorithm.

Is my DFS right or not ?

Example of my DFS :

(I listed the vertices clockwise, so a = 0, b = 1, c = 2, d = 3, h = 4, g = 5, f = 6, e = 7)

Graph as adjacency list :

{0} --> {1}

{1} --> {2, 6, 7}

{2} --> {3, 5}

{3} --> {2, 4}

{4} --> {3, 5}

{5} --> {6}

{6} --> {5}

{7} --> {0, 6}

An other issue with my DFS is that my algorithm computes neighbours in decreasing order. I thought it was not important because of neighbours are in fact set of vertices but in my example I got weird issue.

Explanation of the increasing computation order of neighbours:

Entering 0, opening 1

I pop the DFS stack (was {0}), it returns 0. He has 1 as neighbour, so I push 1 on the DFS stack (now is {1})

Entering 1, opening 2 6 7

I pop 1 from the DFS stack, he has 2, 6 and 7 as neighbours, so I push them on the stack (now is {7, 6, 2})

Entering 2, opening 3

I pop 2 from the stack (now is {7, 6}), neighbours are 3 and 5, I push them, the stack is {7, 6, 5, 3}

Entering 3, opening 4

*I pop 3 from the stack (now is {7, 6, 5}), 4 is the only one neighbour, I push it, the stack is {7, 6, 5, 4}

Entering 4

I pop 4 from the stack (is {7, 6, 5}), 5 is a neighbour but already "marked" because was neighbour of 2

Entering 5

I pop 5 from the stack, now is {7, 6}, all neighbours (6) are already "marked

Entering 6

I pop 6 from the stack, {7}, 5 is an already "marked" neighbour

Entering 7

I pop 7 from the stack, {empty}, neighbours (1 & 6) are already "marked"

my result array is 0 1 2 3 4 5 6 7 because I "treated" nodes is this order (or 7 6 5 4 3 2 1 0 with my post-visit implementation)

With decreasing computation order of neighbours (my actual DFS), I got :

Entering 0, opening 1

stack {} -> {1}

Entering 1, opening 7 6 2

stack {} -> {2, 6, 7}

Entering 7

stack {2, 6} -> {2, 6}

Entering 6, opening 5

stack {2} -> {2, 5}

Entering 5

stack {2} -> {2}

Entering 2, opening 3

stack {} -> {3}

Entering 3, opening 4

stack {} -> {4}

Entering 4

stack {} -> {}

And I got the following result 0 1 7 6 5 2 3 4 (or 4 3 2 5 6 7 1 0 for post visit)

The issue is, when I reverse the graph to compute the final part of Kosaraju's algorithm, the two results are not equivalent:

1st result (which get finally the right amount of SCC) (stack {7, 6, 5, 4, 3, 2, 1, 0}):

Opening 0, dfs returns 1 and 7 -> 0, 1, 7 are in the same SCC, delete them from the working stack (now is {6, 5, 4, 3, 2}) and the graph.

Opening 2, dfs returns 3 and 4 -> 2, 3, 4 are in the same SCC, delete them from the working stack (now is {6, 5}) and the graph.

Opening 5, dfs returns 6 -> 5, 6 are in the same SCC

2n result, stack {4, 3, 2, 5, 6, 7, 1, 0}:

Opening 0, dfs returns 1 and 7 -> 0, 1, 7 are in the same SCC, delete them from the working stack (now is {4, 3, 2, 5, 6}) and the graph.

Opening 6, dfs returns 5, 4, 3 and 2 -> 2, 3, 4, 5, 6 are in the same SCC (BUT THEY AREN'T) (because in the reversed graph, starting from 6 I go to 5 then to 4 or 2...)

Can anyone explain me why compute vertices in increasing or decreasing order into the DFS don't get the same result for Kosaraju's algorithm ?

EDIT: I put some extra informations about how I get the results and how I run the algorithm by hand. Hope it is clearer now.

Answer 1

Here is my C implementation of the DFS getting the post visit order, hope this will be helpful for someone:

typedef struct _graph_list {
    int nb_nodes;
    int* tab_nodes;
    int* succ_list;
} graph_list;

typedef struct _stack {
    unsigned int max_capacity;
    int* array;
    int top_position;
} stack;

int* getSuccFromList(graph_list* graph, int i){
    if (graph->tab_nodes[i] == -1) return NULL;
    int case_succ = graph->tab_nodes[i];
    int next_case_succ = graph->tab_nodes[++i];
    while (next_case_succ == -1){
        next_case_succ = graph->tab_nodes[++i];
    }
    int nb_succ = next_case_succ - case_succ;
    int j;
    int* res = malloc(sizeof(int)*(nb_succ + 1));
    for(j = 0; j < nb_succ; j++){
        res[j] = graph->succ_list[case_succ + j];
    }
    res[nb_succ] = -1;
    return res;
}

int* dfsPostVisit(graph_list* graph, int vertex){
    int i, j, nb_nodes, tmp_v;
    int* succ;
    int eof_visit;
    nb_nodes = graph->nb_nodes;
    int* res = malloc(sizeof(int)*(nb_nodes + 1));
    int* mark = malloc(sizeof(int)*nb_nodes);
    int* blocked = malloc(sizeof(int)*nb_nodes);
    int* prec = malloc(sizeof(int)*nb_nodes);
    for(i = 0; i < nb_nodes; i++){
        res[i] = -1;
        mark[i] = 0;
    blocked[i] = 0;
    prec[i] = -1;
    }
    res[nb_nodes] = -1;
    stack* s = createStack(nb_nodes);

    push(s, vertex);
    mark[vertex] = 1;
    i = 0;
    while(!isEmpty(s)){
        vertex = pop(s);
        succ = getSuccFromList(graph, vertex);  
        j = 0;
        eof_visit = 0;
        if(succ!=NULL){
            while(succ[j] != -1){
                tmp_v = succ[j++];
                if(!mark[tmp_v]){
                    mark[tmp_v] = 1;
                    blocked[vertex]++;
                    prec[tmp_v] = vertex;
                    push(s, tmp_v);
                    eof_visit++;
                }
            }
            free(succ);
        }
        if (eof_visit == 0){
            while (blocked[vertex] == 0){
                res[i++] = vertex;
                vertex = (prec[vertex] >= 0)? prec[vertex] : vertex;
                blocked[vertex]--;
            }
        }
    }
    i = 0;
    freeStack(s);
    free(mark);
    free(blocked);
    free(prec);
    return res;
}

Some things may need to be enhanced, e.g. using bits arrays as boolean arrays instead of int arrays, but this is my actual code and it seems to be working.

Thanks for the ones who tried to help me.