📌 A topological sort or topological ordering of a DAG is a linear ordering of vertices such that:

  • for every directed edge $u \to v$, $u$ comes before $v$ in it.

For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

âš¡ For a Graph $G$:

  • Topological sort is possible $\iff$ $G$ has no directed cycles $\iff$ $G$ is a DAG.

💎 Any DAG has at least one topological ordering.

🚀 Algorithms are known for constructing a topological ordering of any DAG in linear time $\text{O}(V + E)$.

Directed Acyclic Graph A topological ordering of a DAG: every edge in ordering goes from earlier (upper left) to later (lower right). A directed graph is acyclic $\iff$ if it has a topological ordering.

Examples

🔦 Example 1

Topologic Sorting

The graph shown above has many valid topological sorts, including:

  • 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
  • 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
  • 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
  • 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
  • 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
  • 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

🔦 Example 2

Input:

adj[][] = [[1], [2], [], [2, 4], []]

img.png Image credits: GeeksForGeeks.org

Output:

[0, 3, 1, 4, 2]

### Explanation

Since vertices $0$ and $3$ do not have any incoming edges from any other vertex, they appear first.

Next, $1 \leftarrow 0$ ($1$ depends only on $0$), so it comes after $0$.

Similarly, $4 \leftarrow 3$, placing it after $3$.

Finally, vertex $2$ depends on both vertices $1$ and $3$, so it appears after both of them in the ordering.

Application

The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies.

The jobs are represented by vertices, and if there is an edge $x \to y$ then job $x$ must be completed before job $y$ can be started

(for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs.

Other application is dependency resolution. Each vertex is a package and each edge is a dependency of package $a$ on package $b$. Then topological sorting will provide a sequence of installing dependencies in a way that every next dependency has its dependent packages to be installed in prior.

Implementations

  • 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

    # G[i][j] indicates whether the path from the i-th node to the j-th node exists or not.
# NOTE: The graph must be Directed-Acyclic
from collections import deque

G = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 0, 0],
    [1, 1, 0, 0, 0, 0],
]


inDegrees = [0 for _ in range(len(G))]
Q = deque()
iter = 0

print('Calculating in-degrees for each Node...')

for currNode in range(0, len(G)):
    for currNodeNeighbor in range(0, len(G)):
        if G[currNode][currNodeNeighbor]:
            inDegrees[currNodeNeighbor] += 1
            # print(f"{currNode} -> {currNodeNeighbor}")

print('Done.In - Degrees are: [ ${String(inDegrees)}]')
print('Initializing queue with all the sources (nodes with no incoming edges)')

for node, inDegree in enumerate(inDegrees):
    if not inDegree:
        print(f"{node} is a source")
        Q.append(node)

print(f"Done. Initial State of Queue: {Q}")

while Q:
    print("Iteration #${iter}. Queue state: [ ${String(Q)} ]")

  • 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

    // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not. NOTE: The graph must be Directed-Acyclic
const G = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [1, 0, 0, 1, 0, 0],
  [1, 1, 0, 0, 0, 0],
];

const inDegrees = Array(...Array(G.length)).map(Number.prototype.valueOf, 0); // create an Array of G.length number of 0s
const Q = [];
let iter = 0;
let i;

console.log('Calculating in-degrees for each Node...');

for (let currNode = 0; currNode < G.length; currNode++) {
  for (let currNodeNeighbor = 0; currNodeNeighbor < G.length; currNodeNeighbor++) {
    if (G[currNode][currNodeNeighbor]) {
      
      inDegrees[currNodeNeighbor]++;
      
    }
  }
}

console.log(`Done. In-Degrees are: [ ${String(inDegrees)} ]`);
console.log('');

console.log('Initializing queue with all the sources (nodes with no incoming edges)');

inDegrees.map((indegrees, node) => {
  
  if (!indegrees) {
    
    console.log(`${node} is a source`);
    
    Q.push(node);
  }
  
});

console.log(`Done. Initial State of Queue: [ ${String(Q)} ]`);
console.log('');

// begin topological sort (kahn)
while (Q.length > 0) {
  
  console.log(`Iteration #${iter}. Queue state: [ ${String(Q)} ]`);
  
  const currNode = Q.shift();

  for (i = 0; i < G.length; i++) {
    if (G[currNode][i]) {
      
      inDegrees[i]--;

      if (!inDegrees[i]) {
        
        console.log(`${i}'s in-degree is now 0. Enqueuing ${i}`);
        
        Q.push(i);
      }
    }
  }

  console.log(`In-degrees are: [${String(inDegrees)} ]`);
  console.log('-------------------------------------------------------------------');

  iter++;
}

References