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
|
import random
from heapq import heappush, heappop
from collections import deque
# A topological sort returns the vertices of a graph sorted in an ascending
# order by the number of incoming edges each vertex has.
#
# A few algorithms for solving this exist, and at the time of this writing, I
# know none. I'm going to focus on two:
# 1. Kahn's
# 2. DFS (TODO)
def count_in_edges(graph):
result = {k: 0 for k in graph.keys()}
for xs in graph.values():
for x in xs:
result[x] += 1
return result
# Kahn's algorithm for returning a topological sorting of the vertices in
# `graph`.
def kahns_sort(graph):
result = []
q = deque()
in_edges = count_in_edges(graph)
for x in [k for k, v in in_edges.items() if v == 0]:
q.append(x)
while q:
x = q.popleft()
result.append(x)
for c in graph[x]:
in_edges[c] -= 1
if in_edges[c] == 0:
q.append(c)
return result
graphs = [
{
0: [],
1: [],
2: [3],
3: [1],
4: [0, 1],
5: [0, 2],
},
{
'A': ['C', 'D'],
'B': ['D', 'E'],
'C': [],
'D': ['F', 'G'],
'E': [],
'F': [],
'G': ['I'],
'H': ['I'],
'I': [],
}
]
print("--- Kahn's --- ")
for graph in graphs:
print(kahns_sort(graph))
|
