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

#ifndef _GRAPH_HPP_

#define _GRAPH_HPP_

#include

#include

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;

}

}

### Like this:

Like Loading...

*Related*