diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
commit | fb9380ba268b3cd27372acadb87b14cc96163374 (patch) | |
tree | f65d7fc8d8726499165a0949af39afd1abc8118c /universe/data_structures_and_algorithms/topo-sort.py | |
parent | 15110e6de9f85537c7847267caa35fa068aea001 (diff) | |
parent | 8ad51b24dd8719840aac47134835ea25cfe1b0b8 (diff) |
Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'
git-subtree-dir: universe git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001 git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8
Diffstat (limited to 'universe/data_structures_and_algorithms/topo-sort.py')
-rw-r--r-- | universe/data_structures_and_algorithms/topo-sort.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/universe/data_structures_and_algorithms/topo-sort.py b/universe/data_structures_and_algorithms/topo-sort.py new file mode 100644 index 000000000000..fe295b0279ff --- /dev/null +++ b/universe/data_structures_and_algorithms/topo-sort.py @@ -0,0 +1,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)) |