Tushar
Tushar

Reputation: 97

Map reprsentation of Graph

#include <iostream>
#include<map>
#include<vector>
using namespace std;
static int index = 0;
template <typename T>
class graph
{
    private:

            typename  map< T, int > :: iterator iter;
            map <T,int> vtxMap;
            int numVertices;
            int numedges;

    public:
            void addEdge(graph<T>&, const T& ,const T&);
            void show(graph<T>&);


};

int main()
{
    graph <char> g;

    g.addEdge(g,'A','B');     // add edge AB
    g.addEdge(g,'A','C');
    g.addEdge(g,'B','D');
    g.addEdge(g,'C','D');
    g.addEdge(g,'B','C');
    g.show(g);

    return 0;
}

template <typename T>
void graph<T> :: addEdge ( graph<T>& g , const T& v1 , const T& v2)
{
    pair<map<char, int>::iterator, bool> ret;
      ret = g.vtxMap.insert( pair<char,int>('v1',index));
      if(ret.second )         // if() condition is true , means node
      {                       // gets inserted successfully. Now 
          index++;            // increase "index"to assign new unique
      }                       // value to new node.

      ret = g.vtxMap.insert( std::pair<char,int>('v2',index));
      if(ret.second)
      {
        index++;
      }

}
template<typename T>
 void graph<T> :: show( graph<T>& g)
    {
       for( g.iter = g.vtxMap.begin(); g.iter != g.vtxMap.end(); g.iter++)
         {
             cout<< (*(g.iter)).first <<" - >" << (*(g.iter)).second <<endl;
         }
    }

Output :

1-> 0
2-> 1

Above program is not a complete representation of Graph.
I stumbled at initial stage so not posting other functions ( like removeEdge() , inDegree() , outDegree() , getNeighbor() etc... )
By seeing output, it seems that program executing only first input

g.addEdge(g,'A','B)     

I am expecting output as

A -> 0
B -> 1
C -> 2
D -> 3

Means whenever there will be a new node, it should be inserted in vtxMap with a unique value ( i.e index ). If node is already present, it should not be inserted ( as map does not accept duplicates )
Where I am wrong ??

Upvotes: 1

Views: 3825

Answers (1)

AchmadJP
AchmadJP

Reputation: 903

When inserting the edge, use v1 instead of 'v1'

 template <typename T>
    void graph<T> :: addEdge ( graph<T>& g , const T& v1 , const T& v2)
    {
        pair<map<char, int>::iterator, bool> ret;
          ret = g.vtxMap.insert( pair<char,int>(v1,index));
          if(ret.second )         // if() condition is true , means node
          {                       // gets inserted successfully. Now 
              index++;            // increase "index"to assign new unique
          }                       // value to new node.

      ret = g.vtxMap.insert( std::pair<char,int>(v2,index));
      if(ret.second)
      {
        index++;
      }

}

Output :

enter image description here

Upvotes: 1

Related Questions