topological_sort.cpp File Reference

Topological Sort Algorithm More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <vector>

Include dependency graph for topological_sort.cpp:

Go to the source code of this file.

Classes
class	graph::topological_sort::Graph
	Class that represents a directed graph and provides methods for manipulating the graph. More...

Namespaces
namespace	graph
	Graph Algorithms.
namespace	topological_sort
	Topological Sort Algorithm.

Functions
void	graph::topological_sort::dfs (int v, std::vector< int > &visited, const std::vector< std::vector< int > > &graph, std::stack< int > &s)
	Function to perform Depth First Search on the graph.
std::vector< int >	graph::topological_sort::topologicalSort (const Graph &g)
	Function to get the topological sort of the graph.
static void	test ()
	Self-test implementation.
int	main ()
	Main function.

Detailed Description

Topological Sort Algorithm

Topological sorting of a directed graph is a linear ordering or its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the oredering.

A topological sort is possible only in a directed acyclic graph (DAG). This file contains code of finding topological sort using Kahn's Algorithm which involves using Depth First Search technique

Definition in file topological_sort.cpp.

Function Documentation

dfs()

void graph::topological_sort::dfs	(	int	v,
		std::vector< int > &	visited,
		const std::vector< std::vector< int > > &	graph,
		std::stack< int > &	s )

Function to perform Depth First Search on the graph.

Parameters

v	Starting vertex for depth-first search
visited	Array representing whether each node has been visited
graph	Adjacency list of the graph
s	Stack containing the vertices for topological sorting

Definition at line 79 of file topological_sort.cpp.

                                                                   {
    visited[v] = 1;
    for (int neighbour : graph[v]) {
        if (!visited[neighbour]) {
            dfs(neighbour, visited, graph, s);
        }
    }
    s.push(v);
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 186 of file topological_sort.cpp.

           {
    test();  // run self test implementations
    return 0;
}

test()

void test ( )

static

Self-test implementation.

Returns

void

Definition at line 126 of file topological_sort.cpp.

                   {
    // Test 1
    std::cout << "Testing for graph 1\n";
    int n_1 = 6;
    graph::topological_sort::Graph graph1(n_1);
    graph1.addEdge(4, 0);
    graph1.addEdge(5, 0);
    graph1.addEdge(5, 2);
    graph1.addEdge(2, 3);
    graph1.addEdge(3, 1);
    graph1.addEdge(4, 1);
    std::vector<int> ans_1 = graph::topological_sort::topologicalSort(graph1);
    std::vector<int> expected_1 = {5, 4, 2, 3, 1, 0};
    std::cout << "Topological Sorting Order: ";
    for (int i : ans_1) {
        std::cout << i << " ";
    }
    std::cout << '\n';
    assert(ans_1 == expected_1);
    std::cout << "Test Passed\n\n";
 
    // Test 2
    std::cout << "Testing for graph 2\n";
    int n_2 = 5;
    graph::topological_sort::Graph graph2(n_2);
    graph2.addEdge(0, 1);
    graph2.addEdge(0, 2);
    graph2.addEdge(1, 2);
    graph2.addEdge(2, 3);
    graph2.addEdge(1, 3);
    graph2.addEdge(2, 4);
    std::vector<int> ans_2 = graph::topological_sort::topologicalSort(graph2);
    std::vector<int> expected_2 = {0, 1, 2, 4, 3};
    std::cout << "Topological Sorting Order: ";
    for (int i : ans_2) {
        std::cout << i << " ";
    }
    std::cout << '\n';
    assert(ans_2 == expected_2);
    std::cout << "Test Passed\n\n";
 
    // Test 3 - Graph with cycle
    std::cout << "Testing for graph 3\n";
    int n_3 = 3;
    graph::topological_sort::Graph graph3(n_3);
    graph3.addEdge(0, 1);
    graph3.addEdge(1, 2);
    graph3.addEdge(2, 0);
    try {
        graph::topological_sort::topologicalSort(graph3);
    } catch (std::invalid_argument& err) {
        assert(std::string(err.what()) == "cycle detected in graph");
    }
    std::cout << "Test Passed\n";
}

topologicalSort()

std::vector< int > graph::topological_sort::topologicalSort

(

const Graph &

g

)

Function to get the topological sort of the graph.

Parameters

g	Graph object

Returns

A vector containing the topological order of nodes

Definition at line 95 of file topological_sort.cpp.

                                               {
    int n = g.getNumNodes();
    const auto& adj = g.getAdjacencyList();
    std::vector<int> visited(n, 0);
    std::stack<int> s;
 
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, adj, s);
        }
    }
 
    std::vector<int> ans;
    while (!s.empty()) {
        int elem = s.top();
        s.pop();
        ans.push_back(elem);
    }
 
    if (ans.size() < n) {  // Cycle detected
        throw std::invalid_argument("cycle detected in graph");
    }
    return ans;
}