Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'

git-subtree-dir: universe
git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001
git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8

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