I am reading in data from a textfile, specified by command line args
eg.. <app> inputfile outputfile
I have not yet done any file output, yet have developed some code.
What I'm aiming for is printing out the shortest route from one node to another in a graph.
*The graph is unweighted.
*The graph is directed
Input is read in like this
<numEdges>
<numNodes>
startNode endNode
A B
A C
B D
etc etc...
Here is a sample file:
input.txt
7
5
B E
B A
A C
B C
B D
D E
C E
C D
I have achieved that aim, and get "B C E" from the sample input.
I was then trying to repeat the algorithm, but making B C = 5000 and C E = 5000, so that a different path is found. I have tried for hours to do this but my code is a bit complex so error spotting takes hours...
I would like some pointers, no pun intended, on how I should go about this. I tried to do it, but am getting output of 'E' everytime on the second run, yet manually if i set these edges to 5000 on first run, it works fine and gives me expected output of B D E.
I also had some problems when saying things like (node == node2), on the second run, as the characteristics of the node are the same but not actually the same node... so instead I started using node1->id == node->id, yet this somehow feels like cheating...
Please can you give me a hand, I've put a large amount of work into this... My code so far is below.. If you feel that the programming is unneccessary, give me suggestions with that too, I am new to C++ and it is not an easy language to self study like Java..
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
class Node;
class Edge;
Node* getFoundNode(char nodeLetter);
Node* ExtractSmallest(vector<Node*>& nodes);
vector<Node*>* AdjacentRemainingNodes(Node* node);
vector<Node*> nodes;
vector<Edge*> edges;
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
bool Contains(vector<Node*>& nodes, char nodeID);
void Dijkstras();
void PrintShortestRouteTo(Node* destination);
void addNode(char nodeID);
//void printNodes();
//void printEdges();
class Node
{
public:
Node(char id):id(id), previous(NULL), distanceFromStart(INT_MAX)
{
nodes.push_back(this);
}
public:
char id;
Node* previous;
int distanceFromStart;
};
class Edge
{
public:
Edge(Node* node1, Node* node2, int distance)
: node1(node1), node2(node2), distance(distance)
{
edges.push_back(this);
}
bool Connects(Node* node1, Node* node2)
{
return (
(node1->id == this->node1->id &&
node2->id == this->node2->id) ||
(node1->id == this->node2->id &&
node2->id == this->node1->id));
}
void setDist(int dist)
{
distance = dist;
}
public:
Node* node1;
Node* node2;
int distance;
};
int main(int argc, char* argv[])
{
ifstream inputFile(argv[1]);
if(argc != 3)
{
cout << "Incorrect parameters given.";
cout << "\nParameters must be: \"graph InputFile OutputFile\"\n";
}
else
{
int numEdges = 0;
inputFile >> numEdges;
int numNodes = 0;
inputFile >> numNodes;
char start;
inputFile >> start;
char dest;
inputFile >> dest;
char edgeNode1;
char edgeNode2;
int wt = 1;
while(!inputFile.eof())
{
inputFile >> edgeNode1 >> ws;
inputFile >> edgeNode2 >> ws;
addNode(edgeNode1);
addNode(edgeNode2);
wt = 1;
new Edge(getFoundNode(edgeNode1),getFoundNode(edgeNode2),wt);
}
Node* destNode = getFoundNode(dest);
getFoundNode(start)->distanceFromStart = 0;
Dijkstras();
PrintShortestRouteTo(destNode);
}
return 0;
}
Node* getFoundNode(char nodeLetter)
{
const int size = nodes.size();
for(int i=0; i<size; ++i)
{
if (nodeLetter == nodes.at(i)->id)
{
return nodes.at(i);
}
}
return NULL;
}
void Dijkstras()
{
while (nodes.size() > 0)
{
Node* smallest = ExtractSmallest(nodes);
vector<Node*>* adjacentNodes =
AdjacentRemainingNodes(smallest);
const int size = adjacentNodes->size();
for (int i=0; i<size; ++i)
{
Node* adjacent = adjacentNodes->at(i);
int distance = Distance(smallest, adjacent) + smallest->distanceFromStart;
if (distance < adjacent->distanceFromStart)
{
adjacent->distanceFromStart = distance;
adjacent->previous = smallest;
}
}
delete adjacentNodes;
}
}
// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
int size = nodes.size();
if (size == 0)
return NULL;
int smallestPosition = 0;
Node* smallest = nodes.at(0);
for (int i=1; i<size; ++i)
{
Node* current = nodes.at(i);
if (current->distanceFromStart < smallest->distanceFromStart)
{
smallest = current;
smallestPosition = i;
}
}
nodes.erase(nodes.begin() + smallestPosition);
return smallest;
}
// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
vector<Node*>* adjacentNodes = new vector<Node*>();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Node* adjacent = NULL;
if (edge->node1 == node) //Check this
{
adjacent = edge->node2;
}
if (adjacent && Contains(nodes, adjacent))
{
adjacentNodes->push_back(adjacent);
}
}
return adjacentNodes;
}
// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->Connects(node1, node2))
{
return edge->distance;
}
}
return -1; // should never happen
}
// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
const int size = nodes.size();
for(int i=0; i<size; ++i)
{
if (node == nodes.at(i))
{
return true;
}
}
return false;
}
bool Contains(vector<Node*>& nodes, char nodeID)
{
const int size = nodes.size();
for(int i=0; i<size; ++i)
{
if (nodeID == nodes.at(i)->id)
{
return true;
}
}
return false;
}
void addNode(char nodeID)
{
if (!Contains(nodes,nodeID))
{
new Node(nodeID);
}
}
void PrintShortestRouteTo(Node* destination)
{
Node* previous = destination;
vector<char> routeVector;
while (previous)
{
routeVector.push_back(previous->id);
previous = previous->previous;
}
string shortestRoute = "";
int size = routeVector.size();
for(int a = 0; a < size; a++)
{
shortestRoute += routeVector.back();
shortestRoute += " ";
routeVector.pop_back();
}
cout << shortestRoute;
}