Given a Directed Acyclic Graph (DAG), print all its topological orderings.

A topological ordering of a directed graph G is a linear ordering of the nodes as `v _{1},v_{2},..,v_{n}` such that all edges point

*forward*: for every edge

`(v`, we have

_{i},v_{j})`i < j`. Moreover, the first node in a topological ordering must be one that has no edge coming into it. Analogously, the last node must be one that has no edge leaving it. A topological order is only possible when the graph has no directed cycles, i.e. if the graph is DAG.

For example, consider below graph

Above graph has many valid topological ordering of vertices like,

7, 5, 3, 1, 4, 2, 0, 6

7, 5, 1, 2, 3, 4, 0, 6

5, 7, 3, 1, 0, 2, 6, 4

3, 5, 7, 0, 1, 2, 6, 4

5, 7, 3, 0, 1, 4, 6, 2

7, 5, 1, 3, 4, 0, 6, 2

5, 7, 1, 2, 3, 0, 6, 4

3, 7, 0, 5, 1, 4, 2, 6

.. and many more

Note that for every directed edge u -> v, u comes before v in the ordering. For example, the pictorial representation of the topological order {7, 5, 3, 1, 4, 2, 0, 6} is:

In the previous post, we have seen how to print topological order of a graph using Depth First Search (DFS) algorithm. We have also seen Kahn’s Topological Sort Algorithm which provides a efficient way to print topological order of a graph. In this post, we will see how to print all possible topological orderings of a DAG.

The idea remains similar to the Kahn's Topological Sort where we find vertices with no incoming edges and removing all outgoing edges from these vertices. We build all possible orderings from left to right, where the vertices with in-degree zero become candidates for the next vertex. This can be done using backtracking where the graph state is restored after processing the selected vertex.

The algorithm can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <iostream> #include <vector> #include <list> using namespace std; // Data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // construct another vector for storing in-degree of the vertices vector<int> indegree; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the adjacency list to N elements of type vector<int> adjList.resize(N); // resize the in-degree vector for N vertices indegree.resize(N); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); // increment in-degree of destination vertex by 1 indegree[edge.dest]++; } } }; // Utility function to print a std::list void printPath(list<int> list) // no ref, no const { while (!list.empty()) { cout << list.front() << ' '; list.pop_front(); } cout << endl; } // Recursive function to find all topological orderings of a given DAG void findAllTopologicalOrders(Graph &graph, auto &path, auto &discovered, int N) { // do for every vertex for (int v = 0; v < N; v++) { // proceed only if in-degree of current node is 0 and // current node is not processed yet if (graph.indegree[v] == 0 && !discovered[v]) { // for every adjacent vertex u of v, reduce in-degree of u by 1 for (int u: graph.adjList[v]) { graph.indegree[u]--; } // include current node in the path and mark it as discovered path.push_back(v); discovered[v] = true; // recur findAllTopologicalOrders(graph, path, discovered, N); // backtrack: reset in-degree information for the current node for (int u: graph.adjList[v]) { graph.indegree[u]++; } // backtrack: remove current node from the path and // mark it as undiscovered path.pop_back(); discovered[v] = false; } } // print the topological order if all vertices are included in the path if (path.size() == N) { printPath(path); } } // Print all topological orderings of a given DAG void printAllTopologicalOrders(Graph &graph) { // get number of nodes in the graph int N = graph.adjList.size(); // create an auxiliary array to keep track of whether vertex is discovered vector<bool> discovered(N); // list to store the topological order list<int> path; // find all topological ordering and print them findAllTopologicalOrders(graph, path, discovered, N); } int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0}, {3, 4}, {5, 1}, {7, 0}, {7, 1} }; // Number of nodes in the graph int N = 8; // create a graph from edges Graph graph(edges, N); // print all topological ordering of the graph printAllTopologicalOrders(graph); return 0; } |

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Nice Article