Skip to content

Instantly share code, notes, and snippets.

@abhishekmunie

abhishekmunie/main.cpp

Created November 9, 2012 04:54
Show Gist options
  • Save abhishekmunie/4043768 to your computer and use it in GitHub Desktop.
Save abhishekmunie/4043768 to your computer and use it in GitHub Desktop.
Download ZIP
Finding minimum cost to visit all vertices in a graph and returning back.
Raw
main.cpp
//
// main.cpp
// FloydGreedyTravel
//
// The program tries to find a path to visit all vertices of Graph.
// The rules are:
// * Nodes can be visited more than once.
// * Try to find shortest path
//
// First it find All-Pairs Shortest Paths using The Floyd-Warshall algorithm.
// Then taking a Greedy approach it travels the whole graph.
// Finally it checks if there exists a shorter path using Backtracking.
//
// In most cases the first result from geedy approach will be shortest.
// If not, it will reduce the backtracking tree by setting a lower limit.
//
// Created by Abhishek Munie on 08/11/12.
// (cc) 2012 Abhishek Munie.
//
#include <iostream>
#include <limits.h>
using namespace std;
#define M INT_MAX
template<const unsigned int n>
class Path {
int unvisited;
class Vertex {
public:
int val;
int isIntermediate;
Vertex *next;
Vertex(int val, int isIntermediate):val(val), isIntermediate(isIntermediate) {
next = NULL;
}
Vertex(int val, int isIntermediate, Vertex *next):val(val), isIntermediate(isIntermediate), next(next) {
next = NULL;
}
Vertex(const Vertex *v) {
val = v->val;
isIntermediate = v->isIntermediate;
next = NULL;
}
};
protected:
Vertex *start;
Vertex *end;
const char *nodes;
const int *shortestDist;
const int *parents;
size_t len;
size_t rlen;
public:
int visited[n];
const int startVertex;
Path(char *nodes, int *shortestDist, int *parents, int start):nodes(nodes), shortestDist(shortestDist), parents(parents), startVertex(start) {
this->start = end = new Vertex(start, 0);
len = 0;
rlen = 0;
for(int i = 0; i < n; i++) {
visited[i] = 0;
}
visited[start] = 1;
unvisited = n - 1;
}
Path(const Path<n> &p):nodes(p.nodes), shortestDist(p.shortestDist), parents(p.parents), startVertex(p.startVertex), unvisited(p.unvisited), len(p.len), rlen(p.rlen) {
for(int i = 0; i < n; i++) {
visited[i] = p.visited[i];
}
Vertex **v = &start;
Vertex *vp = p.start;
while(vp) {
end = (*v) = new Vertex(vp);
vp = vp->next;
v = &((*v)->next);
}
}
~Path() {
Vertex *v = start;
Vertex *next;
while (v) {
next = v->next;
delete v;
v = next;
}
}
private:
void addPath(int s, int d) {
int i = s*n + d;
if(parents[i] != s) {
addPath(s, parents[i]);
add(parents[i]);
}
}
int add(int vertex, int isIntermediate) {
if(!isIntermediate) {
visited[vertex] = 1;
unvisited--;
}
addPath(end->val, vertex);
len += shortestDist[end->val*n + vertex];
end->next = new Vertex(vertex, isIntermediate);
end = end->next;
return unvisited;
}
public:
/**
* Adds a vertex and the intemediate path to it to the Path.
*
* vertex - index of vertex to be added;
*
* returns number of unvisited vertices after adding this vertex;
*/
int add(int vertex) {
return add(vertex, visited[vertex]);
}
/**
* Closes th path by adding intermediate path from end vertex to start vertex.
*/
void close() {
rlen = shortestDist[end->val*n + start->val];
add(start->val, 1);
}
/**
* Returns the unvisited vertex closest to end of current path.
*/
int getNextClosest() {
int minp = -1;
int min = M;
for(int i = 0; i < n; i++) {
if(!visited[i] && (shortestDist[end->val*n + i] < min)) {
minp = i;
min = shortestDist[end->val*n + i];
}
}
return minp;
}
/*
* Returns the length of path traveled to while visiting all nodes.
*/
size_t visitLength() {
return len - rlen;
}
/*
* Returns the length of path traveled to while returning to start.
*/
size_t returnLength() {
return rlen;
}
/*
* Returns the length of path traveled.
*/
size_t length() {
return len;
}
/**
* Prints the path.
*
* => visited_node
* -> intermediate_node
*/
void print() {
Vertex *v = start;
if (v) {
cout<<nodes[v->val];
v = v->next;
}
while (v) {
cout<<((v->isIntermediate) ?" -> " :" => ")<<nodes[v->val];
v = v->next;
}
}
};
template<const unsigned int n>
class Graph {
int parents[n][n];
size_t minGreedyFloydDist;
size_t minPathLength;
protected:
char nodes[n];
int adjMatrix[n][n];
int shortestDist[n][n];
public:
Graph(char nodes[n], int adjMatrix[n][n]) {
int i, j;
for(i = 0; i < n; i++) {
this->nodes[i] = nodes[i];
for(j = 0; j < n; j++) {
this->adjMatrix[i][j] = adjMatrix[i][j];
this->shortestDist[i][j] = adjMatrix[i][j];
if (adjMatrix[i][j] != 0 && adjMatrix[i][j] != M) {
this->parents[i][j] = i;
} else {
this->parents[i][j] = -1;
}
}
}
}
private:
int isMin(int i, int j, int k) {
if((shortestDist[i][k] == M) || (shortestDist[k][j] == M)) {
return 0;
} else if((shortestDist[i][k] + shortestDist[k][j]) < shortestDist[i][j]) {
return 1;
}
return 0;
}
void calcFloydShortestPath() {
register int i, j, k;
for(k = 0; k < n; k++) {
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(isMin(i, j, k)) {
shortestDist[i][j] = shortestDist[i][k] + shortestDist[k][j];
parents[i][j] = parents[k][j];
}
}
}
}
}
/**
* returns last visited node
*/
int travelGreedyFloyd(Path<n> &p, int s) {
int v, l = s;
if((v = p.getNextClosest()) != -1) {
p.add(v);
l = travelGreedyFloyd(p, v);
}
return l;
}
void printShorterPaths(Path<n> p, int s) {
p.visited[s] = 1;
for(int i = 0; i < n; i++) {
if(!p.visited[i] && (shortestDist[s][i] != M) && ((p.visitLength() + shortestDist[s][i] + shortestDist[i][p.startVertex]) < minPathLength)) {
Path<n> np = p;
if(np.add(i)) {
printShorterPaths(np, i);
} else {
np.close();
minPathLength = np.length();
cout<<"Path("<<np.length()<<"): ";
np.print();
cout<<endl;
}
}
}
}
public:
/**
* Travel path to visit all nodes and return back.
*
* start - starting node
*
* => visited_node
* -> intermediate_node
*/
void travelGreedyFloyd(char start) {
int i, s = 0;
minGreedyFloydDist = 0;
for(i = 0; i < n; i++) {
if(nodes[i] == start) {
s = i;
break;
}
}
calcFloydShortestPath();
Path<n> path(nodes, (int *)shortestDist, (int *)parents, s);
travelGreedyFloyd(path, s);
path.close();
cout<<"Path: ";
path.print();
minGreedyFloydDist = path.length();
cout<<"\nDistance Travelled: "<<minGreedyFloydDist;
}
void printShorterPaths(char start) {
int i, s = 0;
minPathLength = minGreedyFloydDist;
for(i = 0; i < n; i++) {
if(nodes[i] == start) {
s = i;
}
}
printShorterPaths(Path<n>(nodes, (int *)shortestDist, (int *)parents, s), s);
}
};
int randomNo(int lower, int range) {
int r = lower+int(range*(rand()/(RAND_MAX + 1.0)));
if(r <= 0 || r > 99) {
r = M;
}
return r;
}
void printMatrix(int *Matrix, int n) {
char CH = 'A';
int index;
cout<<"{";
for (int i = 0; i < n; i++) {
if(i != 0)
cout<<" ";
cout<<"{ ";
for (int j = 0; j < n; j++) {
index = i*n + j;
if(Matrix[index] != M) {
cout<<Matrix[index];
} else {
cout<<"∞";
}
if(Matrix[index] < 10 || Matrix[index] == M) {
cout<<" ";
}
if(j != n-1)
cout<<", ";
}
if(i != n-1)
cout<<"}, ";
else
cout<<"}};";
cout<<"// "<<CH++<<"\n";
}
}
int main(int argc, char const *argv[]) {
char nodes26[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
cout<<"GRAPH 1:\n";
int adjMatrix7[][7] = {{ 0 , 3 , 6 , M , M , M , M }, // A
{ 3 , 0 , 2 , 4 , M , M , M }, // B
{ 6 , 2 , 0 , 1 , 4 , 2 , M }, // C
{ M , 4 , 1 , 0 , 2 , M , 4 }, // D
{ M , M , 4 , 2 , 0 , 2 , 1 }, // E
{ M , M , 2 , M , 2 , 0 , 1 }, // F
{ M , M , M , 4 , 1 , 1 , 0 }};// G
Graph<7> g1(nodes26, adjMatrix7);
g1.travelGreedyFloyd('A');
cout<<"\nShorter Paths:\n";
g1.printShorterPaths('A');
cout<<"\n\nGRAPH 2:\n";
int adjMatrix26[][26] = {{ 0 , 6 , 7 , 3 , 9 , M , 6 , 9 , 3 , 2 , 12, 15, 18, 6 , 43, 4 , 12, 64, 7 , 4 , 8 , M , M , 7 , 3 , 23}, // A
{ 6 , 0 , 76, 8 , 32, 8 , 43, 95, 22, 5 , M , M , M , M , M , 5 , 8 , M , 32, 9 , 99, M , M , 32, M , 54}, // B
{ 7 , 76, 0 , 8 , 2 , 7 , 54, M , M , 95, 32, 79, 32, 55, 76, 54, M , M , M , M , 2 , 54, 32, 12, 54, 8 }, // C
{ 3 , 8 , 8 , 0 , 5 , 12, 15, 18, 76, 54, 65, 77, 32, 43, M , M , 64, 6 , M , 4 , 2 , 1 , 2 , 4 , M , M }, // D
{ 9 , 32, 2 , 5 , 0 , M , 7 , M , M , M , M , M , M , M , M , M , M , M , M , 64, 76, M , M , M , M , M }, // E
{ M , 8 , 7 , 12, M , 0 , M , M , M , M , 64, 8 , 7 , 3 , 4 , 2 , 4 , M , M , M , M , M , M , M , M , 5 }, // F
{ 6 , 43, 54, 15, 7 , M , 0 , 3 , M , M , M , M , M , M , M , 2 , 3 , M , 44, 2 , 4 , 3 , M , 3 , 5 , 2 }, // G
{ 9 , 95, M , 18, M , M , 3 , 0 , 5 , 3 , 2 , 5 , 3 , 2 , 4 , 2 , 5 , 2 , 4 , 6 , 2 , 4 , 2 , 4 , M , M }, // H
{ 3 , 22, M , 76, M , M , M , 5 , 0 , M , M , M , M , M , 4 , 2 , 3 , 2 , 4 , 2 , 4 , 1 , 3 , 5 , 3 , 2 }, // I
{ 2 , 5 , 95, 54, M , M , M , 3 , M , 0 , 4 , 32, 43, 33, 3 , 3 , 2 , M , 45, 3 , 2 , 4 , 3 , 2 , 42, 4 }, // J
{ 12, M , 32, 65, M , 64, M , 2 , M , 4 , 0 , 55, 32, 8 , 43, 95, 22, 5 , M , M , M , M , M , 5 , 8 , M }, // K
{ 15, M , 79, 77, M , 8 , M , 5 , M , 32, 55, 0 , 32, 9 , 99, M , M , 32, M , 54, 8 , 2 , 7 , 54, M , M }, // L
{ 18, M , 32, 32, M , 7 , M , 3 , M , 43, 32, 32, 0 , 95, 32, 79, 32, 55, 76, 54, M , M , M , M , 2 , 54}, // M
{ 6 , M , 55, 43, M , 3 , M , 2 , M , 33, 8 , 9 , 95, 0 , 32, 12, 54, 8 , 5 , 12, 15, 18, 76, 54, 65, 77}, // N
{ 43, M , 76, M , M , 4 , M , 4 , 4 , 3 , 43, 99, 32, 32, 0 , 32, 43, M , M , 64, 6 , M , 4 , 2 , 1 , 2 }, // O
{ 4 , 5 , 54, M , M , 2 , 2 , 2 , 2 , 3 , 95, M , 79, 12, 32, 0 , 4 , M , M , M , 7 , M , M , M , 32, 8 }, // P
{ 12, 8 , M , 64, M , 4 , 3 , 5 , 3 , 2 , 22, M , 32, 54, 43, 4 , 0 , 43, 95, 22, 5 , M , M , M , M , M }, // Q
{ 64, M , M , 6 , M , M , M , 2 , 2 , M , 5 , 32, 55, 8 , M , M , 43, 0 , 5 , 8 , M , 32, 9 , 99, M , M }, // R
{ 7 , 32, M , M , M , M , 44, 4 , 4 , 45, M , M , 76, 5 , M , M , 95, 5 , 0 , 32, M , 54, 8 , 2 , 7 , 54}, // S
{ 4 , 9 , M , 4 , 64, M , 2 , 6 , 2 , 3 , M , 54, 54, 12, 64, M , 22, 8 , 32, 0 , M , M , 95, 32, 79, 32}, // T
{ 8 , 99, 2 , 2 , 76, M , 4 , 2 , 4 , 2 , M , 8 , M , 15, 6 , 7 , 5 , M , M , M , 0 , 55, 76, 54, M , M }, // U
{ M , M , 54, 1 , M , M , 3 , 4 , 1 , 4 , M , 2 , M , 18, M , M , M , 32, 54, M , 55, 0 , M , M , 2 , 54}, // V
{ M , M , 32, 2 , M , M , M , 2 , 3 , 3 , M , 7 , M , 76, 4 , M , M , 9 , 8 , 95, 76, M , 0 , 32, 12, 54}, // W
{ 7 , 32, 12, 4 , M , M , 3 , 4 , 5 , 2 , 5 , 54, M , 54, 2 , M , M , 99, 2 , 32, 54, M , 32, 0 , 8 , 5 }, // X
{ 3 , M , 54, M , M , M , 5 , M , 3 , 42, 8 , M , 2 , 65, 1 , 32, M , M , 7 , 79, M , 2 , 12, 8 , 0 , 12}, // Y
{ 23, 54, 8 , M , M , 5 , 2 , M , 2 , 4 , M , M , 54, 77, 2 , 8 , M , M , 54, 32, M , 54, 54, 5 , 12, 0 }};// Z
Graph<26> g2(nodes26, adjMatrix26);
g2.travelGreedyFloyd('A');
//uncommented lines for testing larger graph
//cout<<"\nShorter Paths:\n";
//g2.printShorterPaths('A');
cout<<"\n\nRANDOM GRAPH:\n";
//change commented lines for testing larger graph
const int n = 12;
//const int n = 26;
int Mat[n][n];
for (int i = 0; i < n; i++) {
Mat[i][i] = 0;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Mat[i][j] = Mat[j][i] = randomNo(1, 120);
}
}
printMatrix((int *)Mat, n);
Graph<n> gRND(nodes26, Mat);
gRND.travelGreedyFloyd('A');
cout<<"\nShorter Paths:\n";
gRND.printShorterPaths('A');
for(int i = 0; i < 33; i++) {
cout<<"\n\nRANDOM GRAPH"<<(i+1)<<":\n";
const int n = 11;
int Mat[n][n];
for (int i = 0; i < n; i++) {
Mat[i][i] = 0;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Mat[i][j] = Mat[j][i] = randomNo(1, 120);
}
}
printMatrix((int *)Mat, n);
Graph<n> gRND(nodes26, Mat);
gRND.travelGreedyFloyd('A');
cout<<"\nShorter Paths:\n";
gRND.printShorterPaths('A');
}
cout<<"\n\nCompleted. :)";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment