algorithms.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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