blob: fe295b0279fffcd44571b27aaf755b9d37c704f6 (
plain) (
blame)
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
|
from fixtures import unweighted_digraph
from collections import deque
# vertices_no_in_edges :: UnweightedDigraph -> Set(Vertex)
def vertices_no_in_edges(g):
"""Return the vertices in graph `g` with no in-edges."""
result = set()
vertices = set(g.keys())
for neighbors in g.values():
result = result.union(neighbors)
return vertices ^ result
# topo_sort :: UnweightedDigraph -> List(Vertex)
def topo_sort(g):
q = deque()
seen = set()
result = []
for x in vertices_no_in_edges(g):
q.append(x)
while q:
vertex = q.popleft()
if vertex in seen:
continue
result.append(vertex)
neighbors = g.get(vertex)
for x in g.get(vertex):
q.append(x)
seen.add(vertex)
return result
print(topo_sort(unweighted_digraph))
|
