Trouble with list

[radioHarry]

Hello everyone,

I am new here. I use this website excessively everyday for reference. I hit a blocker while coding this simple program and I guess I can use some help from the experts here.

I am trying to create a graph or a logical implementation of it (which I did successfully). Then I tried traversing it using 'Depth First Search'. It worked for the first iteration of the node from where I started and after that, it just goes haywire.

I am using graphNode.h and dfs.cpp (which includes graphNode.h). Following is graphNode.h

#include <iostream>
#include <list>

using namespace std;

class graphNode {

                public:
                        string value;
                        list<graphNode> adjacents;
                        bool isVisited;


                public:
                        graphNode () {

                                isVisited = false;
                        }

                        void addNode (string str);
                        void addAdjacent (graphNode g);
};

void graphNode :: addNode (string str) {

        value.assign(str);
}

void graphNode :: addAdjacent (graphNode g) {

                adjacents.push_back (g);
}

Following is dfs.cpp:

#include <iostream>
#include <stack>
#include </home/graphs/graphNode.h>

using namespace std;

class dfs : public graphNode {

	public:
		stack<graphNode> st;

	public:
		void traverseGraphIter (graphNode node);
};

void dfs :: traverseGraphIter (graphNode node) {

	list<graphNode>::iterator it;
	st.push(node);

	do {
		node.isVisited=true;
		st.pop();
		cout<<"\n #### Popped node "<<node.value;
		
		// Go over node's adjacents and add them to the stack if they
		// were not visited earlier
		for (it=node.adjacents.begin(); it!=node.adjacents.end(); it++) {
			if (it->isVisited == false) {
				st.push(*it);
			}
		}

		/* Have to put this check to avoid a SEGV because 
                   compiler does not thrown an error when the stack is empty 
                   and a method call like pop or top is being called on it. */
		if (!st.empty()) {
			node=st.top();
			cout<<"\n Node "<<node.value<<"'s adjacent list contains "<<(int)node.adjacents.size()<<" elements";
		}

	} while (!st.empty());

	cout<<"\n Exiting the do-while loop";
}

int main () {

		int size=4;
		string s;

         	graphNode *node = new graphNode[size];
			
		for (int i=0; i<size; i++) {

			cout<<"\n Enter the value for the node : ";
			cin>>s;		
			node[i].addNode(s);
		}

	        //Hard coding the adjacents for now 					
		node[0].addAdjacent (node[1]);
		node[0].addAdjacent (node[2]);
		node[1].addAdjacent (node[2]);
		node[2].addAdjacent (node[3]);
		node[2].addAdjacent (node[0]);
		
                //Check if adjacents are added correctly
		list<graphNode>::iterator it;

		for (int i=0; i<4; i++) {
			if (node[i].adjacents.empty()) {
				cout<<"\n Node "<<node[i].value<<"'s adjacent list is empty. Continuing from the top";
				continue;
			}
			for (it=node[i].adjacents.begin(); it!=node[i].adjacents.end(); it++ ) {
				cout<<"\n Node "<<node[i].value<<"'s adjacent is "<<it->value; 
			}
		}

		dfs d;
		d.traverseGraphIter (node[0]);
		
		//Destructor
		delete[] node;	

		cout<<"\n\n";
												
	return 0;
}

I left the debugging stuff there in case you guys want to run it to verify if things are in right place to begin with. I have hard coded the number of graphNodes and the adjacents. So for nodes A, B, C and D (using node: adjacents format), I am doing:

A: B, C
B: C
C: D, A
D: <EMPTY>

Idea: I am just creating 4 graphNodes and storing each graphNode's adjacent list with the node. The list is of type graphNode, so it should store the graphNode object itself. Starting from the graphNode object that I pass to the function traverseGraphIter(graphNode):

1) Add each node to the stack, mark it visited, pop it and print it.
2) Then explore its unvisited adjacents, add them to the stack. Then for each adjacent continue from step 1 .....while stack is not empty.

Problem: Let us say that I enter node A, B, C and D. I pass object for node A to the function traverseGraphIter(graphNode). A contains 2 adjacents (B and C). Node B and Node C get added to the stack. When the program print the number of elements in the adjacent list of B and C, it is 0 and indeed B and C adjacent list is empty. I thought that the root cause was that I was sending a copy of A which may not be copying B & C's list information. Don't know why that should happen because B and C's values and isVisited fields print just fine. I tried passing by reference. That did not work either.

What am I doing wrong here? I have spent hours debugging this. Help please!!

Thanks much!

[helios]

It's a disaster. Everything makes a copy of everything else. It's practically impossible to reason about how the data is flowing through the structure because none of the changes you make are permanent.
Just to name one example:

class graphNode {

                public:
                        string value;
                        list<graphNode> adjacents;
                        bool isVisited;

This doesn't define a general graph. What you get, I think, is like some sort of weird tree that looks like a graph, but isn't.

Start by using pointers to link together nodes. I recommend a vector of pointers. Then make the traversal function take its parameter by reference. Then you might be able to make it work.

[radioHarry]

Hi Helios,

Thanks for replying.

Everything makes a copy of everything else.

I guess you are talking about each graphNode keeping a list of its adjacents, which are of type graphNode too. I am not going to disagree there. List does contain each graphNode object and as the size of the graph expands, space complexity will start rising too.

Start by using pointers to link together nodes

That was my original approach but I saw 2 examples, by a buddy of mine, of a logical implementation of a graph working in exact same way. The code was in Java. Implementation was quite the same and works just right. He is using the same logic of using a list of adjacents for each node.

This doesn't define a general graph. What you get, I think, is like some sort of weird tree that looks like a graph, but isn't.

It does logically implement a graph. Think about it -- Each node in a directed graph may or may not have adjacent nodes. One can choose to link those using pointers or logically keep track of those adjacent nodes in a data structure, such as list. That is what I am doing with each node.

A: B, C
B: C
C: D, A
D: <EMPTY>

My point is that it should work. It worked for node A & I got its adjacent nodes out of the list (B and C). But for nodes B and C, the adjacent list was empty. Assuming this is the correct way to implement a graph, why would the adjacent list be empty? Even if I start implementing this using pointers or resort to Java, I am still interested in knowing that. This will be a good learning experience anyway.

Thanks much!

[helios]

The code was in Java.

C++ is not Java. Java "objects" actually have pointer semantics. If you do this in Java

Node a,b;
a=b;

it doesn't make a copy of b. It just makes a point to the object that b points to.

It does logically implement a graph.

Trust me. It doesn't.
For example, if you try to make this graph:
A -> B -> C -> A
you'll notice that you can't. Sure, if you print the names of the nodes each node points to, it'll look okay. But if you actually try to iterate over the list, you'll eventually hit a node that doesn't point to any other node. This is because of the way you construct your nodes. Suppose you do it like this:

graphNode A,B,C;
A.addAdjacent(B);
B.addAdjacent(C);
C.addAdjacent(A);

On line 2, you're making A point to B. But that's not quite it. What you're actually doing is adding a copy of B to the list in A. When on line 3 you make B point to C, you're only modifying the object that sits on the stack. The object that's inside of A's list is a different instance, and it's still pointing to no other node. And so on.
It doesn't matter in what order you make the links, either:

graphNode A,B,C;
C.addAdjacent(A);
B.addAdjacent(C);
A.addAdjacent(B);

By the end, A does indeed point to a B that points to a C that points an A. But this A is, again, not the same one as the A that's on the stack. The one on the structure is a copy of the A when it was still pointing to nothing.

It's impossible to define a graph in this manner.

[radioHarry]

Thanks for replying helios.

I understand what you're saying. It makes sense. I implemented my nodes, node storage in list and stack as pointers and things work now.

So stack holds a pointer to the graphNodes -- stack<graphNode*> st;
List is -- list<graphNode*> adjacents;
I am passing the node's address to traverseGraphIter (graphNode *g)

...etc.

Thanks again for clarifying the doubt. It was helpful to learn this.

Cheers!