0

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;
      }
      
           
};

class Adjacency_list
{
      private:
      int num_nodes;
      Node* head;  
      
      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;         
                                           
                           }
                           /*for(Node* t=head;t!=NULL;t=t->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_node=head;
           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()
{
    Adjacency_list a;
    a.makeList();
    a.display();
    

system("pause");    
return 0;    
}

Any help is appreciated !!
Thanks !!

2
Contributors
1
Reply
2
Views
7 Years
Discussion Span
Last Post by daviddoria
0

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

http://en.wikipedia.org/wiki/Adjacency_list

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.