In this task you’ll implement Topographical Sort. This sort algorithm is laid ou

Question

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.

######### Graph.h #########

#ifndef GRAPH_H
#define GRAPH_H

#include
#include
#include
#include
#include
#include
#include
#include

#include "Vertex.h"

using namespace std;

class Graph
{
   vector _vertices;       // All vertices in the graph (vertex id == index)
   int _last_startingID = -1;

public:
   // Remove all vertices
   void clear() {
       _vertices.clear();
   }

   // Number of vertices in our graph
   int size() {
       return _vertices.size();
   }

   /**
   * Parses a single in from a dot file
   */
   void parseDotfileLine( string line ) {
       smatch matched;
       regex newSubGraph ("\s*(\S+)\s*->\s*(\S+)\s*\[.*?weight="*(\S+?)"*\s*\]\;");

       if( regex_match( line, matched, newSubGraph ) ) {
           string strconv = matched[1];
           int srcid = ::atof(strconv.c_str());
           strconv = matched[2];
           int destid = ::atof(strconv.c_str());
           strconv = matched[3];
           double weight = ::atof(strconv.c_str());
           //cout << "SrcID: " << srcid << " | DestID: " << destid << " | Edge Weight: " << weight << endl;

           // Grow set of vertices if new high id is inserted or connected to
           int growVerts = max(srcid, destid);
           for( int i = _vertices.size(); i <= growVerts; i++ ) {
               Vertex* newVert = new Vertex(i);       // Allocate the new vertex
               _vertices.push_back( newVert );       // Add vertex to the end of the list
           }
           _vertices[srcid]->addEdge(_vertices[destid], weight);
       }
   }

   /**
   * Loads a single Graphviz-(limited) formatted dot file with a graph
   */
   void loadDotFile( string filename ) {
       cout << " [d] Loading dot file: " << filename;
       ifstream ifs( filename );
       string instr;
       while (getline(ifs, instr)) {
           parseDotfileLine( instr );
       }
       cout << " - Done." << endl;
   }

   /**
   * Returns stringified version of graph for viewing
   */
   string to_string( bool with_edges = false ) {
       string ret = "";
       for( auto vert : _vertices ) {
           ret += vert->to_string( with_edges ) + " ";
       }
       return ret;
   }

};

#endif

########### 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 <<""
" _.-'`'-._ "
" .-' _ '-. "
" `-.__ `\_.-' "
" | `-``\| "
" jgs `-.....-A "
" # "
" # ";
   cout << endl;
   cout << " Oh, and you should probably run 'make test' to test your program. "
" To run the mouse brain graph, use 'make bigtest', which takes about 15 sec for me. "
" You'll find images of the graphs we're using in: "
" bookGraph.png "
" MouseBrainGraph.png (currently being built - fingers crossed) "
" "
" Both built using: neato -Tpng bookGraph.dot -o bookGraph.png "
" Both built using: neato -Tpng MouseBrainGraph.dot -o MouseBrainGraph.png ";
}

/**
* 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();
   }
}

###### 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 += " | k: "; ( _known ) ? ret += "T" : ret += "F";
       ret += " | pw: " + std::to_string(_path_weight);
       ret += " | p: ";
       if( _path ) {
           ret += std::to_string( _path->getId() );
       } else {
           ret += "null";
       }

       if( with_edges ) {
       ret += " | Edges:";
           for( auto edge : _edges ) {
               ret += " 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

######### graph file ########

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"];
        }

Explanation / Answer

#ifndef GRAPH_H
#define GRAPH_H

#include
#include
#include
#include
#include
#include
#include
#include

#include "Vertex.h"

using namespace std;

class Graph
{
   vector _vertices;       // All vertices in the graph (vertex id == index)
   int _last_startingID = -1;

public:
   // Remove all vertices
   void clear() {
       _vertices.clear();
   }

   // Number of vertices in our graph
   int size() {
       return _vertices.size();
   }

   /**
   * Parses a single in from a dot file
   */
   void parseDotfileLine( string line ) {
       smatch matched;
       regex newSubGraph ("\s*(\S+)\s*->\s*(\S+)\s*\[.*?weight="*(\S+?)"*\s*\]\;");

       if( regex_match( line, matched, newSubGraph ) ) {
           string strconv = matched[1];
           int srcid = ::atof(strconv.c_str());
           strconv = matched[2];
           int destid = ::atof(strconv.c_str());
           strconv = matched[3];
           double weight = ::atof(strconv.c_str());
           //cout << "SrcID: " << srcid << " | DestID: " << destid << " | Edge Weight: " << weight << endl;

           // Grow set of vertices if new high id is inserted or connected to
           int growVerts = max(srcid, destid);
           for( int i = _vertices.size(); i <= growVerts; i++ ) {
               Vertex* newVert = new Vertex(i);       // Allocate the new vertex
               _vertices.push_back( newVert );       // Add vertex to the end of the list
           }
           _vertices[srcid]->addEdge(_vertices[destid], weight);
       }
   }

   /**
   * Loads a single Graphviz-(limited) formatted dot file with a graph
   */
   void loadDotFile( string filename ) {
       cout << " [d] Loading dot file: " << filename;
       ifstream ifs( filename );
       string instr;
       while (getline(ifs, instr)) {
           parseDotfileLine( instr );
       }
       cout << " - Done." << endl;
   }

   /**
   * Returns stringified version of graph for viewing
   */
   string to_string( bool with_edges = false ) {
       string ret = "";
       for( auto vert : _vertices ) {
           ret += vert->to_string( with_edges ) + " ";
       }
       return ret;
   }

};

#endif

########### 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 <<""
" _.-'`'-._ "
" .-' _ '-. "
" `-.__ `\_.-' "
" | `-``\| "
" jgs `-.....-A "
" # "
" # ";
   cout << endl;
   cout << " Oh, and you should probably run 'make test' to test your program. "
" To run the mouse brain graph, use 'make bigtest', which takes about 15 sec for me. "
" You'll find images of the graphs we're using in: "
" bookGraph.png "
" MouseBrainGraph.png (currently being built - fingers crossed) "
" "
" Both built using: neato -Tpng bookGraph.dot -o bookGraph.png "
" Both built using: neato -Tpng MouseBrainGraph.dot -o MouseBrainGraph.png ";
}

/**
* 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();
   }
}

###### 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 += " | k: "; ( _known ) ? ret += "T" : ret += "F";
       ret += " | pw: " + std::to_string(_path_weight);
       ret += " | p: ";
       if( _path ) {
           ret += std::to_string( _path->getId() );
       } else {
           ret += "null";
       }

       if( with_edges ) {
       ret += " | Edges:";
           for( auto edge : _edges ) {
               ret += " 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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.