{"id":1094,"date":"2010-07-07T13:03:35","date_gmt":"2010-07-07T13:03:35","guid":{"rendered":"http:\/\/www.codingfriends.com\/?p=1094"},"modified":"2011-01-14T13:33:14","modified_gmt":"2011-01-14T13:33:14","slug":"graphs-part-2","status":"publish","type":"post","link":"https:\/\/www.codingfriends.com\/index.php\/2010\/07\/07\/graphs-part-2\/","title":{"rendered":"Graphs – Part 2"},"content":{"rendered":"

<\/a><\/span>The graphs use two algorithms to either find the shortest path (Dijkstra<\/a> algorithm) or the minimal spanning tree (Krushal’s<\/a> method).<\/p>\n

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>, 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.<\/p>\n

\r\nclass Path {\r\n\r\n\/\/ [TODO: complete the class definition]\r\n\r\npublic:\r\n\tPath();\r\n\t~Path();\r\n\r\n\/*\r\n * Function: Add\r\n * Usage: Add(arcT *arc);\r\n * ----------------------------------\r\n * Adds a arc to the internal array of arc(s)\r\n *\/\r\n\tvoid Add(arcT *arc);\r\n\r\n\/*\r\n * Function: TotalPathDistance\r\n * Usage: TotalPathDistance();\r\n * ----------------------------------\r\n * returns the total distance in a O(1) time instead of cycling through the list of arcs\r\n *\/\r\n\tdouble TotalPathDistance();\r\n\r\n\t\r\n\/*\r\n * Function: toString\r\n * Usage: toString();\r\n * ----------------------------------\r\n * converts the array of arcs to a string repenstation\r\n *\/\r\n\tstring toString();\r\n\r\n\/*\r\n * Function: size\r\n * Usage: size();\r\n * ----------------------------------\r\n * returns the size of the internal arcs implemetation e.g. the total amount of arcs already stored.\r\n *\/\r\n\tint size();\r\n\/*\r\n * Function: GetElementAt\r\n * Usage: GetElementAt(4);\r\n * ----------------------------------\r\n * returns a arcT* at any given element index, as passed by the parameter\r\n *\/\r\n\tarcT* GetElementAt(int i);\r\n\r\nprivate:\r\n\tVector arcs;\r\n\tdouble totalCost;\r\n};\r\n<\/pre>\n
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.<\/p>\n
\r\nPath::Path()\r\n{\r\n\ttotalCost = 0;\r\n}\r\n\r\nPath::~Path()\r\n{\r\n\tarcs.clear();\r\n}\r\n\r\nvoid Path::Add(arcT *arc)\r\n{\r\n\tarcs.add(arc);\r\n\ttotalCost += arc->cost;\r\n}\r\n\r\ndouble Path::TotalPathDistance()\r\n{\r\n\treturn totalCost;\r\n}\r\n\r\nstring Path::toString()\r\n{\r\n\tstring returnStr;\r\n\tforeach(arcT *arc in arcs)\r\n\t{\r\n\t\treturnStr = returnStr + arc->start->name + \"->\" + arc->finish->name + \"(\" + RealToString(arc->cost) + \")\" +\"\\n\";\r\n\t}\r\n\treturn returnStr;\r\n}\r\n\r\nint Path::size()\r\n{\r\n\treturn arcs.size();\r\n}\r\n\r\narcT* Path::GetElementAt(int i)\r\n{\r\n\treturn arcs[i];\r\n}<\/pre>\n
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.<\/p>\n
\r\nPath FindShortestPath(nodeT *start, nodeT *finish) {\r\n\tPath path;\r\n\tPQueue< Path> queue;\r\n\tMap fixed;\r\n\twhile (start != finish) {\r\n\t\tif (!fixed.containsKey(start->name)) {\r\n\t\t\tfixed.put(start->name, path.TotalPathDistance());  \r\n\t\t\tforeach (arcT *arc in start->arcs) {\r\n\t\t\t\tif (!fixed.containsKey(arc->finish->name)) {\r\n\t\t\t\t\tPath newPath = path;\r\n\t\t\t\t\tnewPath.Add(arc);\r\n\t\t\t\t\tqueue.add(newPath, newPath.TotalPathDistance());\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tif (queue.isEmpty()) return Path();\r\n\t\tpath = queue.extractMin();\r\n\t\tstart = path.GetElementAt(path.size() -1)->finish; \r\n\t}\r\n\treturn path;\r\n}<\/pre>\n
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.<\/p>\n
\r\nvoid KruskalMethod(PathfinderGraph &thePath)\r\n{\r\n\tSet arcs = thePath.getArcSet();\r\n\tPQueue path;\r\n\tVector< Set > nodes;\r\n\tSet theJoiningArcs;\r\n\r\n\tCleanScreen(thePath);\r\n\t\/\/ place into a pqueue and also build up a vector of sets of the different node names\r\n\tforeach (arcT *arc in arcs)\r\n\t{\r\n\t\tpath.add(arc, arc->cost);\r\n\t\tbool inAlready = false;\r\n\t\tfor (int i = 0; i < nodes.size(); i++)\r\n\t\t{\r\n\t\t\tif (nodes[i].contains(arc->start->name))\r\n\t\t\t{\r\n\t\t\t\tinAlready = true;\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t\tif (!inAlready)\r\n\t\t{\r\n\t\t\tSet newNode;\r\n\t\t\tnewNode.add(arc->start->name);\r\n\t\t\tnodes.add(newNode);\r\n\t\t}\r\n\t}\r\n\twhile (!path.isEmpty())\r\n\t{\r\n\t\tarcT * arc = path.extractMin();\r\n\t\t\/\/ start node and end nodes set id\r\n\t\tint startN, endN;\r\n\t\tstartN = endN = -1;\r\n\t\tfor (int i =0; i < nodes.size(); i++)\r\n\t\t{\r\n\t\t\tif (nodes[i].contains(arc->start->name))\r\n\t\t\t\tstartN = i;\r\n\t\t\tif (nodes[i].contains(arc->finish->name))\r\n\t\t\t\tendN = i;\r\n\t\t}\r\n\t\t\/\/ if in different sets then\r\n\t\tif (startN != endN)\r\n\t\t{\r\n\t\t\tnodes[startN].unionWith(nodes[endN]);\r\n\t\t\tnodes.removeAt(endN);\r\n\t\t\ttheJoiningArcs.add(arc);\r\n\/\/\t\t\tcout << \"Cost : \" << arc->cost << \" : Start : \" << arc->start->name << \" : Finish : \" << arc->finish->name << endl;\r\n\t\t} \/*else\r\n\t\t\tcout << \"Cost : \" << arc->cost << \" : Start : \" << arc->start->name << \" : Finish : \" << arc->finish->name << \" ( not needed) \" << endl;*\/\r\n\t}\r\n\t\/\/ draw out all of the arcs on the grid in a dim color\r\n\tDrawNodes(thePath.getNodeSet(), DIM_COLOR);\t\r\n\t\/\/ draw the minimum arcs in a highlight color\r\n\tDrawArcs(theJoiningArcs, HIGHLIGHT_COLOR);\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading Graphs – Part 2<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[240,239,238],"class_list":["post-1094","post","type-post","status-publish","format-standard","hentry","category-c_and_cpp","tag-dijkstra","tag-graphs","tag-krushal"],"_links":{"self":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1094","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/comments?post=1094"}],"version-history":[{"count":13,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1094\/revisions"}],"predecessor-version":[{"id":1307,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1094\/revisions\/1307"}],"wp:attachment":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/media?parent=1094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/categories?post=1094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/tags?post=1094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}