How does and operator evaluates its arguments. I have a code to check whether a graph is cyclic or not. In this code there is an and condition in an if statement. And I think, to the best of what I can make out is, that it terminates at the first encounter of a false expression without evaluating the second expression at all.
This is the code
bool Graph::isCyclicUtil(int v, bool *visited, bool *recStack){
if (visited[v] == false){
// Mark the current node as visited
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); i++){
-------->**This and cond**if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // remove the vertex from the recursion stack
return false;
}
void Graph::printRecStack(bool *recStack){
cout << "\n \n";
for (int i = 0; i < V; i++){
if (recStack[i])
cout <<i<< "\n";
}
return;
}
bool Graph::isCyclic(){
// Mark all the vertices as not visited and not part of recursion stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for (int i = 0; i<V; i++){
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees.
if (isCyclicUtil(0,visited, recStack)){
printRecStack(recStack);
return true;
}
/*for (int i = 0; i < V; i++){
if (isCyclicUtil(i, visited, recStack))
printRecStack(recStack);
return true;
}*/
return false;
}
Please observe the and condition inside the if statement in isCyclicUtil function.
If you take a simple graph as a test case like this one:
0->1
1->2
2->0
2->3
3->3
And call isCyclicUtil for 0, the first 3 values in recStack comes out to be true. Which should have not been the case if the second expression was also evaluated in the if statement. Because call to node 2 will reach for its child 0. But since the loop started from 0, 0 is already visited, so recStack[0] should be initialized to false. But this does not happens, and all of them come out to be true. As if the and condition terminated as soon as it encountered visited[0] to be true, without even calling isCyclicUtil(0,visited,recStack) again.
