first draft

1 files changed, 50 insertions, 0 deletions

diff --git a/algorithms.py b/algorithms.py
new file mode 100644
index 0000000..75cd3b7
--- /dev/null
+++ b/algorithms.py
@@ -0,0 +1,50 @@
+import math 
+from collections import defaultdict
+
+
+
+def disjoint_forest(nodes, edges):
+    """ Algorithm to test how many components there are 
+        in our graph. There should optimally be few components 
+        and one with the bulk of all the nodes."""
+    ranks = defaultdict(int)
+    parents = {}
+
+    for node in nodes.keys():
+        parents[node] = node
+
+    def find_parent(node):
+        if node != parents[node]:
+            node = find_parent(parents[node])
+        return node
+
+    def union (node1, node2):
+        node1, node2 = find_parent(node1), find_parent(node2)
+        rank1, rank2 = ranks[node1], ranks[node2]
+        if rank1 < rank2:
+            parents[node1] = node2
+        else:
+            parents[node2] = node1
+            if rank1 == rank2:
+                ranks[node1] += 1
+
+    for node, node2 in edges:
+        union(node, node2)
+
+    sets = defaultdict(set)
+    for node, parent in parents.items():
+        parent = find_parent(parent)
+        sets[parent].add(node)
+
+    print("Total Nodes: ", len(nodes))
+    print("Disjoint components: ", len(sets.keys()))
+
+    max_size = 0
+    for set_nodes in sets.values(): # Find biggest component
+        if len(set_nodes) > max_size:
+            max_size = len(set_nodes)
+
+    print("Size of biggest component:", max_size)
+
+    return sets, find_parent
+