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
#include
#include

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 m_cost;
list 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::iterator it;
list 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[" <GetId() << "], cost="
<< g[i].GetCostTo(*it) << endl;
}
}

Advertisements

About The Seeker

Silicon Forest
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s