Topological Sort

Topological sorting is a classic graph algorithm. Its purpose is to present a linear ordering of vertices composing a directed graph, in such a way that the directions of edges are respected.

Mathematically, a topological sort of a graph G is the ordering of vertices v1 v2 v3 ... vn such that for every edge directed from vi to vj, vi comes before vj in the ordering.

Consider the following directed graph. One possible topological sort would be 0, 1, 2, 3, 4. Another possible ordering is 0, 1, 2, 4, 3.

One practical application of topological sort could be, for example, to find the right order of classes to take as a CS/CSE major here at UC Davis. The classes would be the vertices, and edges would be drawn between classes if one is a pre-requisite of the other. By applying this algorithm, we would find out the right order to take classes!

We will implement this algorithm in its own class. Consider the following class along with its API:

Since topological sort is essentially a graph traversal, we must keep track of the vertices that have been visited. Also, since the algorithm only works for directed graphs, we should also keep track of in-degrees of every vertex. Add private data members and implement the following private helper functions:

Adapt the Breadth-First-Search (BFS) algorithm seen in lecture, in order to implement the topological sort algorithm. The two main modifications are:

The code is implemented as a private method that will be later called in the constructor. The prototype is as follows:

Now, implement the constructor of the TopologicalSort class. The constructor should take in a graph, fill in the in-degree of every vertex in G, and perform Topological sorting. Finally, implement public methods GetOrdering() and HasOrdering(). You may use Graph.h. Write your solution below.

Answer:

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <stdexcept>
#include "Graph.h"

template <typename V, typename E>
class TopologicalSort {
public:
    // Perform topological sort on Graph G
    TopologicalSort(Graph<V, E>& G) {
        FillInDegree(G);
        order = LinearOrdering(G);
    }

// Return true if a valid linear ordering was found
    bool HasOrdering() {
        return !order.empty();
    }

// Return linear ordering of all vertices
    std::vector<typename Graph<V, E>::Vertex> GetOrdering() {
        if (!HasOrdering()) {
            throw std::runtime_error("Graph has a cycle, could not find ordering!");
        }
        return order;
    }

private:
    // Mark visited vertices
    std::map<typename Graph<V, E>::Vertex, bool> visited;
    // Keep track of indegree for each vertex
    std::map<typename Graph<V, E>::Vertex, int> indegree;
    // Store the topological order
    std::vector<typename Graph<V, E>::Vertex> order;

// Mark a vertex as visited
    void SetVisited(typename Graph<V, E>::Vertex v) {
        visited[v] = true;
    }

// Check if a vertex has been visited
    bool IsVisited(typename Graph<V, E>::Vertex v) {
        return visited[v];
    }

// Compute the indegree of each vertex
    void FillInDegree(Graph<V, E>& G) {
        for (auto v : G.vertices()) {
            indegree[v] = 0;
        }

for (auto v : G.vertices()) {
            for (auto w : G.neighbors(v)) {
                indegree[w]++;
            }
        }
    }

// Perform topological sort using BFS
    std::vector<typename Graph<V, E>::Vertex> LinearOrdering(Graph<V, E>& G) {
        std::queue<typename Graph<V, E>::Vertex> q;
        std::vector<typename Graph<V, E>::Vertex> seq;

// Step 1: Add all vertices with indegree 0 to the queue
        for (auto v : G.vertices()) {
            if (indegree[v] == 0) {
                q.push(v);
                SetVisited(v);
            }
        }

// Step 2: BFS traversal adapted for topological sorting
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            seq.push_back(curr);

for (auto w : G.neighbors(curr)) {
                if (IsVisited(w)) {
                    continue;
                }

indegree[w]--;
                if (indegree[w] == 0) {
                    q.push(w);
                    SetVisited(w);
                }
            }
        }

// Step 3: Check if graph contains a cycle
        if (seq.size() != G.num_vertices()) {
            return {};  // Return empty vector if there's a cycle
        }

return seq;
    }
};