Undirected graph implementation using adjacency lists

Question

iokon 0 Newbie Poster

13 Years Ago

Hi to all!
In the following code I am trying to implement a non-directed graph using adjacency lists. Even though there are no compilation errors, I don't get any results. When I am debugging the code it seems that there is a problem when I try to insert a second edge with the first node to be the node 1. More particular, the while-loop in the InsertEdge function seems not to end, a fact that is not logical and I can't figure out why is this happenning.
I would appreciate any help!Thanks in advance!

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

using namespace std;

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 stored in the adjacency list  
	int w;
	Edge(Node*, Node*, int);
	~Edge();
};

Node::Node(int a)
{
	id=a;
	visited=0;
	adj=NULL;       //used to point the first edge inserted in the adjacency list
                        //after the 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
{
protected:
	Node* List[];           //stores all the nodes of the graph. Every node of the 
                                //array points (List[]->adj) to a queue that contains 
                                //all the edges starting from the same node.
public:
	int Maxnodes;
	int count;
	Edge* Akmes[];          //stores all the edges of the graph
	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);
	}
	count=0;
}

MyGraph::~MyGraph()
{

}


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

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[count]=akmi;
	count++;
	Node* p;
	Node* q;
	Edge* l;
	Edge* m;
	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);  //I also insert edge <b,a> as my graph is 
                                      // undirected
	q=List[y-1];
	m=q->adj;
	if (m==NULL)
		q->adj=akmi2;
	else
	{
		while (m!=NULL)
			m=m->adj;
		m=akmi2;
	}
}



int main()
{
	MyGraph* grafima=new MyGraph(5);
	grafima->InsertEdge(1,2,3);
	grafima->InsertEdge(2,3,4);
	grafima->InsertEdge(3,5,6);
	grafima->InsertEdge(1,4,7);
}

c++

1 Contributor
1 Reply
2K Views
5 Days Discussion Span
Latest Post 13 Years Ago Latest Post by iokon

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

iokon 0 Newbie Poster · Answer 1 · 2011-01-22T05:47:41+00:00

Just to give a reply to my question...the right code is below

#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;
	Node* remaining[];
	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);
}