<commit_before>""" Provides a solution (`solve`) to the EMST problem. """

from .graph import Graph

# Euclidean Minimum Spanning Tree (MST) algorithm
#
# input: a list of n Point objects
#
# output: a list of (p, q) tuples, where p and q are each input Point
# objects, and (p, q) should be connected in a minimum spanning tree
# of the input points
def solve(points):
    """ Solves the EMST problem """
    # it's not a list
    if not isinstance(points, list):
        raise TypeError("solve expects a list of n Point objects, received %s" % points)

    graph = Graph(points)

    if graph.num_edges() < 1:
        return []

    edges = graph.edges
    num_points = graph.num_points()
    start = edges.pop()
    spanned = set([start])
    solution = [(start.left, start.right)]

    print("beginning main loop")
    while len(spanned) < num_points - 1:
        smallest_edge = None

        for spanned_edge in spanned:
            print("inner loop (spanned)")
            for candidate_edge in edges:
                print("inner loop (candidate_edge)")
                # if the candidate isn't connected to our lil spanned set,
                # ignore it
                if not candidate_edge.connected_to(spanned_edge.left) \
                        and not candidate_edge.connected_to(spanned_edge.right):

                    continue

                if smallest_edge is None or candidate_edge.weight() < smallest_edge.weight():
                    smallest_edge = candidate_edge

        print("extending edge %s" % smallest_edge)
        edges.remove(smallest_edge)
        spanned.add(smallest_edge)
        solution.append((smallest_edge.left, smallest_edge.right))

    return solution
<commit_msg>Add note about Graph doing work in init<commit_after>""" Provides a solution (`solve`) to the EMST problem. """

from .graph import Graph

# Euclidean Minimum Spanning Tree (MST) algorithm
#
# input: a list of n Point objects
#
# output: a list of (p, q) tuples, where p and q are each input Point
# objects, and (p, q) should be connected in a minimum spanning tree
# of the input points
def solve(points):
    """ Solves the EMST problem """
    # it's not a list
    if not isinstance(points, list):
        raise TypeError("solve expects a list of n Point objects, received %s" % points)

    # NOTE: this does some initialization work
    graph = Graph(points)

    if graph.num_edges() < 1:
        return []

    edges = graph.edges
    num_points = graph.num_points()
    start = edges.pop()
    spanned = set([start])
    solution = [(start.left, start.right)]

    print("beginning main loop")
    while len(spanned) < num_points - 1:
        smallest_edge = None

        for spanned_edge in spanned:
            print("inner loop (spanned)")
            for candidate_edge in edges:
                print("inner loop (candidate_edge)")
                # if the candidate isn't connected to our lil spanned set,
                # ignore it
                if not candidate_edge.connected_to(spanned_edge.left) \
                        and not candidate_edge.connected_to(spanned_edge.right):

                    continue

                if smallest_edge is None or candidate_edge.weight() < smallest_edge.weight():
                    smallest_edge = candidate_edge

        print("extending edge %s" % smallest_edge)
        edges.remove(smallest_edge)
        spanned.add(smallest_edge)
        solution.append((smallest_edge.left, smallest_edge.right))

    return solution

{'fraction_non_alphanumeric': 0.08948418352807068, 'fraction_numerical': 0.001139925904816187, 'mean_word_length': 2.404461687681862, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4497580', 'n_tokens_mistral': 1008, 'n_tokens_neox': 949, 'n_words': 335}