Friday, 31 March 2017

Graph Implementation using C++ STL

The most common and basic reprsentation of graphs are Adjacency List (using Linked List) and Adjacency matrix. But the question is that why to use C++ STL to implement graph when we can easily represent the graph using adjacency matrix (In which arrays are used) or Adjacency list (using Linked List). So here are the some main reasons why to prefer C++ STL to implement graph.

1.   Correct: First of all you don't need to bug them because a queue made by using C++ STL can
      take care of size and other thing itself. You don't need to update indexing while popping out and
      pushing elements to the graph.

2.  Fast: They are just about as fast as can be for the general case.
3.  Maintainable: You and your peers both can easily understand what is happening. In most of cases
     use of Standard Library is self-documenting. So why to reinvent the wheel.
4.  Why to spend time reinventing the wheel and pushing the deadline. Why to have poor runtime and
     poor memory performance by writing C style code.

In the program given below to implement graph using C++ STL, we used two STL containers to represent graph:
  • Vector:  A sequence container. we are using it to store adjacency lists of all vertices.
  • Pair:     A simple container to store pair of all elements. To store the the edge e is connecting vertex u to vertex v.

Declaration of vector:   std::vector < pair<int,int> > adj_list;
Declaration of iterartor to the vector:    std::vector <pair<int,int>>::iterator it;

PROGRAM:


#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define MAX 100
#define visited 1
#define unvisited 0
class graph_stl
{
     private:
     std::vector< pair<int,int> > adj_list;
     std::vector< pair<int,int> >::iterator it;
     int n;
  public:
     void get_data();
     void traversal();
};
void graph_stl::get_data()
{
   printf("\nEnter the total number of vertices: \n");
   scanf("%d",&n);
   int max_edge=n*(n-1)/2;
   int source,destination;
   for(int i=0;i<max_edge;i++)
   {
         printf("\nEnter the source and destination of edge %d & (0,0) to exit: ",i+1);
         scanf("%d%d",&source,&destination);
         if(source==0 && destination==0)
         {
               break;
         }
         else
         {
               adj_list.push_back(make_pair(source,destination));
         }
   }
}
void graph_stl::traversal()
{
      printf("\n Vertex u connected with  vertex v:\n");
   for(it=adj_list.begin();it!=adj_list.end();it++)
   {
            printf("\t%d\t->->->\t\t%d",it->first,it->second);
            printf("\n");
   }

}
int main()
{
    graph_stl graph;
    graph.get_data();
    graph.traversal();
    return 0;
}

OUTPUT


See also: Implementation of BFS (Breadth First Search) to traverse graph
See also: Implementation of DFS (Depth First Search) to traverse graph 


EmoticonEmoticon