Solved

Non-weighted and non-directed graph

Posted on 2005-04-07
386 Views
Hi,
I have to implement a simple class for a non-weighted and non-directed graph. Which data structure should I use, taking into account that I have to implement a function that would return the shortest path from one node to another? That is to say, the least possible number of edges between one vertex from another.
0
Question by:zwinmin

LVL 48

Expert Comment

http://msdn.microsoft.com/vcsharp/default.aspx?pull=/library/en-us/dv_vstechart/html/datastructures_guide5.asp

This article contains good description of graphs and data structures used to keep them in memory, and Dijkstra's algorithm to find shortest path between graph nodes.
Sample code is in C# (this language is easy understandable to C++ developer). You can use only article text or sample code if you are familiar with C#.
0

Author Comment

The article suggested using adjacency list or adjacency matrix to implement the graph. But the algorithm described there is to find shortest path for weighted path, while i am doing it for non-weighted path. So, how should I find the shortest path for non-weighted graph using adjacency matrix? Thanks.
0

LVL 48

Accepted Solution

For non-weighted graph it is not necessary to keep edge weight in the Node instance of adjacency list. Generally, it is beter to keep edge weight and set it always to 1 for non-weighted graph. In this case the same algorithm will work both for weighted and non-weighted graphs.
0

LVL 39

Assisted Solution

I tried it using my own structures and algorithm:

#include<iostream>
#include <map>
#include <list>
using namespace std;

class Vertex
{
int id;
public:
Vertex() : id(0) {}
Vertex(int i) : id(i) {}
bool operator < (const Vertex& vertex) const
{
return id < vertex.id;
}
bool operator == (const Vertex& vertex) const
{
return id == vertex.id;
}
bool operator == (int i) const
{
return id == i;
}
int getId() const { return id; }
};

class Edge
{
static int   nextId;
int id;
Vertex v1;
Vertex v2;
public:

Edge(int i1, int i2)
: id(++Edge::nextId), v1((i1 < i2)? i1:i2), v2((i1 <i2)? i2 : i1) {}
Edge(const Vertex& ve1, const Vertex& ve2)
: id(++Edge::nextId)
{
v1 = (ve1 < ve2)? ve1 : ve2;
v2 = (ve1 < ve2)? ve2 : ve1;
}

bool operator < (const Edge& edge) const
{
return v1 < edge.v1;
}

const Vertex& getV1() const { return v1; }
const Vertex& getV2() const { return v2; }
};

class Distance
{
Vertex v;
int dist;
public:
Distance() : v(0), dist(0) {}
Distance(const Vertex& ve1, int d) : v(ve1), dist(d) {}
Vertex& getV() { return v; }
};

class SimpleGraph
{
list<Edge> edges;
public:
{
edges.push_back(Edge(n1, n2));
}
int getNeighbors(const Vertex& v, list<Vertex>& neighbors)
{
sort();
bool found = false;
for (list<Edge>::iterator it = edges.begin(); it != edges.end(); ++it)
{
if (it->getV1() == v)
{
found = true;
neighbors.push_back(it->getV2());
}
else if (found)
break;
}
return neighbors.size();
}

int getShortestPath(int n1, int n2, list<Vertex>& path)
{
int dist = 1;
list<Vertex> vl1;
list<Vertex> vl2;
list<Vertex>& vc = vl1;
list<Vertex>& vn = vl2;
map<Vertex, Distance> m;

Vertex v1 = n1;
Vertex v2 = n2;
m[v1] = Distance(v1, 0);
vc.push_back(v1);
bool found = v1 == v2;

while (!found && dist <= edges.size())
{
for (list<Vertex>::iterator it = vc.begin(); it != vc.end(); ++it)
{
v1 = *it;
list<Vertex> neighbors;
getNeighbors(v1, neighbors);
for (list<Vertex>::iterator it1 = neighbors.begin(); it1 != neighbors.end(); ++it1)
{
v2 = *it1;
cout << dist << ":" << v1.getId() << " -> " << v2.getId() << endl;
if (m.find(v2) == m.end())
{
m[v2] = Distance(*it, dist);
vn.push_back(v2);
if (*it1 == n2)
{
found = true;
break;
}
}

}
}
list<Vertex>& vs = vc;
vc = vn;
vn = vs;
vn.clear();
dist++;
}

path.clear();
if (found)
{
v1 = Vertex(n1);
v2 = Vertex(n2);
Vertex v = v2;
path.push_front(v2);
while(!(v == v1))
{
Distance d = m[v];
v = d.getV();
path.push_front(v);
}
}
return dist;
}

protected:
void sort()
{
edges.sort();
}

};

int   Edge::nextId      = 0;

int  main()
{
SimpleGraph g;

list<Vertex> route;

if (g.getShortestPath(1, 13, route) > 0)
{
for (list<Vertex>::iterator it = route.begin(); it != route.end(); ++it)
{
cout << it->getId() << " -> ";
}
cout << endl;
}

return 0;
}

Regards, Alex
0

Featured Post

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.