<jupyter_start><jupyter_text><jupyter_code>!git clone https://github.com/lmcanavals/algorithmic_complexity.git
from algorithmic_complexity.aclib import graphstuff as gs
import networkx as nx
from heapq import heappush as push, heappop as pop
import math
def prim(G, s):
  for u in G.nodes:
    G.nodes[u]['visited'] = False
    G.nodes[u]['cost'] = math.inf
    G.nodes[u]['path'] = -1

  q = [(0, s)]
  while q:
    _, u = pop(q)
    if not G.nodes[u]['visited']:
      G.nodes[u]['visited'] = True
      for v in G.neighbors(u):
        if not G.nodes[v]['visited']:
          w = G.edges[u, v]['weight']
          if w < G.nodes[v]['cost']:
            G.nodes[v]['cost'] = w
            G.nodes[v]['path'] = u
            push(q, (w, v))

  path = [-1]*G.number_of_nodes()
  for u in G.nodes:
    path[u] = G.nodes[u]['path']

  return path
%%file 1.in
0 1 3
1 2 2
1 5 5
2 4 5
2 5 7
3 5 5
3 7 8
4 6 8
4 7 2
G = nx.read_weighted_edgelist('1.in', nodetype=int)
gs.nx2gv(G, weighted=True)
path = prim(G, 0)
gs.nx2gv(G, weighted=True, path=path)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16651162790697674, 'fraction_numerical': 0.03255813953488372, 'mean_word_length': 2.85663082437276, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 1, '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}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '648980', 'license': 'CC0-1.0', 'n_tokens_mistral': 474, 'n_tokens_neox': 443, 'n_words': 119, 'path': 'notebooks/bg_prim.ipynb', 'repo_name': 'AgustinAMaita/DataSet', 'size': '1075'}