{"id":1091,"date":"2010-07-07T12:27:24","date_gmt":"2010-07-07T12:27:24","guid":{"rendered":"http:\/\/www.codingfriends.com\/?p=1091"},"modified":"2011-01-14T13:32:32","modified_gmt":"2011-01-14T13:32:32","slug":"graphs","status":"publish","type":"post","link":"https:\/\/www.codingfriends.com\/index.php\/2010\/07\/07\/graphs\/","title":{"rendered":"Graphs"},"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

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

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

\r\ntypedef Graph PathfinderGraphMain;\r\nclass PathfinderGraph : public PathfinderGraphMain\r\n{\r\npublic:\r\n\tstring returnJpg() { return jpgimage;}\r\n\tvoid setJpg(string jpg) { jpgimage = jpg;}\r\n\r\nprivate:\r\n\tstring jpgimage;\r\n};\r\n\r\n\/\/ as taken from the graphtypes.h\r\nstruct nodeT {\r\n\tstring name;\r\n\tSet arcs;\r\n\tpointT loc;\r\n};\r\nstruct arcT {\r\n\tnodeT *start, *finish;\r\n\tdouble cost;\r\n};\r\n<\/pre>\n
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.<\/p>\n
\r\nif (contents==\"NODES\")\r\n\t{\r\n\t\t\/\/ end at EOF or ARCS\r\n\t\twhile (contents != \"ARCS\" && !inFile.eof())\r\n\t\t{\r\n\t\t\tcontents = ReadLineFromFile(inFile);\r\n\t\t\t\/\/ add the node into \r\n\t\t\tif (contents != \"ARCS\")\r\n\t\t\t{\r\n\t\t\t\t\/\/ need to split the contents string\r\n\t\t\t\tpointT location;\r\n\t\t\t\tint nameI = contents.find_first_of(\" \");\r\n\t\t\t\tlocation.x = StringToInteger(contents.substr(nameI, contents.find_last_of(\" \")- nameI));\r\n\t\t\t\tlocation.y = StringToInteger(contents.substr(contents.find_last_of(\" \")));\r\n\t\t\t\tAddNode(contents.substr(0,nameI), location, thePath);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\t\/\/ end point is the word ARCS\r\n\tif (contents == \"ARCS\")\r\n\t{\r\n\t\t\/\/ read till the end\r\n\t\twhile (!inFile.eof())\r\n\t\t{\r\n\t\t\tcontents = ReadLineFromFile(inFile);\r\n\t\t\tif (!inFile.eof())\r\n\t\t\t{\r\n\t\t\t\tstring startP, endP;\r\n\t\t\t\tint nameI = contents.find_first_of(\" \");\r\n\t\t\t\tstartP = contents.substr(0, nameI);\r\n\t\t\t\tnameI++;\r\n\t\t\t\tendP = contents.substr(nameI, contents.find_last_of(\" \")-nameI);\r\n\t\t\t\tdouble cost = StringToReal(contents.substr(contents.find_last_of(\" \")));\r\n\t\t\t\tAddArc(startP, endP, cost, thePath);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\nvoid AddNode(string name, pointT location, PathfinderGraph &thePath)\r\n{\r\n\tnodeT *node = new nodeT();\r\n\tnode->name = name;\r\n\tnode->loc = location;\r\n\tthePath.addNode(node);\r\n}\r\n\r\nvoid AddArc(string startP, string endP, double cost, PathfinderGraph &thePath)\r\n{\r\n\tnodeT *start = thePath.getNode(startP);\r\n\tnodeT *end = thePath.getNode(endP);\r\n\r\n\tarcT *arc = new arcT();\r\n\tarc->cost = cost;\r\n\tarc->start = start;\r\n\tarc->finish = end;\r\n\tthePath.addArc(arc);\r\n\r\n\tarcT *arc2 = new arcT();\r\n\tarc2->cost = cost;\r\n\tarc2->start = end;\r\n\tarc2->finish = start;\r\n\tthePath.addArc(arc2);\r\n}\r\n<\/pre>\n
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.<\/p>\n
\r\nvoid DrawNodes(Set nodes, string color)\r\n{\t\r\n\tforeach (nodeT *node in nodes)\r\n\t{\r\n\t\tDrawPathfinderNode(node->loc, color, node->name);\r\n\t\tDrawArcs(node->arcs, color);\r\n\t}\r\n\tUpdatePathfinderDisplay();\r\n}\r\n\r\nvoid DrawArcs(Set arcs, string color)\r\n{\r\n\tforeach (arcT *arc in arcs)\r\n\t\tDrawPathfinderArc(arc->start->loc, arc->finish->loc, color);\r\n}<\/pre>\n
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)<\/p>\n
\r\n\/\/ find the nodes near the mouse cords\r\n\/\/ NULL if not found a node, else return a nodeT\r\nnodeT * GetNodeFromMouseCords(PathfinderGraph &thePath, pointT mouseInput)\r\n{\r\n\tnodeT * returnNode;\r\n\tforeach (nodeT *node in thePath.getNodeSet())\r\n\t{\r\n\t\tpointT location = node->loc;\r\n\t\tif (mouseInput.x >(location.x - NODE_RADIUS) && \r\n\t\t\tmouseInput.x <(location.x + NODE_RADIUS))\r\n\t\t\tif (mouseInput.y > (location.y - NODE_RADIUS) &&\r\n\t\t\t\tmouseInput.y < (location.y + NODE_RADIUS))\r\n\t\t\t\treturn node;\r\n\t}\r\n\treturn NULL;\r\n}\r\n\r\n\/\/ need to pull out two places, start and end.\r\nvoid GetTwoLocationsFromMouse(PathfinderGraph &thePath, nodeT * &startN, nodeT * &finishN)\r\n{\r\n\tpointT mouseClick = pointT();\r\n\tcout << \"Please choice your starting location \"<< endl;\r\n\twhile ((startN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)\r\n\t\tmouseClick = GetMouseClick();\r\n\tcout << \"Start : \" << startN->name << endl;\r\n\tDrawPathfinderNode(startN->loc, HIGHLIGHT_COLOR, startN->name);\r\n\twhile (true)\r\n\t{\r\n\t\tcout << \"Please choice your ending location \"<< endl;\r\n\t\tmouseClick = pointT();\r\n\t\twhile ((finishN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)\r\n\t\t\tmouseClick = GetMouseClick();\r\n\t\tif (startN->name == finishN->name)\r\n\t\t\tcout << \"That is silly, you are already there!\"<< endl;\r\n\t\telse\r\n\t\t\tbreak;\r\n\t}\r\n\tcout << \"Finish : \" << finishN->name << endl;\r\n\tDrawPathfinderNode(finishN->loc, HIGHLIGHT_COLOR, finishN->name);\r\n}<\/pre>\n
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).<\/p>\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). 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 … Continue reading Graphs<\/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-1091","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\/1091","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=1091"}],"version-history":[{"count":6,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1091\/revisions"}],"predecessor-version":[{"id":1306,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1091\/revisions\/1306"}],"wp:attachment":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/media?parent=1091"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/categories?post=1091"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/tags?post=1091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}