Krushal – Coding Friends

Graphs – Part 2

The graphs use two algorithms to either find the shortest path (Dijkstra algorithm) or the minimal spanning tree (Krushal’s method).

This is the second post of the assignment of the Path class and also the Dijkstra / Krushal methods. So to start with the Path class, below is the header of the class with the different methods inside the class, which basically has a Add method to add the arc to the Path, TotalPathDistance which will return the total distance taken in O(1) in big O notation, a toString method which returns a string version of the internal data structure of the arcs added, size method which returns the size of the arcs added to the arcs internal vector array and lastly the GetElementAt method that will return a arc of a element at any given point in the vector array.

class Path {
 
// [TODO: complete the class definition]
 
public:
	Path();
	~Path();
 
/*
 * Function: Add
 * Usage: Add(arcT *arc);
 * ----------------------------------
 * Adds a arc to the internal array of arc(s)
 */
	void Add(arcT *arc);
 
/*
 * Function: TotalPathDistance
 * Usage: TotalPathDistance();
 * ----------------------------------
 * returns the total distance in a O(1) time instead of cycling through the list of arcs
 */
	double TotalPathDistance();
 
 
/*
 * Function: toString
 * Usage: toString();
 * ----------------------------------
 * converts the array of arcs to a string repenstation
 */
	string toString();
 
/*
 * Function: size
 * Usage: size();
 * ----------------------------------
 * returns the size of the internal arcs implemetation e.g. the total amount of arcs already stored.
 */
	int size();
/*
 * Function: GetElementAt
 * Usage: GetElementAt(4);
 * ----------------------------------
 * returns a arcT* at any given element index, as passed by the parameter
 */
	arcT* GetElementAt(int i);
 
private:
	Vector<arcT *> arcs;
	double totalCost;
};

and here is the functions implementation, to start with the Path class is constructed with a total distance of 0 and then every time that a new arc is added the total distance is increased by the value of the cost associated with that arc. The tostring method just loops over the vector array of arcs and builds up a string of there details.

Path::Path()
{
	totalCost = 0;
}
 
Path::~Path()
{
	arcs.clear();
}
 
void Path::Add(arcT *arc)
{
	arcs.add(arc);
	totalCost += arc->cost;
}
 
double Path::TotalPathDistance()
{
	return totalCost;
}
 
string Path::toString()
{
	string returnStr;
	foreach(arcT *arc in arcs)
	{
		returnStr = returnStr + arc->start->name + "->" + arc->finish->name + "(" + RealToString(arc->cost) + ")" +"\n";
	}
	return returnStr;
}
 
int Path::size()
{
	return arcs.size();
}
 
arcT* Path::GetElementAt(int i)
{
	return arcs[i];
}

Because the Dijkstra method was already coded from the course reader handout, here is how I have altered it to use the new Path class to have a big O notation of O(1), I have just basically altered it where it was a Vector types to be a Path type instead and called the relevant methods on that new Path type instead of using the TotalPathDistance function, also with a couple of changes to the bottom part of the function below because there was no = operator, so instead changed to GetElementAt method.

Path FindShortestPath(nodeT *start, nodeT *finish) {
	Path path;
	PQueue< Path> queue;
	Map<double> fixed;
	while (start != finish) {
		if (!fixed.containsKey(start->name)) {
			fixed.put(start->name, path.TotalPathDistance());  
			foreach (arcT *arc in start->arcs) {
				if (!fixed.containsKey(arc->finish->name)) {
					Path newPath = path;
					newPath.Add(arc);
					queue.add(newPath, newPath.TotalPathDistance());
				}
			}
		}
		if (queue.isEmpty()) return Path();
		path = queue.extractMin();
		start = path.GetElementAt(path.size() -1)->finish; 
	}
	return path;
}

and here is the Kruskal function, to start with I only need to store the set of nodes within a array (so using a vector array) with also the just needing to store the arcs that are joining the nodes together (I am using a Set here instead of a vector, but does not really matter as such). So to start with I am first building up a list of nodes (Vector array of Sets of strings) of each node within the graph, whilst also adding to a priority queue of all of the arcs, I could have used a foreach loop and gone over the getNodesSet from thePath variable, but the arcs should have all of the nodes inside it :), and since if the nodes are not attached to the arcs then how could they form a path!. And then the main loop is just going through all of the arcs in order of cost (lowest first to highest) seeing if the start and finish nodes are within the same Set within the vector array, if so they have already been added to the minimal spanning tree (Kruskal) else if they have not been added merge (union) the two sets together and also add the arc to the list of arcs to display to the screen once this function has completed.

void KruskalMethod(PathfinderGraph &thePath)
{
	Set<arcT *> arcs = thePath.getArcSet();
	PQueue<arcT *> path;
	Vector< Set<string> > nodes;
	Set<arcT *> theJoiningArcs;
 
	CleanScreen(thePath);
	// place into a pqueue and also build up a vector of sets of the different node names
	foreach (arcT *arc in arcs)
	{
		path.add(arc, arc->cost);
		bool inAlready = false;
		for (int i = 0; i < nodes.size(); i++)
		{
			if (nodes[i].contains(arc->start->name))
			{
				inAlready = true;
				break;
			}
		}
		if (!inAlready)
		{
			Set<string> newNode;
			newNode.add(arc->start->name);
			nodes.add(newNode);
		}
	}
	while (!path.isEmpty())
	{
		arcT * arc = path.extractMin();
		// start node and end nodes set id
		int startN, endN;
		startN = endN = -1;
		for (int i =0; i < nodes.size(); i++)
		{
			if (nodes[i].contains(arc->start->name))
				startN = i;
			if (nodes[i].contains(arc->finish->name))
				endN = i;
		}
		// if in different sets then
		if (startN != endN)
		{
			nodes[startN].unionWith(nodes[endN]);
			nodes.removeAt(endN);
			theJoiningArcs.add(arc);
//			cout << "Cost : " << arc->cost << " : Start : " << arc->start->name << " : Finish : " << arc->finish->name << endl;
		} /*else
			cout << "Cost : " << arc->cost << " : Start : " << arc->start->name << " : Finish : " << arc->finish->name << " ( not needed) " << endl;*/
	}
	// draw out all of the arcs on the grid in a dim color
	DrawNodes(thePath.getNodeSet(), DIM_COLOR);	
	// draw the minimum arcs in a highlight color
	DrawArcs(theJoiningArcs, HIGHLIGHT_COLOR);
}

Graphs

The graphs use two algorithms to either find the shortest path (Dijkstra algorithm) or the minimal spanning tree (Krushal’s method).

I am going to split up the assignment into 2 posts so that can try and covert as much of the assignment without spanning a massive post, so in this post going to talk about loading in the data from the textual files and also displaying the data on screen (graphics), and how I altered the sublcass to allow for more data to be stored for this assignment. In the next post it will be about the Path class implementation with the Dijkstra and Krushal algorithms.

So to start off with, I altered the type definition for the main/parent class of Graph to be called PathfinderGraphMain so that when I created the subclass I could call it the PathfinderGraph, just liked the look of that :). and since the graph types, nodeT / arcT are capable of holding all of the other data (have included them in the code below) I just need to store the graph image which is what the subclass below is doing for me, was trying to avoid using any global variables, so that is all that my subclass is additional storing and accessing using the get/set functions.

typedef Graph<nodeT, arcT> PathfinderGraphMain;
class PathfinderGraph : public PathfinderGraphMain
{
public:
	string returnJpg() { return jpgimage;}
	void setJpg(string jpg) { jpgimage = jpg;}
 
private:
	string jpgimage;
};
 
// as taken from the graphtypes.h
struct nodeT {
	string name;
	Set<arcT *> arcs;
	pointT loc;
};
struct arcT {
	nodeT *start, *finish;
	double cost;
};

here is the sub part of the method that will read in the data from the textual file, I am basically reading in the nodes to start with and then calling the AddNode function (below the code) and also the AddArc (again further down in the code below) which basically just call the main Graph class addNode / addArc functions.

if (contents=="NODES")
	{
		// end at EOF or ARCS
		while (contents != "ARCS" && !inFile.eof())
		{
			contents = ReadLineFromFile(inFile);
			// add the node into 
			if (contents != "ARCS")
			{
				// need to split the contents string
				pointT location;
				int nameI = contents.find_first_of(" ");
				location.x = StringToInteger(contents.substr(nameI, contents.find_last_of(" ")- nameI));
				location.y = StringToInteger(contents.substr(contents.find_last_of(" ")));
				AddNode(contents.substr(0,nameI), location, thePath);
			}
		}
	}
	// end point is the word ARCS
	if (contents == "ARCS")
	{
		// read till the end
		while (!inFile.eof())
		{
			contents = ReadLineFromFile(inFile);
			if (!inFile.eof())
			{
				string startP, endP;
				int nameI = contents.find_first_of(" ");
				startP = contents.substr(0, nameI);
				nameI++;
				endP = contents.substr(nameI, contents.find_last_of(" ")-nameI);
				double cost = StringToReal(contents.substr(contents.find_last_of(" ")));
				AddArc(startP, endP, cost, thePath);
			}
		}
	}
 
void AddNode(string name, pointT location, PathfinderGraph &thePath)
{
	nodeT *node = new nodeT();
	node->name = name;
	node->loc = location;
	thePath.addNode(node);
}
 
void AddArc(string startP, string endP, double cost, PathfinderGraph &thePath)
{
	nodeT *start = thePath.getNode(startP);
	nodeT *end = thePath.getNode(endP);
 
	arcT *arc = new arcT();
	arc->cost = cost;
	arc->start = start;
	arc->finish = end;
	thePath.addArc(arc);
 
	arcT *arc2 = new arcT();
	arc2->cost = cost;
	arc2->start = end;
	arc2->finish = start;
	thePath.addArc(arc2);
}

To draw to the screen, I have created two methods that will take a set of nodes (nodeT structures) and also the colour that is required to display. Since the Set class has a Iterator I can use the foreach (marco from the CS106B libraries) to loop over the Set class to then just display the nodes/arcs via the CS106B graphics libraries again.

void DrawNodes(Set<nodeT *> nodes, string color)
{	
	foreach (nodeT *node in nodes)
	{
		DrawPathfinderNode(node->loc, color, node->name);
		DrawArcs(node->arcs, color);
	}
	UpdatePathfinderDisplay();
}
 
void DrawArcs(Set<arcT *> arcs, string color)
{
	foreach (arcT *arc in arcs)
		DrawPathfinderArc(arc->start->loc, arc->finish->loc, color);
}

The last part of the graphical aspects is getting the mouse inputs to link to a node on the graphical display, once again using the CS106B libraries for obtaining a point location (x/y coordinates) and then testing to see if this coordinates have clicked on the node location (kinder putting a square around the node of the node radius in size, this NODE_RADIUS is defined in the CS106B libraries and that is what the node will have a circle radius off)

// find the nodes near the mouse cords
// NULL if not found a node, else return a nodeT
nodeT * GetNodeFromMouseCords(PathfinderGraph &thePath, pointT mouseInput)
{
	nodeT * returnNode;
	foreach (nodeT *node in thePath.getNodeSet())
	{
		pointT location = node->loc;
		if (mouseInput.x >(location.x - NODE_RADIUS) && 
			mouseInput.x <(location.x + NODE_RADIUS))
			if (mouseInput.y > (location.y - NODE_RADIUS) &&
				mouseInput.y < (location.y + NODE_RADIUS))
				return node;
	}
	return NULL;
}
 
// need to pull out two places, start and end.
void GetTwoLocationsFromMouse(PathfinderGraph &thePath, nodeT * &startN, nodeT * &finishN)
{
	pointT mouseClick = pointT();
	cout << "Please choice your starting location "<< endl;
	while ((startN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)
		mouseClick = GetMouseClick();
	cout << "Start : " << startN->name << endl;
	DrawPathfinderNode(startN->loc, HIGHLIGHT_COLOR, startN->name);
	while (true)
	{
		cout << "Please choice your ending location "<< endl;
		mouseClick = pointT();
		while ((finishN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)
			mouseClick = GetMouseClick();
		if (startN->name == finishN->name)
			cout << "That is silly, you are already there!"<< endl;
		else
			break;
	}
	cout << "Finish : " << finishN->name << endl;
	DrawPathfinderNode(finishN->loc, HIGHLIGHT_COLOR, finishN->name);
}

after the user has selected two nodes it will highlight the nodes with the HIGHLIGHT_COLOR from the CS106B libraries again (which was the colour red). I shall post next on the Path class and also the two breath-search and minimal spanning trees, (Dijkstra and Krushal’s algorithms).