As the title says it, I have made a program to implement adjacency list representation of graph. I wish to use it in implementing various graph algorithms like DFS, BFS, Dijkstra, etc. The program works fine for the test cases I put in it. But I am sure that there must be way more elegant, efficient and easier ways to do it. It'll be great if you could point out those. For example if I could use STL in this to make it shorter and easier, or if I should have not made the classes in the way I have, etc.

By the way, I have not freed memory on purpose, because I thought that would be not necessary for my goal. (which is to implement graph algorithms)

``````#include <iostream>
#include <cstdlib>

using namespace std;

class Node
{
public:
Node* next_node;//will be null if there is no "next node" or if the node is being used as an edge node
Node* next_edge;//will be null if no further edges are there
int node_name;

Node()
{
next_node=NULL;
next_edge=NULL;
node_name=-1;//means the node is empty
}
Node(int i)
{
next_node=NULL;
next_edge=NULL;
node_name=i;//name of node is the integer in i
}

bool isEmpty()
{
return node_name==-1;
}

};

{
private:
int num_nodes;

public:
void makeList()
{
cout<<"\nEnter the number of nodes: ";
cin>>num_nodes;

Node* temp_node=NULL;//temporary pointer for moving over main nodes of adjacency list
Node* temp_edge=NULL;//temporary pointer for moving over edge nodes of a particular main node
for(int i=0;i<num_nodes;i++)
{
if(i==0)
{
head=new Node(i);//make first node
temp_node=head; //initialize temp pointer to point to first node

//code to add edges to 0th node
temp_edge=temp_node;
cout<<"\nEnter the nodes adjacent to node 0 (enter -1 to stop): ";
for(;;)
{
int c;
cin>>c;
if(c==-1)
break;

temp_edge->next_edge=new Node(c);
//cout<<endl<<c<<endl;
temp_edge=temp_edge->next_edge;

}
{
cout<<t->node_name;
if(t->next_edge!=NULL)
cout<<"--->";
}*/
//temp_node=temp_node->next_node;

}
else
{
temp_node->next_node=new Node(i);//make next node

temp_node=temp_node->next_node;//move temporary to next node (to ith node from (i-1)th node)
//otherwise following code will overwrite edges of (i-1)th node

//code to add edges to ith node
temp_edge=temp_node;
cout<<"\nEnter the nodes adjacent to node "<<i<<" (enter -1 to stop): ";
for(;;)
{
int c;
cin>>c;
if(c==-1)
break;

temp_edge->next_edge=new Node(c);
temp_edge=temp_edge->next_edge;

}

/*for(Node* t=temp_node;t!=NULL;t=t->next_edge)
{
cout<<t->node_name;
if(t->next_edge!=NULL)
cout<<"--->";
}*/

}

}
}
void display()
{
Node* temp_edge=NULL;
for(;temp_node!=NULL;)
{
temp_edge=temp_node;
//cout<<temp_node->node_name;

//print all edges for this node
for(;temp_edge!=NULL; temp_edge=temp_edge->next_edge)
{
cout<<temp_edge->node_name;
if(temp_edge->next_edge!=NULL)
cout<<"--->";
}

temp_node=temp_node->next_node;//move to next main node
cout<<endl;

}
cout<<endl;

}

};

int main()
{
a.makeList();
a.display();

system("pause");
return 0;
}``````

Any help is appreciated !!
Thanks !!

An adjacency list should simply be a std::vector<std::pair>, right?

You look like you have created more of a graph traversal structure here. Unless you are doing this simply as an exercise, there are some graph libraries out there already. I use vtkGraph (I put some examples here: http://www.vtk.org/Wiki/VTK/Examples#Graphs

It uses Boost Graph Library (BGL) under the hood, but these VTK wrappers make it much much easier to use.

Another suggestion would be to separate the actual input (cin) from the makeList function. This will allow you to populate the list either manually in the code, from the user (as you're doing now) or from a file with the maximum amount of code reuse.

Dave