Creating a graph using STL's in C++

Monday, February 17, 2014 , , 0 Comments

Below is a implementation of Graph Data Structure in C++ as Adjacency List.

I have used STL vector for representation of vertices and STL pair for denoting edge and destination vertex.



struct vertex{
 typedef pair ve;
 vector adj; //cost of edge, destination vertex
 string name;
 vertex(string s)
 {
  name=s;
 }
};

class graph
{
 public:
  typedef map vmap;
  vmap work;
  void addvertex(const string&);
  void addedge(const string& from, const string& to, double cost);
};

void graph::addvertex(const string &name)
{
 vmap::iterator itr=work.begin();
 itr=work.find(name);
 if(itr==work.end())
 {
  vertex *v;
  v= new vertex(name);
  work[name]=v;
  return;
 }
  cout<<"\nVertex already exists!";
}

void graph::addedge(const string& from, const string& to, double cost)
{
 vertex *f=(work.find(from)->second);
 vertex *t=(work.find(to)->second);
 pair edge = make_pair(cost,t);
 f->adj.push_back(edge);
}

0 comments: