06 Aug graphicalSort(lunix)
In this task you’ll implement Topographical Sort. This sort algorithm is laid out in chapter 9 of our book.
I’ve included code to build the graph from a GraphViz dot file. This is based on our code from the
Dijkstra’s MA.
Because toposort doesn’t specify order when there are multiple nodes with an indegree of zero, I can’t
pre-test your output, but I’ll know it when I see it done properly.
Here are some of the key requirements:
1) Your toposort algorithm must return a list of vertex pointers
2) Your toposort algorithm must actually remove the vertices from the graph as you execute
3) The code will print the graph after you run toposort and it should have ZERO nodes left
Yes, you’ll need to modify the Vertex objects, maybe change how vertices are stored in the graph and
eventually just chuck everything but my main and the dot file parser. That’s entirely up to you.
The points for this assignment will count towards your PA/Homework pool of points.
Testing The final tests basically go:
1) load dot file into graph
2) print graph out
3) run toposort
4) print toposort results
5) print graph out (with no nodes since toposort destroyed it)
Deliverables You must upload your program through Blackboard no later than midnight on Monday, May 1st, 2017.
Grading Criteria Your assignment will be judged by the following criteria:
● [16] Final tests output a proper toposort ● [2] Data structure usage. Your program actually deletes the graph as it runs toposort ● [2] Your code is well documented and generally easy to read.
File/main.cpp
#include <cstdlib> #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <string.h> #include “Graph.h” #include “Vertex.h” #include <list> using namespace std; /** * Test the graph algorithm with the topo graph from the class textbook * Graph may be found on page ??? and in topoGraph.png */ void run_TopoGraphTest() { cout << ” [d] Testing Topological sort graph (small graph) tests.” << endl; Graph graph{}; graph.loadDotFile( “topoGraph.dot” ); cout << ” [d] Current graph structure from topo’s graph: ” << endl; cout << graph.to_string( true ) << endl; cout << ” [d] ** Starting Topological Here **” << endl; //list<Vertex*> topoResults = graph.getTopoSort(); cout << ” [!!!!] Resulting topographical sort output goes here.” << endl; cout << ” [!!!!] Valid output would look something like:” << endl; cout << ” {1, 0, 8, 9, 10, 16, 2, 3, 6, 5, 15, 4, 12, 14, 7, 13, 11}” << endl; cout << ” — No, I don’t know your final output because there’s actually several places you could do it in different ways.” << endl; cout << ” [d] Current graph structure AFTER topographical sort run (should be empty): ” << endl; cout << graph.to_string( true ) << endl; cout << ” [d] Topo sort graph tests complete. ” << endl; } /** * Test mode operations */ void run_test_mode( bool bigtest = false ) { cout << ” [t] Running in test mode. ” << endl; run_TopoGraphTest(); if( bigtest ) cout << ” [!] No Bigtest option yet” << endl; cout << ” [t] All tests complete. ” << endl; } /** * Normal mode execution for general user control */ void run_normal_mode() { cout << ” [!] Nothing to do in normal mode so here’s a hat: ” << endl; cout <<“” ” _.-‘`’-._\n” ” .-‘ _ ‘-.\n” ” `-.__ `\\_.-‘\n” ” | `-“\\|\n” ” jgs `-…..-A\n” ” #\n” ” #\n”; cout << endl; cout << ” Oh, and you should probably run ‘make test’ to test your program. \n” ” To run the mouse brain graph, use ‘make bigtest’, which takes about 15 sec for me. \n” ” You’ll find images of the graphs we’re using in:\n” ” bookGraph.png\n” ” MouseBrainGraph.png (currently being built – fingers crossed)\n” “\n” ” Both built using: neato -Tpng bookGraph.dot -o bookGraph.png\n” ” Both built using: neato -Tpng MouseBrainGraph.dot -o MouseBrainGraph.png\n”; } /** * Main function for test or use */ int main( int argc, char* argv[] ) { int retState = 0; // Note: If you call this program like this: ./Dijkstra –test // it will call the test function if( argc > 1 && !strcmp(argv[1], “–bigtest” ) ) { run_test_mode( true ); cout << ” [x] BIGTEST testing program complete. ” << endl; } else if( argc > 1 && !strcmp(argv[1], “–test” ) ) { run_test_mode( ); cout << ” [x] Testing program complete. ” << endl; } else { cout << ” [x] Running in normal mode. ” << endl; run_normal_mode(); } }
File/Makefile
# # # # Variables GPP = g++ CFLAGS = -g -std=c++0x #-static RM = rm -f BINNAME = TopoSort # Shell gives make a full user environment # Adding this to PATH will find the newer g++ compiler on the EECS servers. SHELL := /bin/bash PATH := /opt/rh/devtoolset-3/root/usr/bin/:$(PATH) # Default is what happenes when you call make with no options # In this case, it requires that ‘all’ is completed default: all # All is the normal default for most Makefiles # In this case, it requires that build is completed all: build # build depends upon *.cpp, then runs the command: # g++ -g -std=c++0x -o bigFiveList build: main.cpp $(GPP) $(CFLAGS) -o $(BINNAME) main.cpp run: build ./$(BINNAME) test: build ./$(BINNAME) –test bigtest: build ./$(BINNAME) –bigtest # If you call “make clean” it will remove the built program # rm -f HelloWorld clean veryclean: $(RM) $(BINNAME)
File/topoGraph.dot
digraph { 0 [label=”0″, pos=”2,8!”]; 1 [label=”1″, pos=”2,6!”]; 2 [label=”2″, pos=”4,2!”]; 10 [label=”10″, pos=”4,4!”]; 9 [label=”9″, pos=”4,6!”]; 8 [label=”8″, pos=”4,8!”]; 16 [label=”16″, pos=”4,10!”]; 4 [label=”4″, pos=”6,2!”]; 15 [label=”15″, pos=”6,4!”]; 3 [label=”3″, pos=”6,6!”]; 5 [label=”5″, pos=”6,8!”]; 6 [label=”6″, pos=”6,10!”]; 7 [label=”7″, pos=”8,2!”]; 14 [label=”14″, pos=”8,4!”]; 13 [label=”13″, pos=”8,6!”]; 11 [label=”11″, pos=”8,8!”]; 12 [label=”12″, pos=”8,10!”]; 0 -> 8 [weight=”1″]; 1 -> 8 [weight=”1″]; 1 -> 9 [weight=”1″]; 1 -> 10 [weight=”1″]; 8 -> 16 [weight=”1″]; 8 -> 6 [weight=”1″]; 8 -> 5 [weight=”1″]; 8 -> 3 [weight=”1″]; 8 -> 15 [weight=”1″]; 8 -> 4 [weight=”1″]; 9 -> 15 [weight=”1″]; 10 -> 3 [weight=”1″]; 10 -> 15 [weight=”1″]; 10 -> 2 [weight=”1″]; 5 -> 11 [weight=”1″]; 3 -> 12 [weight=”1″]; 3 -> 13 [weight=”1″]; 3 -> 14 [weight=”1″]; 15 -> 14 [weight=”1″]; 15 -> 4 [weight=”1″]; 13 -> 11 [weight=”1″]; 14 -> 7 [weight=”1″]; }
File/topoGraph.png
File/Vertex.h
#ifndef VERTEX_H #define VERTEX_H #include <string> #include <queue> #include <unordered_map> #include <limits> using namespace std; class Vertex { private: int _id; // ID (key) of given vertice bool _known = false; // Dijkstra’s algorithm “known” flag Vertex* _path = nullptr; // Dijkstra’s algorithm parent vertex pointer // Weight of path through graph – starts at a true infinity (inf) double _path_weight = std::numeric_limits<double>::infinity(); unordered_map<Vertex*, double> _edges; // Adjacent nodes to this vertice public: Vertex() { } Vertex(int id) { _id = id; } string to_string( bool with_edges = false ) { //cout << “Vertex self address: ” << this << endl; string ret = “V- ID: ” + std::to_string(_id); ret += “\t| k: “; ( _known ) ? ret += “T” : ret += “F”; ret += “\t| pw: ” + std::to_string(_path_weight); ret += “\t| p: “; if( _path ) { ret += std::to_string( _path->getId() ); } else { ret += “null”; } if( with_edges ) { ret += ” | Edges:”; for( auto edge : _edges ) { ret += “\n edge to: ” + std::to_string( edge.first->getId() ); ret += ” | weight: ” + std::to_string( edge.second); } } return(ret); } /* Just a bunch of accessors and setters */ int getId() const { return _id; } double getPathWeight() const { return _path_weight; } void setPathWeight(double weight) { _path_weight = weight; } bool is_known() const { return _known; } void set_known() { _known = true; } void unset_known() { _known = false; } void set_path(Vertex *path) { _path = path; } Vertex *get_path() { return _path; } void addEdge(Vertex *vertex, double weight) { _edges[vertex] = weight; } int getEdgeWeight(Vertex *edge) { return _edges[edge]; } unordered_map<Vertex *, double> &getEdges() { return _edges; } void removeEdge(Vertex *vertex) { _edges.erase(vertex); } }; /** * Comparison operators used for sorting, treeing, and queuing * These will provide functions to call when passed vertices to compare */ int operator==(const Vertex &lhs, const Vertex &rhs) { return lhs.getId() == rhs.getId(); } bool operator<(const Vertex &lhs, const Vertex &rhs) { return lhs.getId() < rhs.getId(); } bool operator>(const Vertex &lhs, const Vertex &rhs) { return lhs.getId() > rhs.getId(); } /** * Class used to compare path weights in priority queues */ class PathWeightComparer { public: bool operator()(const Vertex* lhs, const Vertex* rhs) { return (lhs->getPathWeight() > rhs->getPathWeight()); } }; /** * Hashing algorithm must exist in STD namespace * Used by structures like unordered_map (it’s a hash table) */ namespace std { template <> struct hash<Vertex> { // Provide a hash (convert item into integer) std::size_t operator()(const Vertex& item) const { size_t hash_val = 0; hash<int> int_hash{}; // To hash INTs using the STL hash_val = int_hash(item.getId()); // Define hashing algorithm. return hash_val; // Add other hash algs as necessary } }; } #endif
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.