about summary refs log tree commit diff
path: root/data_structures_and_algorithms/topo-sort.py
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))