Organizing and optimizing code into source and header files
I'm a new C++ programmer coming from java. I translated Dijkstra's algorithm from java into C++. I know this is not good programming practice, hence I will post the code here for optimisation suggestions.
This is one giant source file.
Code:
#include <iostream>
#include <vector>
#include <string>
using std::vector;
///////////////////////////////////////////////////////////////////////////////
//Class that holds distance and parent
class DistPar
{
public:
int distance; //distance from start to this vertex
int parentVert; //parent of this vertex
//-----------------------------------------------------------------------------
DistPar(int pv, int d) //constructor
{
distance = d;
parentVert = pv;
}
}; //end class Distpar
///////////////////////////////////////////////////////////////////////////////
//A vertice in our graph
class Vertex
{
public:
char label;
bool isInTree;
//-----------------------------------------------------------------------------
Vertex(char lab)
{
label = lab;
isInTree = false;
}
}; //end class Vertex
///////////////////////////////////////////////////////////////////////////////
//Graph class that does the computation
class graphCalc
{
public:
int MAX_VERTS; //Need to change later to match user input
int INFINITY;
vector<Vertex> vertexList; //list of all our vertices
vector<vector<int> > adjMat; //This is our adjacency matrix for vertice layout representation
vector<DistPar> sPath; //shortest path array
int nTree; //Number of vertices in our tree
int nVerts; //current number of vertices
int currentVert; //current vertex
int startToCurrent; //distance to currentVert from start
//-----------------------------------------------------------------------------
graphCalc() //Needs to take input parameters later
{
MAX_VERTS = 999;
INFINITY = 1000000;
nVerts = 0;
nTree = 0;
//Set adjMatrix to infinity
for (int i = 0; i < 5; i++)
{
adjMat.push_back( vector<int>(1, INFINITY) );
for ( int j = 0; j < 5; j++)
adjMat[i].push_back(INFINITY);
}
}
//-----------------------------------------------------------------------------
void addVertex(char lab)
{
nVerts++;
vertexList.push_back( Vertex(lab) );
}
//-----------------------------------------------------------------------------
void addEdge(int start, int end, int weight)
{
adjMat[start][end] = weight; //directed
}
//-----------------------------------------------------------------------------
//find all shortest paths
void path()
{
int startTree = 0; //start at vertex 0 or A
vertexList[startTree].isInTree = true;
nTree = 1; //put in tree
//transfer row of distances from A in adjMat to sPath
for (int j = 0; j < nVerts; j++)
{
//Distance of 2nd object in row since we skip A, A->A = INFINITE
int tempDist = adjMat[startTree][j];
sPath.push_back( DistPar(startTree, tempDist));
}
//until all vertices are in tree
while (nTree < nVerts)
{
int indexMin = getMin(); //get min from sPath
int minDist = sPath[indexMin].distance;
if (minDist == INFINITY) //if all infinite
{
std::cout << "There are unreachable vertices.";
break;
}
else
{
currentVert = indexMin; //reset currentVert to closest vert
startToCurrent = sPath[indexMin].distance;
}
//put current vertex in tree
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath(); //update sPath[] array
} //end while (nTree < nVerts)
displayPaths(); //display sPath[]
nTree = 0; //clear tree
for (int j = 0; j < nVerts; j++)
vertexList[j].isInTree = false;
} //end path()
//-----------------------------------------------------------------------------
//get minimum distance in sPath and return it
int getMin()
{
int minDist = INFINITY; //assume minimum
int indexMin = 0;
//For each vertex, if it's in tree and smaller than old one
for (int j = 1; j < nVerts; j++)
{
if (!vertexList[j].isInTree && sPath[j].distance < minDist)
{
minDist = sPath[j].distance;
indexMin = j;
}
} //end for
return indexMin;
} //end getMin()
//-----------------------------------------------------------------------------
void adjust_sPath()
{
//adjust values in shortest-path array sPath
int column = 1; //skip the starting vertex 'A'
while (column < nVerts) //loop across all vertices in array
{
//if this column's vertex is in tree, skip it
if (vertexList[column].isInTree)
{
column++;;
continue;
}
/*calculate distances*/
//get edge from currentVert to destination vertex
int currentToFringe = adjMat[currentVert][column];
//add distance from start to current
int startToFringe = startToCurrent + currentToFringe;
//get distance of current sPath entry
int sPathDist = sPath[column].distance;
//compare distance from start to fringe with sPath fringe entry
if (startToFringe < sPathDist) //if shorter
{
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} //end while (column < nVerts)
} //end adjust_sPath()
void displayPaths()
{
for (int j = 0; j < nVerts; j++)
{
std::cout << vertexList[j].label << "=";
if (sPath[j].distance == INFINITY)
std::cout << "inf";
else
std::cout << sPath[j].distance;
char parent = vertexList[ sPath[j].parentVert].label;
std::cout << "(" << parent << ") ";
}
std::cout << " ";
std::cout << std::endl;
}
//-----------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
//This is the main class
int main()
{
graphCalc theGraph;
theGraph.addVertex('A'); //0 start
theGraph.addVertex('B'); //1 start
theGraph.addVertex('C'); //2 start
theGraph.addVertex('D'); //3 start
theGraph.addVertex('E'); //4 start
theGraph.addEdge(0, 1, 50); //A->B 50
theGraph.addEdge(0, 3, 80); //A->B 50
theGraph.addEdge(1, 2, 60); //A->B 50
theGraph.addEdge(1, 3, 90); //A->B 50
theGraph.addEdge(2, 4, 40); //A->B 50
theGraph.addEdge(3, 2, 20); //A->B 50
theGraph.addEdge(3, 4, 70); //A->B 50
theGraph.addEdge(4, 1, 50); //A->B 50
std::cout << std::endl;
std::cout << "Shortest paths ";
theGraph.path(); //main function that does everything
std::cout << std::endl;
} //end main class
What I plan to do is to create 3 header files to hold each of the 3 classes. Then have a .cpp source to hold the function declarations associated with each of the header files. Finally, the source with main() would include all the header files.
EDIT: All the line length comments are there for easy readability. They will be removed of course.
EDIT2: Good lord the formatting got destroyed during copy/paste. Trying to fix. Sorry would take too long to fix.