Undirected Graph

The following small program illustrate how to implement a undirected graph with costs to neighbor nodes.

#ifndef _GRAPH_HPP_
#define _GRAPH_HPP_

#include <iostream>
#include <map>
#include <list>

using namespace std;

/*
 * Undirected graph class
 */
class Graph {
public:
 Graph(unsigned int id=0) { m_id = id; m_Ecount = 0; }
 virtual ~Graph();
 void SetId(unsigned int id) { m_id = id; }
 bool Match(Graph& g);
 bool AddAdjacent(Graph* g, int cost=0);
 bool AddAdjacentOne(Graph *g);
 list GetAdjacents() { return m_Adjacents; }
 
 int GetVCount() { return m_Adjacents.size(); }
 int GetECount() { return m_Ecount; }
 unsigned int GetId() { return m_id; }
 void SetCostTo(Graph *g, int cost);
 int GetCostTo(Graph* g);
 
 private:
 unsigned int m_id;
 int m_Ecount;
 map<Graph*,int> m_cost;
 list<Graph*> m_Adjacents;
};


#endif

graph.pp:

#include "graph.hpp"

using namespace std;

Graph::~Graph()
{
 // TODO:
 m_Adjacents.clear();
}


bool Graph::Match(Graph& g)
{
 cout << "this=" << this << endl;
 cout << "&g =" << &g << endl;
 if ((this == &g) || (g.GetId() == this->GetId()) &&
  (g.GetECount() == this->GetECount()) &&
  (g.GetVCount() == this->GetVCount()) )
  return true;
 return false;
}

bool Graph::AddAdjacentOne(Graph *g)
{
 m_Adjacents.push_back(g);
 //TODO: we need to tell g to add also edge to this object
 m_Ecount++;
 return true;
}


void Graph::SetCostTo(Graph *g, int cost)
{
 if (g == NULL)
  return;
 // Use hash-table to set the cost from this node to g
 m_cost[g] = cost;
}

int Graph::GetCostTo(Graph *g)
{
 if (g == NULL)
  return -1;
 // use hash-table to get the cost from this node to g
 return m_cost[g];
}

bool Graph::AddAdjacent(Graph* g, int cost)
{
 if (!g) return false;

 if (Match(*g))
 {
  cout << "ERROR: Tried to add itself" << endl;
  return false;
 }
 else {
  AddAdjacentOne(g);
  // tell other node to set its adjacent to this node too
  g->AddAdjacentOne(this);
  // add cost from this object to g
  g->SetCostTo(this, cost);
  SetCostTo(g, cost);
  return true;
 }
}



int main()
{
 Graph g[10];
 int i;
 int numOfVertices = 4;

 for(i=0; i<numOfVertices; i++)
  g[i].SetId(i);

 // g0 --- g1
 g[0].AddAdjacent(&g[1]);
 //g1 --- g2
 g[1].AddAdjacent(&g[2]);
 // g2 --- g3
 g[2].AddAdjacent(&g[3]);
 // g3 --- g0
 g[3].AddAdjacent(&g[0]);
 // g0 -- g2
 g[0].AddAdjacent(&g[2], 5);

 list<Graph*>::iterator it;
 list<Graph*> adjacents;

 for(i=0; i<numOfVertices; i++)
 {
  cout << "NODE g[" << i << "]" << endl;
  cout << "\tNumber of Edges in G[" << i << "] = " << g[i].GetECount() << endl;

  adjacents = g[i].GetAdjacents();
  cout << "\tNeighbors:" << endl;
  for ( it=adjacents.begin() ; it != adjacents.end(); it++ )
   cout << "\t\tNode=" << *it << ", g[" << (*it)->GetId() << "], cost="
     << g[i].GetCostTo(*it) << endl;
 }
}