Kruskal's Algorithm, Implemented in Python

kruskal.md

Output of kruskal(graphExamples["1a"], print_result=True):

EG: 13
AC: 15
AB: 18
DE: 19
BE: 21
FG: 27

Tree total: 113

Output of kruskal(graphExamples["1b"], print_result=True):

BC: 6
DE: 8
AC: 9
EH: 9
BE: 11
GH: 12
EF: 15
HI: 17

Tree total: 87

kruskal.py

from contextlib import suppress
from operator import itemgetter


def kruskal(graph, print_result = False):
    graph = sorted(graph, key=itemgetter(1))  # Sort the connections by value
    tree = []

    for connection in graph:  # Iterate through available connections
        if not creates_circuit(tree, connection, graph):
            tree.append(connection)  # Add the connection to our tree IF no circuits would be created

    if print_result:
        print_tree(tree)

    return tree


# Returns a list of all the nodes in the graph or tree
def get_nodes(graph) -> list:
    return sorted(set((i for x in graph for i in x[0])))


# Returns a boolean of whether adding the specified connection to the tree would create a circuit.
def creates_circuit(tree, conn, graph) -> bool:
    tree = list(tree)
    if len(tree) == 0:
        return False  # Adding a connection can't create a circuit if the tree is empty
    tree.append(conn)

    nodes = get_nodes(tree)
    max_steps = len(graph) - 1

    # Returns a list of points connected to a given point
    def connected_to(point, exclude):
        result = list(
            map(lambda y: y.replace(point, ""),  # Get the other point in the connections
                filter(lambda x: point in x,  # Filter out connections that don't touch the point in question
                       map(itemgetter(0), tree)  # Get the points in the connection
                       )
                ))

        if exclude in result:
            result.remove(exclude)

        return result

    # Returns whether the current path successfully terminates
    def move(prev, curr, steps):
        steps += 1
        with suppress(ValueError):
            nodes.remove(curr)
        # If the number of "steps" is more than the possible connections of the tree, then it must be looping.
        if steps > max_steps:
            return False
        paths = connected_to(curr, prev)
        paths_terminate = [move(curr, path, steps) for path in paths]
        return False not in paths_terminate

    # The tree may have "broken branches", where two or more parts are disconnected.
    # We therefore make sure that all the nodes in our tree are checked over.
    while len(nodes) > 0:
        if not move(None, nodes[0], -1):
            return True
    return False


# Prints a tree and its length
def print_tree(tree):
    for conn, val in tree:
        print("{}: {}".format(conn, val))

    total = sum(map(itemgetter(1), tree))
    print("\nTree total: {}".format(total))

graphExamples = {
    "1a": [
        ("AB", 18),
        ("AC", 15),
        ("BD", 24),
        ("BE", 21),
        ("CD", 31),
        ("CF", 37),
        ("DE", 19),
        ("DF", 32),
        ("DG", 20),
        ("EG", 13),
        ("FG", 27)
    ],

    "1b": [
        ("AB", 12),
        ("AC", 9),
        ("AD", 14),
        ("BC", 6),
        ("BE", 11),
        ("CD", 12),
        ("CE", 13),
        ("DE", 8),
        ("EF", 15),
        ("EG", 13),
        ("EH", 9),
        ("FG", 21),
        ("FI", 25),
        ("GH", 12),
        ("GI", 19),
        ("HI", 17)
    ]
}