Introduction to Topological Sorting

Estimated Time

1 hour

Introduction

Introduction video for DAGs and Topological Sort

Prerequisites of the Experiment

Overview of the Experiment

  • The aim of this experiment is to understand the Topological Sort algorithms - Depth First Search and Kahn's algorithm along with their time and space complexity.
  • The experiment features a series of modules with video lectures, interactive demonstrations, simulations, hands-on practice exercises and quizzes for self analysis.

Learning Objectives of the Experiment

In this experiment, we will be able to do the following:

  • Given a directed acyclic graph of numbers, generate a topological ordering of numbers by applying the algorithms.
  • Demonstrate knowledge of time complexity of both algorithms by counting the number of operations involved in each iteration.

Experiment Modules & their Weightage

Module Weightage Expectation
Pre-test 10% Solve All Questions
Topological Sort: DFS Algorithm 20% Understand the DFS algorithm
Topological Sort: Kahn's Algorithm 20% Understand the Kahn's algorithm
Analysis 25% Understand the time and space complexity
Post-test 25% Solve all Questions

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-Test

  • Pretest includes questions on DAG, time complexity and space complexity.
  • If you want to revise these topics before taking the quiz, go through the Recap module first.
  • Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quick look at DAGs, Time and Space Complexity

Trees and Graphs

  • Tree is an abstract data structure that simulates a hierarchical tree structure, with a root and subtrees of children with a parent node, represented as a set of linked nodes.
  • A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
  • Graph with all vertices connectes is a connected graph and a tree that covers all vertices in called spanning tree.
  • Graphs with edges that have weights are called weighted graphs. Graphs with directions is known as a directed graph.

Types of graphs

Picture shows types of graphs

Depth First Search (DFS)

A Depth First Search (DFS) is an algorithm for traversing a finite graph. DFS visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. A stack (often the program's call stack via recursion) is generally used when implementing the algorithm.

What is a DAG?

A Directed Acyclic Graph (DAG) is a graph that is directed and without cycles connecting the other edges. This means that it is impossible to traverse the entire graph starting at one edge. The edges of the directed graph only go one way.

Time and Space Complexity

Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

A Quiz with Multiple Choice Questions

Q1. Which of these best describes a graph?

(A) A linear data structure with finite nodes and edges

(B) A non-linear data structure consisting of nodes and edges

(C) A data structure which has infinite nodes and edges

(D) All of the above

A Graph is a non-linear data structure consisting of a finite set of vertices(or nodes) and set of edges which connect a pair of nodes.

Q2. How many number of edges need to be present in a complete graph having n vertices?

(A) (n*(n-1))/2

(B) (n*(n+1))/2

(C) n

(D) None of these

Taking a general example such as inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array, when you will need to move n elements

Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

(A) X will always be a better choice for small inputs

(B) X will always be a better choice for large inputs

(C) Y will always be a better choice for small inputs

(D) X will always be a better choice for all inputs

Performance could be similar for small inputs, but definitely better for larger inputs

Q4. int i, j, k = 0;
for (i = n / 2; i <= n; i++){
for (j = 2; j <= n; j = j * 2){
k = k + n / 2; }
}
What is the time complexity for the above code?

(A) O(n)

(B) O(N + M) time, O(N + M) space

(C) O(N + M) time, O(1) space

(D) O(N * M) time, O(N + M) space

The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

Q5. ans = 0;
for (i = n; i >= 1; i /= 2){
for (j = 1; j <=m ; j *=2 ){
ans += (i * j);
}
}
What is the time complexity for the above code?

(A) O(n*m)

(B) O(logmlogn)

(C) O(mlogn)

(D) O(nlogm)

The first for loop runs for logn times, each of the loop runs for logm. So total it runs for O(logmlogn) time.

Topological Sort

Estimated Time

15 min

Video Demo for Topological Sort

Demo Video

Learning Objectives of this Module

In this module we will learn:

  • What is Topological Sort?
  • Why topological sort is applicable for DAG?
  • Topological Sort through DFS

Basic View

What is Topological Sort?

Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices v1,v2,...,vn in such a way, that if there is an edge directed towards vertex vj from vertex v i, then vi comes before vj. There are multiple topological sortings possible for a graph. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Example of Topological Sort

Image for example of topological sort should be displayed here.

Why topological sort only for DAG?

It is clear that a topological ordering is not possible if the graph has a cycle, since for two vertices v and w on the cycle, v precedes w and on contrary even w precedes v, so it is not meaningful to say which preceeds the other. So topological sorting can be achieved for only directed and acyclic graphs.

A DAG 'G' has at least one vertex with in-degree 0 and one vertex with out-degree 0.

Proof: A DAG does not contain a cycle which means that all paths will be of finite length. Now let S be the longest path from u(source) to v(destination). Since S is the longest path there can be with no incoming edge to u and no outgoing edge from v, if this situation had occurred then S would not have been the longest path => indegree(u) = 0 and outdegree(v) = 0

Through DFS

Algorithm

We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Step-wise Representation of finding topological sort through DFS

Image showing Step-wise Representation of finding topological sort through DFS should be displayed here.

Kahn's Algorithm

Estimated Time

15 min

Video Demo for Kahn's Algorithm

Demo Video

Learning Objectives of this Module

In this module we will learn about:

  • Basic Concept of Kahn's algorithm
  • Demo of Kahn's algorithm
  • Practice of Kahn's algorithm
  • Exercise of Kahn's algorithm

Basic Concept & Algorithm

Algorithm

Steps involved in finding the topological ordering of a DAG:

  • Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
  • Step-2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)
  • Step-3: Remove a vertex from the queue (Dequeue operation) and then increment count of visited nodes by 1. Decrease in-degree by 1 for all its neighbouring nodes. If in-degree of a neighbouring node is reduced to zero, then add it to the queue.
  • Step 4: Repeat Step 3 until the queue is empty.
  • Step 5: If count of visited nodes is not equal to the number of nodes in the graph, then the topological sort is not possible for the given graph.

Step-wise Representation of Kahn's Algorithm

Image showing Step-wise Representation of Kahn's Algorithm should be displayed here.

What is indegree and how to find it?

What is meant by indegree?

It is simply the count of number of edges pointed towards the vertex from other vertices.

How to find indegree?

Traverse the array of edges and simply increase the counter of the destination node by 1.
Algorithm:
for each node in Nodes
  indegree[node] = 0;
for each edge(src,dest) in Edges
  indegree[dest]++;

Video Demo for Kahn's Algorithm

Demo Video

Kahn's Algorithm: Demo

Kahn's Algorithm Demo

Requires Demo Artefact

Kahn's Algorithm: Practice

Kahn's Algorithm Practice

Recquires Practice Artefact

Kahn's Algorithm: Exercise

Kahn's Algorithm Exercise

Recquires Exercise Artefact

Analysis of Topological Sort

Estimated Time

10 minutes

Learning Objectives of this Module

In this module, we will be learning about :

Time and Space complexity : We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.

Time and Space Complexity of Topological Sort

Running Time of Topological Sort

Time complexity for Kahn's algorithm:

Lets assume that we are ordering a graph with V vertices and E edges using Topological Sort.

  • While traversing the nodes, when we come across a node (Let it be X), we need to decrease the indegree of all the nodes which have the edges from the node X. So time complexity for decreasing all the indegree of the connected nodes is O(|E|).
  • In Topological sort, we run across all edges, which takes O(|V|) time. Hence overall time complexity becomes O(|V|+|E|).

Time complexity for Topological sort through DFS:

Since it is modification of DFS, time complexity doesn't alter. Time complexity is O(|V|+|E|).

Space Complexity of Toplological Sort

Space complexity for Kahn's Algorithm:

While enqueuing a node, we need some extra space to store temporary values. Other than that, the ordering can be done in-place. Hence space complexity is O(|V|).

Space complexity for Topological Sort through DFS:

Since we need to store the sequence of nodes into a stack, we need some extra space. Other than that, the ordering can be done in-place. Hence space complexity is O(|V|).

Post Test of the Experiment

Estimated Time

10 minutes

Instructions for Quiz

Post Test includes questions on concepts from the entire experiment. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Post test quiz

Q1. Which of the following best describes the topological order?

(A) If a digraph has no directed cycle it does have a topological order otherwise it might or might not have a topological order

(B) If a digraph has at least one directed cycle it has no topological order otherwise it might or might not have a topological order

(C) A directed graph has a topological order if and only if it has no directed cycle

(D) None of these

As it is explained earlier. Please refer topological sort basic view.

Q2. Assume you use a digraph to schedule a set of tasks, that have precedence constraints. In such a graph, the tasks should be the ________________ and the constraints should be the ______________.

(A) vertices,bedges

(B) edges, vertices

(C) vertices, vertices

(D) edges, edges

It is obvious that tasks must be vertices and constraints must be edges, since in order to perform tasks, we need to complete constraints

Q3. Topological Sort is equivalent to which of the traversals in trees?

(A) Pre-order traversal

(B) Post-order traversal

(C) In-order traversal

(D) None of these

In pre-order traversal of trees, we process the root first and then the child from left to right.

Q4. Topological sort of a Directed Acyclic graph is ________.

(A) Always unique

(B) Always Not unique

(C) Sometimes unique and sometimes not unique

(D) None of these

As it is explained earlier. Please refer topological sort basic view.

Q5. Time Complexity of Topological Sorting is _______. (V – number of vertices, E – number of edges)

(A) O(|E|)

(B) O(|V|)

(C) O(|V| + |E|)

(D) None of these

O(|V|+|E|) as it is explained earlier. Please refer topological sort analysis.

Further Readings and References of the Experiment

Explore More About Topological Sort

You can explore more about Topological Sort Experiment through following resources:


Useful Links: Quizzes: