Topological Order

[Qingquan-Li]

In college, before taking a particular course, students, usually, must take all its prerequisite courses, if any. For example, before taking the Programming II course, the student must take the Programming I course. However, certain courses can be taken independently of each other. The courses within a department can be represented as a directed graph. A directed edge from, say vertex u to vertex v means the course represented by the vertex u is a prerequisite of the course represented by the vertex v. The Topological Order algorithm can be used to output the vertices of a directed graph in such a sequence.

Topological Ordering

Definition

Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering.

Properties

• Topological ordering is possible if and only if the graph has no directed cycles, i.e., it must be a Directed Acyclic Graph (DAG).
• There can be more than one topological ordering for a given graph.

Example 1

A --> B
|     |
v     v
C --> D

Possible Topological Orderings for this directed acyclic graph:

1. A, B, C, D
2. A, C, B, D

Both are valid as they satisfy the rule that for every directed edge UV, U comes before V in the ordering.

Example 2

   B
  ^ \
 /   v
A --> C --> D

Possible Topological Orderings for this directed acyclic graph:

1. A, B, C, D
2. A, C, B, D

Both are valid as they satisfy the rule that for every directed edge UV, U comes before V in the ordering.

Applications

• Scheduling problems where some tasks must be done before others.
• Compilation order in programming where some modules depend on others.
• Resolving symbol dependencies in linkers in computer programming.

Algorithms

• The most common way to find a topological sort is using Depth-First Search (DFS). The algorithm involves:
  • Marking each vertex as unvisited initially.
  • Performing a DFS on each unvisited vertex.
  • Each time a DFS finishes on a vertex, that vertex is added to a stack.
  • The stack represents the topological order once all vertices have been processed.
• While DFS-based topological sorting is more common and easier to implement, BFS-based topological ordering (Kahn's Algorithm) is essential for certain types of graph problems, particularly where parallelism or level-wise processing is required.

Depth-First Search versus Breadth-First Search

(source: https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9)

• The key difference is that DFS goes as deep as possible into the graph's branches before backtracking, while BFS explores all neighbors at one level before moving deeper.
• DFS is typically implemented using recursion or a stack, whereas BFS is implemented using a queue.

Breadth-First Topological Ordering

Definition

It's a variant of topological sorting where Breadth-First Search (BFS) is used instead of DFS. This approach uses the concept of in-degree of nodes.

Algorithm (Kahn's Algorithm)

• Calculate in-degree (number of incoming edges) for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
• Pick all the vertices with in-degree as 0 and add them to a queue.
• Remove a vertex from the queue (decrementing in-degrees of all adjacent vertices).
• Repeat until the queue is empty.
• Each time a vertex is dequeued, it's appended to the topological order and the count of visited nodes is incremented.
• If the count of visited nodes is not equal to the number of vertices, then the topological sort is not possible for the given graph (it indicates a cycle).

Properties

• It finds a level-wise ordering where nodes in the same level can be processed parallelly or simultaneously.
• Suitable for large graphs where depth-first traversal might lead to stack overflow.

Applications

Same as general topological sorting but more efficient in certain scenarios, especially in distributed systems or parallel computing environments.