Ok, so i have an assignment due in 9 hours, its about computing the shortest paths from a vertix input by the user to all other vertices. The adjacency matrix is supplied from a text file, so I have done the following code:
(Some of it was given for me to begin with, the main functions were done by me:)
The final output should be to print all the paths from the base vertix supplied by the user to all others. The function that should be implemented is the sthPath and the other functions used in it.
Help Please!!
Edge class:
// File: Edge.h
// Definition of Edge class
/* _______________________________________________________________
An edge (u,v,w) existing between nodes (u) and (v) with weight (w)
is modeled as a class (Edge).
__________________________________________________________________
*/
#ifndef EDGE_H
#define EDGE_H
typedef int weightType; // weights are positive integers
class Edge
{
public:
int u;
int v;
weightType w;
bool operator < (const Edge &e)
{ return (w < e.w); }
bool operator <= (const Edge &e)
{ return (w <= e.w); }
}; // end of class Edge declaration
#endif // EDGE_HHeader file:
// File: Graphs.h
// Graph library header file
/*
______________________________________________________________________________________________
This file describes a structure for a weighted undirected graph with a maximum of Vmax = 50
vertices and Emax = Vmax(Vmax-1)/2 edges. The verices are numbered 0,1,...V-1. The graph is
assumed to be on a text file in the form of an adjacency matrix. The weights on the edges are
assumed to be positive integers with zero weight indicating the absence of an edge.
An edge (u,v,w) existing between nodes (u) and (v) with weight (w) is modeled as a class
(Edge). When loaded from the text file, the weights are stored in a 2-D
array (AdjMatrix) representing the adjacency matrix. Another array (edges) stores
the non-zero edges in the graph. The functions declared here are needed to implement the
Dijkstra's Algorithm to compute the shortest paths from a given source node to all other
nodes in the graph.
_______________________________________________________________________________________________
*/
#ifndef GRAPHS_H
#define GRAPHS_H
#include <string>
#include "Edge.h"
using namespace std;
const int Vmax = 50; // Maximum number of vertices
const int Emax = Vmax*(Vmax-1)/2; // Maximum number of edges
class Graphs
{
public:
//_____________________________________
// Member Functions
// Class Constructor & Destructor
Graphs();
~Graphs();
// Function Prototypes___________________
char Vname(const int s) const; // Map vertex number to a name (character)
void getGraph(string fname); // Get Graph from text File (fname)
void dispGraph() const; // Display Ajacency Matrix
int No_of_Verices() const; // Get number of vertices (V)
int No_of_Edges() const; // Get Number of Non-zero edges (E)
void dispEdges() const; // Display Graph edges
void shPath(int s); // Shortest paths from node (s)
//______________________________________________________________________________________________
private:
int V, E; // No.of vertices (V) and edges (E)
weightType AdjMatrix[Vmax][Vmax]; // Adjacency Matrix
Edge edges[Emax]; // Array of non-zero edges
weightType distance[Vmax]; // Distance array for shortest paths
int via[Vmax]; // Via array for shortest paths
bool processed[Vmax]; // processed array for shortest paths
bool prcd();
int directDistance(int i,int j);
bool isAdjacent(int i,int j);
int getClosest(int s);
void getEdges(); // Get Non-Zero edges from adjacency matrix
void printEdge(Edge e) const; // Output an edge (e)
void printPath(int s,int i) const; // Print path from source (s) to destination (i)
};
#endif // GRAPHS_H
#include "Graphs.cpp"Main cpp file:
// FILE: graphs.cpp
// Graph Library Implementation File
#include <fstream> // For reading file from disk
#include <iostream>
#include <string> // For file name
#include <iomanip>
#include "Edge.h" // Deinition of an Edge
using namespace std;
// Constructor
Graphs::Graphs()
{
E = V = 0;
//Removed variable called order (was =0)
}
// Destructor
Graphs::~Graphs()
{
}
// Map vertex number (0,1,2,..) to (A,B,C,..)
char Graphs::Vname(const int s) const
{
return char(s+65);
}
// Get Graph from text File (file name is stored in string fname)
// Graph is stored in adjacency matrix
void Graphs::getGraph(string fname)
{
// Local data ...
weightType wi;
int i,m,r,c;
ifstream source;
source.open(fname.c_str());
source >> V; // Read no. of verices (V)
m = V*V; // Total Number of weights in file
// Convert from a 1-D file of size m weights
// to a 2-D Adjacency Matrix of V rows and V columns
int temp1;
for (i = 0; i < 256; i++)
{
source >> temp1;
r = i / V;
c = i % V;
AdjMatrix[r][c]=temp1;
// get a weight from file
// compute row(r) and column(c)
// put weight in adjacency matrix at [r][c]
}
source.close();
getEdges();
// close file
// Get graph edges
}
// Display Adjacency Matrix
void Graphs::dispGraph() const
{
int i,j;
cout<<"Adjacency Matrix\n";
for(i=0; i<V; i++)
{
for(j=0; j<V; j++)
cout<< setw(3)<< AdjMatrix[i][j] << " ";
cout<< endl;
}
}
// Get Non-Zero edges from adjacency matrix
// and store them in array edges[].
void Graphs::getEdges()
{
int r , c;
int i = 0;
weightType weight;
// Only examine weights above the diagonal
for (r = 0; r <= V-2; r++)
for (c = r+1; c <= V-1; c++)
{
weight = AdjMatrix[r][c];
if (weight > 0)
{
// save (r,c,weight) in edges[i]
edges[i].u = r;
edges[i].v = c;
edges[i].w = weight;
i++;
}
}
E = i; // Number of non-zero edges
}
// Get number of vertices (V)
int Graphs::No_of_Verices() const
{
return V;
}
// Get Number of Non-zero edges (E)
int Graphs::No_of_Edges() const
{
return E;
}
// Output an edge (e): Vertex names and weight
void Graphs::printEdge(Edge e) const
{
cout << Vname(e.u) << " " << Vname(e.v) << " " << e.w << endl;
}
// Display Graph Edges
void Graphs::dispEdges() const
{
cout<<"Graph Edges\n";
for (int i = 0; i < E; i++)
printEdge(edges[i]);
}
// Shortest paths from node s
// uses Dijkstra's Algorithm
void Graphs::shPath(int s)
{
falsify();
for(int k=0;k<V;k++)
cout<<processed[k]<<endl;
processed[s]=true;
while(prcd()==false)
{
int j=getClosest(s);
processed[j]=true;
cout<<j<<"processed"<<endl;
for(int i=0;i<V;i++)
{
if(processed[i]==true || isAdjacent(i,j)==false)
continue;
int new_distance = distance[j]+ directDistance(i,j);
if(new_distance < distance[i])
{
distance[i]=new_distance;
via[i]=j;
}
}
for(int p=0;p<V;p++)
{
cout<<processed[p];
}
system("pause");
}
//printPath(s,5);
//printing
/*for(int i=0;i<V;i++)
{
if(i==s)
continue;
printPath(s,i);
}*/
}
//function to get closest vertix adjacent to another
void Graphs::falsify()
{
for(int i=0;i<V;i++)
{
processed[i]=false;
}
}
bool Graphs::prcd()
{
//function to check if all vertices proces or not yet
for(int i=0;i<V;i++)
{
if(processed[i]==false)
return false;
}
return true;
}
int Graphs::getClosest(int s)
{ //function to get closest adjacent vertix to another
int j=-1;
int temp_weight=9999;
for(int x=0;x<V;x++)
{
if(processed[x]==true) continue;
for(int k=0;k<E;k++)
{
if( (edges[k].u==s && edges[k].v==x) || (edges[k].u==x && edges[k].v==s) )
{
if(j==-1 || edges[k].w<temp_weight)
{
if(x==edges[k].u)
j=edges[k].u;
else
j=edges[k].v;
temp_weight=edges[k].w;
}
}
}
}
return j;
}
// Print path (vertex names) from source (s) to destination (i)
int Graphs::directDistance(int i,int j)
{ //function to get direct distance from two nodes
for(int k=0;k<E;k++)
{
if((edges[k].u==i &&edges[k].v==j) || (edges[k].u==j &&edges[k].v==i))
return edges[k].w;
}
return 0;
}
bool Graphs::isAdjacent(int i,int j)
{ //function to check if two vertices are adjacent
for(int k=0;k<E;k++)
{
if((edges[k].u==i &&edges[k].v==j) || (edges[k].u==j &&edges[k].v==i))
return true;
}
return false;
}
void Graphs::printPath(int s, int i) const
{
if (i == s) cout << Vname(s);
else
{ printPath(s,via[i]); cout << Vname(i); }
// Implement the function here
}