<commit_before># -*- coding: utf-8 -*-

"""
    Kruskal MST Algorithm
    ---------------------

    Offers two functions that calculate the Minimum Spanning Tree of an undirected graph.

    - kruskal
        Parameters:
            Edges
                A list of the graph's edges.
                Each element is a tuple in the form ((From, To), Weight).
            Vertices
                A list of the graph's vertices.
        

    - kruskal_from_graph
        Parameters:
            Graph
                The graph as an adjacency list.
        
    Both return the tuple (Cost, Mst) where
        Cost
            The weight of the MST.
        Mst
            The edges selected in the MST.
            Each edge is in the form (From, To).
"""

from union_find import UnionFind

def kruskal_from_graph(graph):
    """
    Runs the Kruskal algorithm using the graph representation.
    """
    # Create the list of edges.
    edges = dict() 
    for u in graph:
        neighbours = graph[u]
        for v in neighbours:
            edges[( min(u,v), max(u,v) )] = neighbours[v]

    return kruskal(edges.items(), graph.keys())


def kruskal(edges, vertices):
    """
    Runs the Kruskal algorithm using the edges and vertices.
    """<commit_msg>Add Kruskal's complexity<commit_after># -*- coding: utf-8 -*-

"""
    Kruskal MST Algorithm
    ---------------------

    Offers two functions that calculate the Minimum Spanning Tree of an undirected graph.

    - kruskal
        Parameters:
            Edges
                A list of the graph's edges.
                Each element is a tuple in the form ((From, To), Weight).
            Vertices
                A list of the graph's vertices.
        

    - kruskal_from_graph
        Parameters:
            Graph
                The graph as an adjacency list.
        
    Both return the tuple (Cost, Mst) where
        Cost
            The weight of the MST.
        Mst
            The edges selected in the MST.
            Each edge is in the form (From, To).

    Complexity
        Θ( |E| log(|E|) )
"""

from union_find import UnionFind

def kruskal_from_graph(graph):
    """
    Runs the Kruskal algorithm using the graph representation.
    """
    # Create the list of edges.
    edges = dict() 
    for u in graph:
        neighbours = graph[u]
        for v in neighbours:
            edges[( min(u,v), max(u,v) )] = neighbours[v]

    return kruskal(edges.items(), graph.keys())


def kruskal(edges, vertices):
    """
    Runs the Kruskal algorithm using the edges and vertices.
    """
{'fraction_non_alphanumeric': 0.09592233009708738, 'fraction_numerical': 0.0007766990291262136, 'mean_word_length': 1.642051282051282, 'pattern_counts': {'":': 0, '<': 3, '<?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': '5189398', 'n_tokens_mistral': 739, 'n_tokens_neox': 703, 'n_words': 272}