subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 31 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/topo-sort.py b/users/wpcarro/scratch/data_structures_and_algorithms/topo-sort.py
new file mode 100644
index 000000000000..fe295b0279ff
--- /dev/null
+++ b/users/wpcarro/scratch/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))