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))
