0%

Graph topological sort

topological ordering is possible only if the graph is a DAG(Directed Acyclic Graph).

Time Complexity: V + E

  • E is the number of edges
  • V is the number of vertices

Implementation (Kahn’s Algorithm)

Python

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
#!/usr/local/bin/python3

from typing import List
from collections import defaultdict

def topological_sort(vertices: int, edges: List[List[int]]) -> List[int]:
'''
Args:
vertices: 0, 1, 2, .... , vertices-1
edges: (start, end, weight)
Return:
A valid topological ordering
Raise:
ValueError: if there is not a valid topological ordering.
'''
# build graph
graph, indegrees = defaultdict(set), [0] * vertices
for (start, end, weight) in edges:
graph[start].add(end)
indegrees[end] += 1
# find vertices have zero indegree
zero_degrees = [vertex for vertex, indegree in enumerate(indegrees) if indegree == 0]
ordering = []
while zero_degrees:
vertex = zero_degrees.pop()
ordering.append(vertex)
for successor in graph[vertex]:
indegrees[successor] -= 1
if indegrees[successor] == 0:
zero_degrees.append(successor)
if len(ordering) != vertices:
raise ValueError('There is not a valid topological ordering')
return ordering


ordering = topological_sort(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]])
print('->'.join([str(vertex) for vertex in ordering]))

Test Case

1
2
3
4
5
6
7
8
9
10
11
          +-+                  +-+
+-2----->+1| |4+<--+
| +++ +++ |
+++ | +-+ ^ |
|0| +--3----->+3+----3---+ |
+++ +-+ |
| +-+ |
+--5---->+2+----------------10------+
+-+

0->2->1->3->4

Application in Shortest Path Finding

topological sort can also be used to find shortest path of a DAG in liner time.

Other algorithms for shortest path finding

Time Complexity: V + E

  • E is the number of edges
  • V is the number of vertices

Implementation

Python

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
def shortest_path_finding(vertices: int, edges: List[List[int]], origin: int, destination: int):
'''
print shortest path from origin to destination
Args:
vertices: number of vertices. First vertex is 0.
edges: list of (start, end, weight)
origin: -
destination: -
Raise:
ValueError: if destination is not reachable from origin
'''
# build graph
graph = defaultdict(dict)
max_dist = 0
for (start, end, weight) in edges:
graph[start][end] = weight
max_dist += weight
# takes V + E
ordering = topological_sort(vertices, edges)
# remove most unreachable vertices
ordering = ordering[ordering.index(origin):]
# prepare data
dist, predecessor = [max_dist+1] * vertices, [None] * vertices
dist[origin] = 0
# relax edges
for vertex in ordering:
for successor in graph[vertex]:
# shorter path is found
if dist[vertex] + graph[vertex][successor] < dist[successor]:
dist[successor] = dist[vertex] + graph[vertex][successor]
predecessor[successor] = vertex
# build path
cur, path = destination, []
while cur != origin and predecessor[cur] is not None:
path.append(cur)
cur = predecessor[cur]
if cur != origin:
raise ValueError(f'{destination} is not reachable from {origin}')
path = [origin] + path[::-1]
print('->'.join([str(vertex) for vertex in path]))

Test Case

1
2
3
4
5
6
7
8
9
          +-+                  +-+
+-2----->+1| |4+<--+
| +++ +++ |
+++ | +-+ ^ |
|0| +--3----->+3+----3---+ |
+++ +-+ |
| +-+ |
+--5---->+2+----------------10------+
+-+
1
2
3
4
5
6
7
8
9
10
11
testcases = [(0, 4), (1, 4), (2, 0), (2, 3)]
for testcase in testcases:
try:
shortest_path_finding(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], *testcase)
except Exception as e:
print('Not reachable')

0->1->3->4
1->3->4
Not reachable
Not reachable