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;

}

Edited 6 Years Ago by John Linux: Error in formatting

for (int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			cout << "\nadjacentNodes(" << i <<")" << "=" << adjacentNodes->at(i)->id;
			cout << "\ndistance(smallest, adjacent) = " << Distance(smallest, adjacent);
			cout << "\nsmallest->distanceFromStart = " << smallest->distanceFromStart;

			int distance = Distance(smallest, getFoundNode(adjacentNodes->at(i)->id)) + smallest->distanceFromStart;

			cout << "\ndistance = Distance(smallest, adjacent) + smallest->distanceFromStart = " << distance;

            cout << "\nadjacent->distanceFromStart = " << getFoundNode(adjacentNodes->at(i)->id)->distanceFromStart;
            cout << "\nadjacentNodes->at(i)->id dist from  start: ";
            cout << getFoundNode(adjacentNodes->at(i)->id)->distanceFromStart;
			if (distance < (adjacentNodes->at(i)->distanceFromStart))
			{
				cout << "\nadjacent->distanceFromStart set to " << distance;
				getFoundNode(adjacentNodes->at(i)->id)->distanceFromStart = distance;
				cout << "\nadjacent->previous set to " << smallest->id;
				getFoundNode(adjacentNodes->at(i)->id)->previous = smallest;
			}
		}
		delete adjacentNodes;

Doing some cout traces it seems like the adjacentNodes referencing is causing issues on the second run. The distanceFromStart figures are incorrect..

Any help would be appreciated..

Start with trivial input files, like say

1
2
A B

then try

2
3
A B
B C


Trying to debug with large data files just clouds the issues.


Another thing to add (for your own benefit) is a 'dump' function you can call to just print the entire data structure as it currently stands (another reason for using smaller test files to avoid being swamped with data).

From what you said, it sounds like you're corrupting the data in some way, so a

dump();
do_something();
dump();

If you believe do_something() should not modify your structure, and it does, then you have something to work with.

I've been trying that, but can't seem to find the error. I battle in C++ with pointers and references as I'm used to Java...

Have done a complete re-do, simplying functions as I went along.. Didn't pinpoint the error, but second time around the problem is solved =)

Comments
Nice - sometimes, that's what it takes - keeping it simple and test as you go.
This article has been dead for over six months. Start a new discussion instead.