c++ function does not update a class' variables in recursive call

I'm trying to implement Tarjan's Strongly Connected Components Algorithm in C++. Here's how I gotten so far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void tarjan(vector<Vertex>& G){
index = 0;
while (!S.empty()) S.pop();
    for (int i = 0; i<G.size(); i++){
        if (G.at(i).index<0){ //undefined
            strongConnect(G.at(i));
        }
    }
}

void strongConnect(Vertex &v){
    v.index = index;
    v.lowlink = index;
    cout << v.name << ".index is now = " << index << endl;
    index++;
    S.push(v);

    for (int i = 0; i<v.adjList.size(); i++){
        Vertex &w = v.adjList.at(i);
        cout << v.name << " --> " << w.name << endl;
        cout << w.name << ".index was : " << w.index << endl;
        if (w.index<0){ //undefined
            strongConnect(w);
            if (w.lowlink < v.lowlink){
                v.lowlink = w.lowlink;
            }
        }
        else if (doesContain(w)){
            cout << "entered" << endl;
        if (w.index < v.lowlink){
            v.lowlink = w.index;
        }
    }
    }
}



Here's an example graph for the algorithm to run: http://gyazo.com/46db8676d10c7bb159c53d8de6746a6f

Here's the first part of the output of the program:
http://gyazo.com/fed5d88301cf984464b5d70565d8f0b5

all the index & lowlink values of the nodes are set to -1 in the beginning. global index value is set to 0. My problem is, the algorithm starts running on Vertex X-4. It runs the instruction X-4.index=0 & X-4.lowlink=0 then it calls itself with the paramater of node X-1. it sets X-1's index & lowlink values to 1. then it calls itself for X2. then it checks whether node X-4 has the index value <0 or not. Even though we set the value of X-4 to 0 in the first run, it still sees X-4.index as -1. Does anybody have any idea how to solve this issue? Thanks!
http://www.eelis.net/iso-c++/testcase.xhtml (6. Make sure your testcase is self-contained and actually reproduces the problem)

As a blind guess, you are storing a copy of the nodes in the neighbour list. The X-4 that's a neighbour of X-2 is not the same node that you've started the algorithm.
Given that you have all the vertex in a vector, store the index of the node in the vector
Vertex &w = G[ v.adjList.at(i) ];
Topic archived. No new replies allowed.