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.

#ifndef GRAPH_H
#define GRAPH_H

#include <queue>
#include <string>
#include <fstream>
#include <vector>
#include <regex>
#include <algorithm>
#include <list>
#include <stack>

#include "Vertex.h"

using namespace std;

class Graph
{
   vector<Vertex*> _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

Explanation / Answer

#include<iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V;
list<int> *adj;

void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V);
void addEdge(int v, int w);
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int> &Stack)
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
Stack.push(v);
}
void Graph::topologicalSort()
{
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
Graph g(6);
g.addEdge(4, 2);
g.addEdge(6, 0);
g.addEdge(3, 0);
cout << "Following is a Topological Sort of the given graph ";
g.topologicalSort();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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