Hamid MousaviNasab Hamid MousaviNasab - 3 years ago 43
C++ Question

Unable to access contents of file-scope variable from another function

I have 2 functions and one of them is recursive. Here is the real code:

class Graph {
public:
Graph(int v);
virtual ~Graph();

void addEdge(int v, int w);

/**
* main function that finds and checks SCC
*/
bool checkSCC();

/**
* function that returns reverse (or transpose) of this graph
*/
Graph getTranspose();
private:
int V;
std::list<int> *adj;
std::vector<int> scc;

/**
* fills stack with vertices (in increasing order of finishing times).
* the top element of stack has the maximum finishing time.
*/
void fillOrder(int v, bool visited[], std::stack<int> &stack);

/**
* a recursive function to print DFS starting from v
*/
void DFSUtil(int v, bool visited[]);
};

Graph::Graph(int v) {
this->V = v;
adj = new std::list<int>[v];
}

Graph::~Graph() {
}

void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}

bool Graph::checkSCC() {
std::stack<int> stack;

bool *visited = new bool[V];
for(int i=0; i<V; i++)
visited[i]=false;

for(int i=0; i<V; i++)
if(visited[i]==false)
fillOrder(i, visited, stack);

Graph gr = getTranspose();

for(int i=0; i<V; i++)
visited[i]=false;

while(stack.empty() == false){
int v = stack.top();
stack.pop();

if(visited[v]==false){

if(scc.size() > 1) { /*NOTE the problem is HERE !*/
return true;
}

gr.DFSUtil(v, visited);
}
}

return false;
}

Graph Graph::getTranspose() {
Graph g(V);
for(int v=0;v<V;v++){
std::list<int>::iterator i;
for(i=adj[v].begin();i!=adj[v].end();++i)
g.adj[*i].push_back(v);
}
return g;
}

void Graph::fillOrder(int v, bool visited[], std::stack<int>& stack) {
visited[v] = true;

std::list<int>::iterator i;
for(i = adj[v].begin(); i!= adj[v].end(); ++i)
if(!visited[*i])
fillOrder(*i, visited, stack);

stack.push(v);
}

void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
scc.push_back(v); /*NOTE scc only works in this function !! */
std::cout << v << " ";

std::list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
Graph::DFSUtil(*i, visited);
}


In this code, if i call Graph::checkSCC, scc preserve it's contents in scope of Graph::DFSUtil but NOT in Graph::checkSCC !! Why this happens ?

I appreciate any ideas and suggestions.

Answer Source

You're calling checkSCC on one object, and DFSUtil on another one (gr, which you create in checkSCC).

The scc member of one has no connection to the scc member of the other.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download