Problem with graph implementation using adjacency lists

[iokon]

The following code is part of a bigger project in which I simulate a non-directed graph using adjacency lists. The code has no compilation errors. When I use in my main function (which is not provided below) the InserEdge function for the first time (to insert e.g the edge <1,3>) then there is no problem. But when I try to insert a second edge with the same initial node (e.g <1,6>) then the program fails. More particulartly, when I am debugging the code, the while loop in InsertEdge function, seems never to end, a fact which is not logical and I can't figure out why, as I initialize all my adj pointers to NULL. I know I could use STL library but I am not very familiar with.
I would appreciate any help, thanks in advance!

class Edge;

class Node
{
public:
	int id;              
	bool visited;        
	Edge* adj;
	int distance;
	Node* previous;
	Node(int);
	~Node();
};

class Edge
{
public:
    Node* initial;                              //first node
    Node* next;	                             //secong node of the edge
	Edge* adj;                                 //used to point the next edge in the adjacency list
	int w;
	Edge(Node*, Node*, int);
	~Edge();
	bool Connects(Node* node1, Node* node2)
	{
		return((node1==this->initial&&node2==this->next)||(node1==this->next&&node2==this->initial));
	}
};

Node::Node(int a)
{
	id=a;
	visited=0;
	adj=NULL;                     // used to point the first edge inserted in the adjacency list with 
	                                      // the first node to be node a
    previous=NULL;
	distance=INT_MAX;
}

Node::~Node()
{

}

Edge::Edge(Node* a, Node* b, int weight)
{
	initial=a;
	next=b;
	adj=NULL;
	w=weight;
}

Edge::~Edge()
{

}

class MyGraph
{
public:
	int Maxnodes;
	int count;
	int m;
	Edge* Akmes[];                    // stores all the edges inserted in the graph
	Node* List[];                         // stores all the nodes of the graph. Every node i has a pointer (List[i]->adj)
                                                         // pointing to a queue of edges. The common of all these edges is that they
                                                         // have as initial node the same node i. 
	Node* remaining[];
	MyGraph(int);
	~MyGraph();
	Node* findnode(int);
	void InsertEdge(int,int,int);
};



MyGraph::MyGraph(int size)
{
	Maxnodes=size;
	for (int i=1;i<=Maxnodes;i++)
	{
		List[i-1]=new Node(i);
	}
	m=0;
	count=0;
}

MyGraph::~MyGraph()
{

}

Node* MyGraph::findnode(int a)
{
	Node* x;
	for (int i=0;i<Maxnodes;i++)
	{
		if(List[i]->id==a)
			x=List[i];
	}
	return x;
}

void MyGraph::InsertEdge(int x, int y, int w)
{
	Node* a=findnode(x);
	Node* b=findnode(y);
	Edge* akmi=new Edge(a,b,w);       //  I insert edge <a,b> in the graph
	Akmes[count]=akmi;
	count++;
	Node* p;
	Node* q;
	Edge* l;
	p=List[x-1];
	l=p->adj;
	if (l==NULL)                                //  if there is no edge inserted starting with node x
		p->adj=akmi;                  //  then insert this edge, and define the pointer of node x to point
                                                                // to this first edge 
	else
	{
		while (l!=NULL)             // else insert the new edge after the last edge that has been inserted in 
			l=l->adj;             // the graph with the same initial node x. Define the pointer of the last 
                                                                // edge to point to the new last edge.
		l=akmi;
	}
	Edge* akmi2=new Edge(b,a,w);            //  I also insert edge <b,a> as my graph is undirected
	q=List[y-1];
	l=q->adj;
	if (l==NULL)
		q->adj=akmi2;
	else
	{
		while (l!=NULL)
			l=l->adj;
		l=akmi2;
	}
}

[tdlr]

In line 109:

Akmes[count]=akmi;

You are accessing Akmes with the index count, without checking wether Akmes has enough memory reserved for count elements.
Also, where do you new[] and delete[] your array called Akmes?

I'd recommend you use std::vector<Nod e*> or std::vector<std ::shared_ptr<No de>> with the latter being C++0x and therefore only available in VC++2010 and g++4.6 or so (maybe others too, don't know). vector does the memory management for you and then you just myVector.push_b ack(&someNode); and the vector will reallocate memory if required. You may then access the vector in the same way you would access an array: myVector[0] is first element and so forth.

Sample code:

#include <vector>
//...
std::vector<Node*> Akmes; //Replace your array with this
//...
//Replace Akmes[count]=akmi; with:
Akmes.push_back(akmi);
// If you want to know the current number of elements:
Akmes.size(); //same like count, but managed by vector

To delete the Nodes correctly, you would need to iterate through the vector and delete every single pointer:

for (std::vector<Node*>::iterator iter = Akmes.begin(); iter != Akmes.end(); ++iter)
{
if ((*iter)) delete (*iter);
}

[iokon]

Thanks, it worked perfect!

[iokon]

Actually it didn't work perfect. I modified the code as you instructed me, but there is still a logical error that I can't figure out.The result of the last cout in main should be 4 according to logic. But still is NULL the same error that I stated at my first post!
Nevertheless, thank you very much for your answer!

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <vector>



class Edge;

class Node
{
public:
	int id;                //anagnwristiko korufhs
	bool visited;         //Xrhsimopoieitai sti dfs()
	Edge* adj;
	int distance;
	Node* previous;
	Node(int);
	~Node();
};

class Edge
{
public:
	Node* initial;
	Node* next;
	Edge* adj;
	int w;
	Edge(Node*, Node*, int);
	~Edge();
	bool Connects(Node* node1, Node* node2)
	{
		return((node1==this->initial&&node2==this->next)||(node1==this->next&&node2==this->initial));
	}
};

Node::Node(int a)
{
	id=a;
	visited=0;
	adj=NULL;
	previous=NULL;
	distance=INT_MAX;
}

Node::~Node()
{

}

Edge::Edge(Node* a, Node* b, int weight)
{
	initial=a;
	next=b;
	adj=NULL;
	w=weight;
}

Edge::~Edge()
{

}

class MyGraph
{
public:
	int Maxnodes;
	int count;
	int m;
	std::vector <Edge*> Akmes;
	std::vector <Node*> List;
	Node* remaining[];
	MyGraph(int);
	~MyGraph();
	int GetNumNodes();
	int GetNumEdges();
	Node* findnode(int);
	void InsertEdge(int,int,int);
};



MyGraph::MyGraph(int size)
{
	Maxnodes=size;
	for (int i=1;i<=Maxnodes;i++)
	{
		Node* temp=new Node(i);
		List.push_back(temp);
	}
	m=0;
	count=0;
}

MyGraph::~MyGraph()
{

}

int MyGraph::GetNumNodes()
{
	return Maxnodes;
}

int MyGraph::GetNumEdges()
{
	return count;
}


Node* MyGraph::findnode(int a)
{
	Node* x;
	for (int i=0;i<Maxnodes;i++)
	{
		if(List[i]->id==a)
			x=List[i];
	}
	return x;
}

void MyGraph::InsertEdge(int x, int y, int w)
{
	Node* a=findnode(x);
	Node* b=findnode(y);
	Edge* akmi=new Edge(a,b,w);
	Akmes.push_back(akmi);
	count++;
	Node* p;
	Node* q;
	Edge* l;
	p=List[x-1];
	l=p->adj;
	if (l==NULL)
		p->adj=akmi;
	else
	{
		while (l!=NULL)
			l=l->adj;
		l=akmi;
	}
	Edge* akmi2=new Edge(b,a,w);
	q=List[y-1];
	l=q->adj;
	if (l==NULL)
		q->adj=akmi2;
	else
	{
		while (l!=NULL)
			l=l->adj;
		l=akmi2;
	}
}


int main()
{
	class MyGraph* grafima;
	class MyGraph* objectPointer;
	objectPointer=new MyGraph(5);
	grafima=objectPointer;
	grafima->InsertEdge(1,2,3);
	std::cout << "ok";
	grafima->InsertEdge(2,3,4);
	std::cout << "ok";
	grafima->InsertEdge(3,5,6);
	std::cout << "ok";
	grafima->InsertEdge(1,4,7);
	std::cout << "ok";
	grafima->InsertEdge(4,5,4);
	std::cout << "ok";
	grafima->InsertEdge(2,4,2);
	std::cout << "ok";
	grafima->InsertEdge(4,3,5);
	std::cout << "ok";
	std::cout << grafima->List[0]->adj->adj->next->id;
}

[tdlr]

MyGraph::MyGraph(int size)
{
    Maxnodes=size;
    for (int i=1;i<=Maxnodes;i++)
    {
        Node* temp=new Node(i);
        List.push_back(temp);
    }
    m=0;
    count=0;
}

I think you should add temp->id = i; above List.push_back( ...).
But this is only one problem of some more issues. I'll check back later, if no one else found it then.

Edit:
There are just so many incomplete or incorrect assignments in your code. In main() you insert 2,3,4 and later 2,4,2.
The first time you are setting the adjacent edge of 1,2,3 to 2,3,4 and with the second call you're replacing the adjacent of 1,2,3 with 2,4,2.

Now the question is what do you want to achieve or what do you need to do? Because your overall design is really bad and incomplete. One cannot fix a special issue here because it's not carefully thought through.

There is a graph which consists of nodes. The structure of the graph depends on the edges. An edge connects two nodes and has an adjacent edge. Can there be more than one adjacent edges or not? This is important for the design of the classes.
I'd suggest you create a class graph which consists of a vector of nodes and a vector of edges. You don't need an ID for nodes because you can use the index within the vector as an ID. Also, you shouldn't fill the vector with lots of nodes at the very beginning, if you are not completely sure that you will ever need them. It's called dynamically allocated for a reason. Then you don't need to (and should not!) save a pointer to a node within an edge, but just save its index within the vector. This prevents pointers from becoming invalid after pushing back more than Nodes.capacity( ) nodes.
If you need to have more than one adjacent edge, save a vector of integers with the indizes of all adjacent edges in the edge class.
If you only need to have one adjacent edge, store a single int of the according index.

Things like next() are obsolete then, because Nodes[1] is automatically followed by Nodes[2]. Also check the size() of Nodes before accessing any element:

Node* nextNode;
if (currentNode < (Nodes.size()-1))
  nextNode = Nodes[currentNode+1];
else
  cout<<"There's no next node!"<<std::endl;

findNode isn't required anymore too, because either the index (aka ID) is smaller than size, then it's just there: Nodes[index] or it isn't smaller than size, then it isn't in Nodes.

That way you can remove many sources of bugs, thus simplifying your overall debugging process.

[iokon]

What I'm trying to do is the below schema
1-> <1,2> -> <1,4>
2-> <2,1> -> <2,3> -> <2,4>
3-> <3,2> -> <3,5> -> <3,4>
4-> <4,1> -> <4,5> -> <4,2> -> <4,3>
5-> <5,3> -> <5,4>

so that I can take advantage of the graph's properties, such as find shortest paths etc.
The first column is a vector containing all the nodes of my graph which is initialized when an object of type graph is created.
Every node has a link to an edge and every edge a link to the next edge in the adjacency list with the same initial node. Every time I call the InsertEdge(a,b, w) -- the w is the weight of edge <a,b> -- and inside the while loop, I find the last edge starting from node a (1st column) and in the end I add the new edge <a,b>. For example when I insert <2,4> I set the pointer <2,3>->adj=<2,4>. I think that my structure is logical enough and very efficient in order to manipulate my data and my assignments are according to the above schema without replacing anything.
The problem is that my code creates the below schema
1-> <1,2>->
2-> <2,1>->
3-> <3,2>->
4-> <4,1>->
5-> <5,3>->
which can be easily seen by calling e.g
std::cout<<List[0]->adj->next->id
the result is 2 as it should be. I can't figure out, why my code can't add the next edge, eg the edge <1,4> after the edge <1,2>.
I don't think that a vector of integers would meet the needs of my project.
Thanks for your attention!

[iokon]

I made some new modifications considering your ideas, and the code now works just perfect...below I post the code just for the story :)
thank you very much for your time!

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <vector>

using namespace std;

class Edge;

class Node
{
public:
	int id;
	bool visited;
	vector <Edge*>* adj;
	int distance;
	Node* previous;
	Node(int);
	~Node();
};

class Edge
{
public:
	Node* initial;
	Node* next;
	int w;
	Edge(Node*, Node*, int);
	~Edge();
	bool Connects(Node* node1, Node* node2)
	{
		return((node1==this->initial&&node2==this->next)||(node1==this->next&&node2==this->initial));
	}
};

Node::Node(int a)
{
	id=a;
	visited=0;
	adj=new vector<Edge*>;
	previous=NULL;
	distance=INT_MAX;
}

Node::~Node()
{

}

Edge::Edge(Node* a, Node* b, int weight)
{
	initial=a;
	next=b;
	w=weight;
}

Edge::~Edge()
{

}

class MyGraph
{
public:
	int Maxnodes;
	int m;
	vector <Edge*> Akmes;
	vector <Node*> List;
	MyGraph(int);
	~MyGraph();
	int GetNumNodes();
	int GetNumEdges();
	void InsertEdge(int,int,int);
};



MyGraph::MyGraph(int size)
{
	Maxnodes=size;
	for (int i=1;i<=Maxnodes;i++)
	{
		Node* temp=new Node(i);
		List.push_back(temp);
	}
	m=0;
}

MyGraph::~MyGraph()
{

}

int MyGraph::GetNumNodes()
{
	return Maxnodes;
}

int MyGraph::GetNumEdges()
{
	return Akmes.size();
}


void MyGraph::InsertEdge(int x, int y, int w)
{
	Node* a=List[x-1];
	Node* b=List[y-1];
	Edge* akmi=new Edge(a,b,w);
	Edge* akmi2=new Edge(b,a,w);
	Akmes.push_back(akmi);
	a->adj->push_back(akmi);
	b->adj->push_back(akmi2);
}

[tdlr]

But please don't forget to delete everything that was created with new.
Vectors do manage their objects, but they do not handle the objects pointed to by the pointers they manage.

I.e. you have to delete every associated object yourself.
In the MyGraph::~MyGra ph implementation you should add:

for (std::vector<Node*>::iterator i = List.begin(); i != List.end(); ++i)
	{
		if (*i)
			delete *i;
	}

Plus the same for Akmes.
And in Node::~Node you have to delete the adj vector pointer.

[iokon]

Thank you my friend for the lesson on vectors :)
I have already included the deletion of the objects in my code.
I hope to recompense you for your time in the future! :)