## Sunday, March 25, 2012

### 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);

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

#endif

```
graph.pp:

```#include "graph.hpp"

using namespace std;

Graph::~Graph()
{
// TODO:
}

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

{
//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];
}

{
if (!g) return false;

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

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

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

// g0 --- g1
//g1 --- g2
// g2 --- g3
// g3 --- g0
// g0 -- g2

list<Graph*>::iterator it;

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