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, 61 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/topo-sort.py b/users/wpcarro/scratch/facebook/topo-sort.py
new file mode 100644
index 000000000000..874005a01932
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/topo-sort.py
@@ -0,0 +1,61 @@
+import random
+from heapq import heappush, heappop
+from collections import deque
+
+# A topological sort returns the vertices of a graph sorted in an ascending
+# order by the number of incoming edges each vertex has.
+#
+# A few algorithms for solving this exist, and at the time of this writing, I
+# know none. I'm going to focus on two:
+#   1. Kahn's
+#   2. DFS (TODO)
+
+def count_in_edges(graph):
+    result = {k: 0 for k in graph.keys()}
+    for xs in graph.values():
+        for x in xs:
+            result[x] += 1
+    return result
+
+# Kahn's algorithm for returning a topological sorting of the vertices in
+# `graph`.
+def kahns_sort(graph):
+    result = []
+    q = deque()
+    in_edges = count_in_edges(graph)
+    for x in [k for k, v in in_edges.items() if v == 0]:
+        q.append(x)
+    while q:
+        x = q.popleft()
+        result.append(x)
+        for c in graph[x]:
+            in_edges[c] -= 1
+            if in_edges[c] == 0:
+                q.append(c)
+    return result
+
+graphs = [
+    {
+        0: [],
+        1: [],
+        2: [3],
+        3: [1],
+        4: [0, 1],
+        5: [0, 2],
+    },
+    {
+        'A': ['C', 'D'],
+        'B': ['D', 'E'],
+        'C': [],
+        'D': ['F', 'G'],
+        'E': [],
+        'F': [],
+        'G': ['I'],
+        'H': ['I'],
+        'I': [],
+    }
+]
+
+print("--- Kahn's --- ")
+for graph in graphs:
+    print(kahns_sort(graph))