TOPOLOGICAL SORTING

In the Directed Acyclic Graph, the Topological sort is a way of the linear ordering of vertices in such a way that for every directed edge (x, y), vertex x will come before y in the ordering.

Topological sorting is possible if and only if the graph has no directed cycles i.e., it is a Directed Acyclic Graph (DAG). There may exist multiple topological orderings for a given DAG. The ordering of the nodes is called topological ordering.

It has been seen that graph having a directed cycle is the only restriction for having a topological sort.

Suppose, if graph G has a directed cycle but it will have no Topological Ordering

Let’s see why?

It is because if a graph G has a directed cycle that means it would have a back-edge, which means when trying to form a topological ordering from at least one of the edges we will have an edge back to one of the earlier edges, or even to the starting edge, in some cases, depending on the graph. Hence topological ordering is only possible on the DAG.

We will talk more about the Topological Sorting of a Directed Acyclic Graph (DAG). But before that let us summarize some important characteristics of Depth First Search (DFS) and Breadth-First Search (BFS):

· We generally use BFS when the target is closer to the source and DFS when the target is far from the source. Using BFS and DFS generally depends on the kind of problem we are trying to solve.

· In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. DFS uses the Stack data structure, in this, the first visited vertices are pushed into the stack and the vertices are explored further. Secondly, if there are no vertices left then visited vertices are popped. There is a possibility of back-tracking in DFS.

Let’s discuss some terms related to Topological Sorting

A Sink is a vertex with no outgoing edges or outbound edges. A DAG has to have at least one sink vertex. In this figure, the arrowhead indicates where the edge is moving to, and E is the sink here.

A Source, on the other hand, is a vertex with no incoming edges. An example of this is edge B because it has no incoming edges and only has outgoing edges.

Application of Topology Sort

  • Build systems

Assuming that there are interdependent DLLs and dependency edges, you can conclude that a successful build is possible if the resulting graph is acyclic. How does the build system decide in which order to build these DLLs? It sorts them topologically.

Let’s consider the following, in order like A->B->C->D, it can start building A (which may only depend on external assemblies already built), then follow the topologically sorted list of assemblies.

  • Determining the order of compilation tasks to perform in make files, data serializations, and resolving symbol dependencies in linkers.
  • Advanced-Packaging Tool (apt-get): In Linux, we use this tool in order to simply install the applications and libraries into our OS. This tool also uses a dependency map to install.
  • Task Scheduling
  • Pre-requisite problems
  • Scheduling jobs from given dependencies among Jobs. For example, if some job requires the dependency of some other job, then we can use topological sorting.
  • Instruction Scheduling

Algorithm

How to find Topological Sort?

Topological Sorting can be implemented by the BFS traversal technique and DFS traversal technique. We’ll discuss both one by one.

BFS Traversal Technique Algorithm to find Topological sort:

· We will maintain an array that will store the ordering of the vertices in topological order. We will follow the below steps:

Step 1: Create an array of lengths equal to the number of vertices.

Step 2: While the number of vertices is greater than 0, repeat 3, 4, 5

Step 3: Take out the vertex whose degree is 0. That means finding a vertex with no incoming edges.

Step 4: We will append the vertices in the Queue and mark these vertices as visited.

Step 5: Now, we will put out all the edges that are originated from that vertex.

DFS Traversal Technique Algorithm to find Topological sort:

Step 1: Select any vertex and start exploring it till you get the sink vertex.

Step 2: Put that sink vertex in the stack and disconnect that vertex from the graph.

Step 3: Backtrack and search for the next sink vertex along the search path.

Step 4: Repeat steps 2, 3 until all the vertices in the graph are visited. (If you’re done with exploring a vertex and wants to choose another you can always start with the smallest number and explore its neighbors first)

Step 5: Then perform the pop operation from the stack and print the popped elements from the stack which will give you the topological ordering.

Manual Illustration and Solving of Topology Sort

Topology sorting is possible for various graphs as long as it’s a Directed Acyclic Graph. Let’s look at the graph drawn above, it is a DAG and further, we will explain the manual illustration of how we will apply topology sort on the DAG.
First, we take a stack and consider all the vertex as unvisited at the beginning, as all the vertex are not explored yet. When we reach each vertex we will explore it using DFS and mark it as visited.

At the start of implementation

for i=0 to nif visited [i]==falsedfs()

First, we start with a vertex, Here, we will start with 0. From there we now have 3 options we can go to vertex 1 or vertex 2 or vertex 6, so let’s go to vertex 1.

Now we check the vertex and here, vertex 1 does not have any outgoing edges. We will push 1 in the stack and backtrack to vertex 0, also vertex 0 and vertex 1 is marked as visited.

Now from vertex 0, we again have 2 options to traverse to vertex 2 or vertex 6 as both this vertex are unvisited. Let’s go to vertex 2 and mark it as visited, from vertex 2 we go to vertex 3 as it has not been visited yet. Now as vertex 3 has no outgoing nodes we will push 3 in the stack and mark it as visited, then we backtrack to vertex 2.

We will backtrack to vertex 2 and as vertex 2 has no outgoing edges to any unvisited vertex we will push 2 in the stack, and backtrack to vertex 0.

From vertex 0 we will explore the unvisited edges which is vertex 6, so we go to vertex 6 as vertex 6 has no outgoing edges we will push 6 in the stack and mark it as visited. Then we backtrack to vertex 0. Now as vertex 0 has no outgoing edges to any unvisited vertex we will push 0 in the stack.

We have 2 more vertexes that are unvisited so the algorithm will select a new node, here we select vertex 4 as vertex 4 has no outgoing edges to any unvisited vertex we will push 4 in the stack and mark it as visited.

Now we will go to vertex 5 and as vertex 5 has no outgoing edges to any unvisited vertex we will push 5 in the stack and mark it as visited.

For new node selection as shown in the example for vertex 4 and vertex 5

for i=0 to nif visited[i]==falsedfs()i=1 visited[1]=Ti=2 visited[2]=Ti=3 visited[3]=T

Once all the vertices have been traversed we will just pop it and give it as our answer for topology sort of this DAG.

Pseudo Code

Let A be an empty listLet all vertices be initially unvisitedwhile there are unvisited vertices:select an unvisited vertex xdfs(x)def dfs(vertex x):mark x as visitedforeach edge x -> yif y is unvisited:dfs(y)add x to head of AA represents the topological order of the DAG

Time And Space Complexity

We consider the following parts to calculate the Time complexity.

1. Determine the indegree for each node: This is O(E) time (where E is the number of edges), since this involves looking at each directed edge in the graph once.

2. Find nodes with no incoming edges: This is a simple loop through all the nodes with some number of constant-time appends. O(V) time (where V is the number of nodes).

3. Add nodes until we run out of nodes with no incoming edges: This loop could run once for every node — O(V) times. In this, we:

· Need to do two constant-time operations for adding a node to the topological ordering.

· Decrementing the indegree for each neighbor of the node we add. In the entire algorithm, we’ll end up doing exactly one decrement for each edge, making this step O(E) time overall.

Altogether, the Worst, Average, Best time complexity is O(E+V)

We consider the following parts to calculate the Space complexity.

1. Calculating Indegrees: This has one entry for each node in the graph, so it’s O(V) space.

2. Calculating nodes with no incoming edges: In a graph with no edges, this would start out containing every node, so it’s O(V) space in the worst case.

3. Topological Ordering: In a graph with no cycles, this will eventually have every node. O(V) space.

Overall, we have three structures and they’re all O(V) space.

Overall space complexity is O(V)

Problem Statment

  • Consider the problem of stirring up a batch of pancakes. We all know that the recipe is pretty simple.
  • Think and note down the ingredients! You need 1 egg, 1 cup of pancake mix, 1 tablespoon oil, and 3/4cup of milk.
  • To start making the pancakes, first, you must heat the griddle and start mixing all the ingredients together and put a spoon of the mix onto a hot griddle. When the pancakes start to have tiny bubbles, you turn them over and let them cook until they are golden brown on the bottom. Before serving your pancakes, you need to add some syrup on top of it. Voila!!!
  • Let’s look for the representation of this process as a graph. (Figure 1)
  • The confusing part about making the pancakes is knowing what to do first and from where to start??
  • You can clearly see in this graph that one might start by heating the griddle or by adding any of the ingredients to the pancake mix.
  • Next, you need to decide the precise order of the steps which is required to make our pancakes that turns to a graph algorithm of the topological sort.
  • You all know that the topological sort takes a directed acyclic graph and the DAG is used to indicate the precedence of events.
  • The below figure shows the depth-first forest constructed by DFS on the pancake-making graph. (Figure 2)
  • Finally, the below graph shows the results of applying the topological sort algorithm to our problem statement. All the ambiguity has been removed and we know the order to be performed for making pancakes!! (Figure 3)

Implementation Code

#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()
{
int v1, v2, n, x;
cout<<”Enter number of edges in the graph:”<<” “;
cin>>n;
Graph g(n);
cout<<”Enter vertices which have an edge between them:”<<” “;
for(int i=0; i<n; i++)
{
cin>>v1>>v2;
g.addEdge(v1,v2);
}
cout << “Following is a Topological Sort of the given “
“graph \n”;
g.topologicalSort();return 0;
}
The output of implementation.

Wondering that DFS and Topological sort can have the same result?

So now let’s discuss that:

Why can’t the DFS result be the same as the topological sort? Need of finding the sink vertex while doing a DFS to have the topological ordering?

In the Depth-first search, we start printing the nodes as we see them but it is not explored yet which means it is still in the Visiting state. So, DFS gives the order in which the nodes enter the Visiting state and not of the Visited state.

On the other hand, the Topological sort gives the order of the nodes or the vertex which is completely explored and marked as Visited. The node is marked Visited only if all of its children have been explored. It is important to remember that we are going to reverse the order in which the nodes are marked Visited so that the child nodes go towards the right.

And there you have it!

Here’s everything you need to know about topology sorting in-depth and implementation of it with a problem statement!!

Hope this blog was helpful to you, kindly share it with your friends and colleagues!

References:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition, The MIT Press and Massachusetts Institute of Technology, 2009, Chapter 22.

https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf

https://geekstocode.com/problems-on-topological-sorting/

https://www.geeksforgeeks.org/cpp-program-for-topological-sorting/

Writers

Gauri Gurav — Shefali Barai — Priyanka Desai.