<commit_before>import networkx as nx                 # graph library
import binomial_heap as bh            # Binomial heap implementation
import dary_heap as dh                # D-ary heap implementation
import fib_heap as fh                 # Fibonacci heap implementation
import disjoint_set as ds             # Disjoint set implementation
import time                           # Time functions
import glob
import os
from argparse import ArgumentParser   # Command line argument parser


def kruskal(graph, edges=[], sort=False):
    """ Kruskal's algorithm for finding a minimum spanning tree. Implements
    the solution presented at Brassard's `Fundamentals of Algorithms' book. """
    
    mst = [] # list of edges that form the minimum spanning tree
    n = nx.number_of_nodes(graph)

    # list of all the edges in graph, sorted by increasing lenght
    if not edges:
        edges = graph.edges(data=True)        
        if sort:
            edges.sort(key=lambda edge: edge[2]['weight'])

    # Initialize n sets, each containing a different element of N
    uf = ds.DisjointSets(graph.nodes())

    # greedy loop
    tn = 0   # number of edges in the set
    en = 0
    while tn < n - 1:
        e = edges[en]
        en += 1
        u = uf.find(e[0])
        v = uf.find(e[1])

        if u != v:
            mst.append(e)
            tn += 1
            uf.merge(u, v)

    return mst


def prim(graph):
    """ Prim's algorithm for finding a minimum spanning tree. Implements the 
    Brassard's `Fundamentals of Algorithms' pseudocode, using lists. """
    
    # Obtiene matriz de adyacencia con <inf> en nodos no conectados.
    mx = nx.adjacency_matrix(graph).toarray()
    mx[mx == 0] = 64000                           # Reemplaza ceros por <inf>
    n = nx.number_of_nodes(graph)                 # Número de nodos del grafo.
    
    mst = []

    nearest = [0] * (n + 1)
    mindist = mx[:,0]

    # greedy loop
    for _ in range(n - 1):
        mini = 64000

        # minimum edge search
        for j in range(1, n):
            if 0 <= mindist[j] and mindist[j] < mini:
                mini = mindist[j]
                k = j

        mst.append((nearest[k]+1, k+1, graph.get_edge_data(nearest[k]+1, k+1)))
        mindist[k] = -1

        for j in range(1, n):
            if mx[j,k] < mindist[j]:
                mindist[j] = mx[j, k]
                nearest[j] = k

    return mst
    

def prim_generic_heap(graph, heap):
    """ Prim's algorithm for finding a minimum spanning tree. It implements the
    solution presented at Brassard's `Fundamentals of Algorithms' book, but uses 
    a Fibonacci Heap instead of a linked-list. """
    
    # initialization step    
    
    # Obtiene matriz de adyacencia con <inf> en nodos no conectados.
    mx = nx.adjacency_matrix(graph).toarray()
    mx[mx == 0] = 64000                           # Reemplaza ceros por <inf>
    n = nx.number_of_nodes(graph)                 # Número de nodos del grafo

    mst = []

    nearest = [0] * n     # nearest edge to i-node
    mindist = [64000] * n
    heapnode = [None] * n # item in the heap
    
    heapnode[0] = heap.insert(mindist[0],0)
    
    # greedy loop
    for _ in range(n):
        # Use heap to obtain minimum edge
        k = heap.extractmin().value
        
        mindist[k] = -1
        if graph.get_edge_data(nearest[k]+1, k+1) is not None:
            mst.append((nearest[k]+1, k+1, graph.get_edge_data(nearest[k]+1, k+1)))
        
        for j in range(1, n):<commit_msg>Fix comments.<commit_after>import networkx as nx                 # graph library
import binomial_heap as bh            # Binomial heap implementation
import dary_heap as dh                # D-ary heap implementation
import fib_heap as fh                 # Fibonacci heap implementation
import disjoint_set as ds             # Disjoint set implementation
import time                           # Time functions
import glob
import os
from argparse import ArgumentParser   # Command line argument parser


def kruskal(graph, edges=[], sort=False):
    """ Kruskal's algorithm for finding a minimum spanning tree. Implements
    the solution presented at Brassard's `Fundamentals of Algorithms' book. """
    
    mst = [] # list of edges that form the minimum spanning tree
    n = nx.number_of_nodes(graph)

    # list of all the edges in graph, sorted by increasing lenght
    if not edges:
        edges = graph.edges(data=True)        
        if sort:
            edges.sort(key=lambda edge: edge[2]['weight'])

    # Initialize n sets, each containing a different element of N
    uf = ds.DisjointSets(graph.nodes())

    # greedy loop
    tn = 0   # number of edges in the set
    en = 0
    while tn < n - 1:
        e = edges[en]
        en += 1
        u = uf.find(e[0])
        v = uf.find(e[1])

        if u != v:
            mst.append(e)
            tn += 1
            uf.merge(u, v)

    return mst


def prim(graph):
    """ Prim's algorithm for finding a minimum spanning tree. Implements the 
    Brassard's `Fundamentals of Algorithms' pseudocode, using lists. """
    
    # Obtiene matriz de adyacencia con <inf> en nodos no conectados.
    mx = nx.adjacency_matrix(graph).toarray()
    mx[mx == 0] = 64000                           # Reemplaza ceros por <inf>
    n = nx.number_of_nodes(graph)                 # Número de nodos del grafo.
    
    mst = []

    nearest = [0] * (n + 1)
    mindist = mx[:,0]

    # greedy loop
    for _ in range(n - 1):
        mini = 64000

        # minimum edge search
        for j in range(1, n):
            if 0 <= mindist[j] and mindist[j] < mini:
                mini = mindist[j]
                k = j

        mst.append((nearest[k]+1, k+1, graph.get_edge_data(nearest[k]+1, k+1)))
        mindist[k] = -1

        for j in range(1, n):
            if mx[j,k] < mindist[j]:
                mindist[j] = mx[j, k]
                nearest[j] = k

    return mst
    

def prim_generic_heap(graph, heap):
    """ Prim's algorithm for finding a minimum spanning tree. It implements the
    solution presented at Brassard's `Fundamentals of Algorithms' book. It uses
    a Heap (concrete implementation by the heap param) and a adjacency matrix. """
    
    # initialization step    
    
    # Obtiene matriz de adyacencia con <inf> en nodos no conectados.
    mx = nx.adjacency_matrix(graph).toarray()
    mx[mx == 0] = 64000                           # Reemplaza ceros por <inf>
    n = nx.number_of_nodes(graph)                 # Número de nodos del grafo

    mst = []

    nearest = [0] * n     # nearest edge to i-node
    mindist = [64000] * n
    heapnode = [None] * n # item in the heap
    
    heapnode[0] = heap.insert(mindist[0],0)
    
    # greedy loop
    for _ in range(n):
        # Use heap to obtain minimum edge
        k = heap.extractmin().value
        
        mindist[k] = -1
        if graph.get_edge_data(nearest[k]+1, k+1) is not None:
            mst.append((nearest[k]+1, k+1, graph.get_edge_data(nearest[k]+1, k+1)))
        
        for j in range(1, n):
{'fraction_non_alphanumeric': 0.09736767619586753, 'fraction_numerical': 0.015284460798188508, 'mean_word_length': 1.911825298722703, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 11, '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': '4676570', 'n_tokens_mistral': 2330, 'n_tokens_neox': 2198, 'n_words': 723}