a bug if DFS

[ludachaz]

Hey guys,

I am building a graph ADT which implements DFS to find the strongly connected components of a digraph and I have run into an bug that I can't seem to squash. The program creates a stack, so for example 8 4 6 7 3 5 2 1 is my output (this works) where 8, 4 6, 73, 5 2 1 are strongly connected. The only problem is that the subfields for these vertices such as discover time, parent and finish time are not correctly filled, even though those fields are entered at the same time as the vertices are placed on a stack after they are processed. Its driving me crazy, if you guys can have a look at the DFS and visit code and tell me if I missed something :-/. Anyways here it is, any help would be greatly appreciated. I tested the transposing algorithm and it works fine, and the above output is from the second call on DFS on the transposed graph performed in the order of the finishing times of the first call to DFS.

void visit(GraphRef G, ListRef S, int *time, int vertex){
  G->color[vertex]=0;
  //-1=white, 0=grey, 1=black
  int vertex2;
  *time = *time+1;
  G->discover[vertex]=*time;
  moveFirst(G->neighbors[vertex]);
  while(!offEnd(G->neighbors[vertex])){
    vertex2=getCurrent(G->neighbors[vertex]);
    moveNext(G->neighbors[vertex]);
    if(G->color[vertex2]==-1){
      G->parent[vertex2]=vertex;
      visit(G, S, &*time, vertex2);
    }
  }
  G->color[vertex]=1;
  G->finish[vertex]=*time;
  insertAfterLast(S, vertex);
}

void DFS(GraphRef G, ListRef S){
  int time=0;
  int i;
  int vertex;
  if(getLength(S)!=G->order){
    fprintf(stderr, "DFS error");
  }
  for(i=1; i<G->order+1; i++){
    G->color[i]=-1;
    G->parent[i]=0;
  }
  moveFirst(S);
  while(!offEnd(S)){
    vertex=getCurrent(S);
    if(G->color[vertex]==-1){
      visit(G, S, &time, vertex);
    }
    moveNext(S);
  }
  for(i=1; i<G->order+1; i++){
    deleteFirst(S);
  }
}

and here is psuedocode for dfs and visit for reference

DFS(G)
1 for each vertex u  V [G]
2     do color[u] ← WHITE
3         π[u] ← NIL
4 time ← 0
5 for each vertex u  V [G]
6     do if color[u] = WHITE
7         then DFS-VISIT(u)
DFS-VISIT(u)
1 color[u] ← GRAY ▹White vertex u has just been discovered.
2 time ← time +1
3 d[u] time
4 for each v  Adj[u] ▹Explore edge(u, v).
5     do if color[v] = WHITE
6         then π[v] ← u
7             DFS-VISIT(v)
8 color[u] BLACK ▹ Blacken u; it is finished.
9 f [u] ▹ time ← time +1