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
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); } |
Could have done something like this to add all of the node names to the Vector< Set > nodes array, but as said in the post, all nodes should be connected via a arc thus it should have all of the nodes and if there is any single nodes then they kinder are not in the shortest spanning tree!.