<commit_before>// Given an undirected graph, find a minimum spanning tree and return it as
// an undirected graph (an unrooted tree). This function uses Prim's
// algorithm as described in "Introduction to Algorithms", Third Edition,
// Comen, et al., Pg 634.
var dig_alg_prim = dig.alg.prim = function(graph, weight) {
  var parents = {};
  var result = new dig.UGraph();
  var q = new dig_data_PriorityQueue();

  if (graph.isDirected()) {
    throw new Error("prim can only be used on undirected graphs");
  }

  if (graph.order() == 0) {
    return result;
  }

  dig_util_forEach(graph.nodes(), function(v) {
    q.add(v, Number.POSITIVE_INFINITY);
    result.addNode(v);
  });

  // Start from an arbitary node
  q.decrease(graph.nodes()[0], 0);

  var u, v;
  while (q.size() > 0) {
    u = q.removeMin();
    dig_util_forEach(graph.neighbors(u), function(v) {
      var pri = q.priority(v);
      if (pri !== undefined) {
        var edgeWeight = weight(u, v);
        if (edgeWeight < pri) {
          parents[v] = u;
          q.decrease(v, edgeWeight);
        }
      }
    });
  }

  dig_util_forEach(graph.nodes(), function(v) {
    if (v in parents) {
      result.addEdge(v, parents[v]);
    }
  });

  return result;
};<commit_msg>Slightly simpler Prim's algorithm<commit_after>// Given an undirected graph, find a minimum spanning tree and return it as
// an undirected graph (an unrooted tree). This function uses Prim's
// algorithm as described in "Introduction to Algorithms", Third Edition,
// Comen, et al., Pg 634.
var dig_alg_prim = dig.alg.prim = function(graph, weight) {
  var parents = {};
  var result = new dig.UGraph();
  var q = new dig_data_PriorityQueue();

  if (graph.isDirected()) {
    throw new Error("prim can only be used on undirected graphs");
  }

  if (graph.order() == 0) {
    return result;
  }

  dig_util_forEach(graph.nodes(), function(v) {
    q.add(v, Number.POSITIVE_INFINITY);
    result.addNode(v);
  });

  // Start from an arbitary node
  q.decrease(graph.nodes()[0], 0);

  var u, v, parent;
  while (q.size() > 0) {
    u = q.removeMin();
    if (u in parents) {
      result.addEdge(u, parents[u]);
    }
    dig_util_forEach(graph.neighbors(u), function(v) {
      var pri = q.priority(v);
      if (pri !== undefined) {
        var edgeWeight = weight(u, v);
        if (edgeWeight < pri) {
          parents[v] = u;
          q.decrease(v, edgeWeight);
        }
      }
    });
  }

  return result;
};
{'fraction_non_alphanumeric': 0.1437829080599433, 'fraction_numerical': 0.005670311867152693, 'mean_word_length': 2.748103186646434, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, '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': '3667364', 'n_tokens_mistral': 869, 'n_tokens_neox': 823, 'n_words': 240}