1

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 :

enter image description here

(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.

4

1 回答 1

0

这是我获取访问后顺序的 DFS 的 C 实现，希望这对某人有所帮助：

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;
}

有些事情可能需要增强，例如使用位数组作为布尔数组而不是 int 数组，但这是我的实际代码，它似乎正在工作。

感谢那些试图帮助我的人。

于 2018-06-15T09:09:19.693 回答