<commit_before>import { cmp_number } from './utils';
import { inverse_permutation } from './permutation';
import { debug } from './core';
import { count_crossings } from './count_crossings';

export function barycenter_order(graph, comps, max_iter) {
  let orders = [[], [], 0];
  // Compute the barycenter heuristic on each connected component
  if (!comps) {
    comps = graph.components();
  }
  for (let i = 0; i < comps.length; i++) {
    const o = barycenter(graph, comps[i], max_iter);
    orders = [orders[0].concat(o[0]), orders[1].concat(o[1]), orders[2] + o[2]];
  }
  return orders;
}

// Take the list of neighbor indexes and return the median according to
// <NAME> and <NAME>, Edge crossings in drawings of bipartite graphs.
// Algorithmica, vol. 11 (1994) 379–403.
function median(neighbors) {
  if (neighbors.length === 0) return -1; // should not happen
  if (neighbors.length === 1) return neighbors[0];
  if (neighbors.length === 2) return (neighbors[0] + neighbors[1]) / 2;
  neighbors.sort(cmp_number);
  if (neighbors.length % 2) return neighbors[(neighbors.length - 1) / 2];
  const rm = neighbors.length / 2,
    lm = rm - 1,
    rspan = neighbors[neighbors.length - 1] - neighbors[rm],
    lspan = neighbors[lm] - neighbors[0];
  if (lspan == rspan) return (neighbors[lm] + neighbors[rm]) / 2;
  else return (neighbors[lm] * rspan + neighbors[rm] * lspan) / (lspan + rspan);
}

export function barycenter(graph, comp, max_iter) {
  const nodes = graph.nodes();
  let layer1;
  let layer2;
  let crossings;
  let iter;
  let best_layer1;
  let best_layer2;
  let best_crossings;
  let best_iter;
  let layer;
  let inv_layer = {};
  let i;
  let v;
  let neighbors;
  let med;

  layer1 = comp.filter((n) => graph.outDegree(n) !== 0);
  layer2 = comp.filter((n) => graph.inDegree(n) !== 0);
  if (comp.length < 3) {
    return [layer1, layer2, count_crossings(graph, layer1, layer2)];
  }

  if (!max_iter) max_iter = 24;
  else if (max_iter % 2 == 1) max_iter++; // want even number of iterations

  inv_layer = inverse_permutation(layer2);

  best_crossings = count_crossings(graph, layer1, layer2);
  best_layer1 = layer1.slice();
  best_layer2 = layer2.slice();
  best_iter = 0;
  const inv_neighbor = (e) => {
      const n = e.source == v ? e.target : e.source;
      return inv_layer[n.index];
    },
    barycenter_sort = (a, b) => {
      let d = med[a] - med[b];
      if (d === 0) {
        // If both values are equal,
        // place the odd degree vertex on the left of the even
        // degree vertex
        d = (graph.edges(b).length % 2) - (graph.edges(a).length % 2);
      }
      if (d < 0) return -1;
      else if (d > 0) return 1;
      return 0;
    };

  for (
    layer = layer1, iter = 0;
    iter < max_iter;
    iter++, layer = layer == layer1 ? layer2 : layer1
  ) {
    med = {};
    for (i = 0; i < layer.length; i++) {
      // Compute the median/barycenter for this node and set
      // its (real) value into node.pos
      v = nodes[layer[i]];
      if (layer == layer1) neighbors = graph.outEdges(v.index);
      else neighbors = graph.inEdges(v.index);
      neighbors = neighbors.map(inv_neighbor);
      med[v.index] = +median(neighbors);
      //console.log('median['+i+']='+med[v.index]);
    }
    layer.sort(barycenter_sort);
    for (i = 0; i < layer.length; i++) inv_layer = inverse_permutation(layer);
    crossings = count_crossings(graph, layer1, layer2);
    if (crossings < best_crossings) {
      best_crossings = crossings;
      best_layer1 = layer1.slice();
      best_layer2 = layer2.slice();
      best_iter = iter;
      max_iter = Math.max(max_iter, iter + 2); // we improved so go on
    }
  }
  if (debug) {
    console.log(`Best iter: ${best_iter}`);
  }

  return [best_layer1, best_layer2, best_crossings];
}<commit_msg>Manual cleanup of barycenter_order.js<commit_after>import { cmp_number } from './utils';
import { inverse_permutation } from './permutation';
import { debug } from './core';
import { count_crossings } from './count_crossings';

export function barycenter_order(graph, comps, max_iter) {
  let orders = [[], [], 0];
  // Compute the barycenter heuristic on each connected component
  if (!comps) {
    comps = graph.components();
  }
  for (let i = 0; i < comps.length; i++) {
    const o = barycenter(graph, comps[i], max_iter);
    orders = [orders[0].concat(o[0]), orders[1].concat(o[1]), orders[2] + o[2]];
  }
  return orders;
}

// Take the list of neighbor indexes and return the median according to
// <NAME> and <NAME>, Edge crossings in drawings of bipartite graphs.
// Algorithmica, vol. 11 (1994) 379–403.
function median(neighbors) {
  if (neighbors.length === 0) return -1; // should not happen
  if (neighbors.length === 1) return neighbors[0];
  if (neighbors.length === 2) return (neighbors[0] + neighbors[1]) / 2;
  neighbors.sort(cmp_number);
  if (neighbors.length % 2) return neighbors[(neighbors.length - 1) / 2];
  const rm = neighbors.length / 2;
  const lm = rm - 1;
  const rspan = neighbors[neighbors.length - 1] - neighbors[rm];
  const lspan = neighbors[lm] - neighbors[0];
  if (lspan == rspan) return (neighbors[lm] + neighbors[rm]) / 2;
  else return (neighbors[lm] * rspan + neighbors[rm] * lspan) / (lspan + rspan);
}

export function barycenter(graph, comp, max_iter) {
  const nodes = graph.nodes();
  let crossings;
  let iter;
  let layer;
  let neighbors;
  let med;

  const layer1 = comp.filter((n) => graph.outDegree(n) !== 0);
  const layer2 = comp.filter((n) => graph.inDegree(n) !== 0);
  if (comp.length < 3) {
    return [layer1, layer2, count_crossings(graph, layer1, layer2)];
  }

  if (!max_iter) max_iter = 24;
  else if (max_iter % 2 == 1) max_iter++; // want even number of iterations

  let inv_layer = inverse_permutation(layer2);

  let best_crossings = count_crossings(graph, layer1, layer2);
  let best_layer1 = layer1.slice();
  let best_layer2 = layer2.slice();
  let best_iter = 0;

  let v;
  const inv_neighbor = (e) =>
    inv_layer[e.source == v ? e.target : e.source.index];

  const barycenter_sort = (a, b) => {
    let d = med[a] - med[b];
    if (d === 0) {
      // If both values are equal,
      // place the odd degree vertex on the left of the even
      // degree vertex
      d = (graph.edges(b).length % 2) - (graph.edges(a).length % 2);
    }
    if (d < 0) return -1;
    else if (d > 0) return 1;
    return 0;
  };

  for (
    layer = layer1, iter = 0;
    iter < max_iter;
    iter++, layer = layer == layer1 ? layer2 : layer1
  ) {
    med = {};
    for (let i = 0; i < layer.length; i++) {
      // Compute the median/barycenter for this node and set
      // its (real) value into node.pos
      v = nodes[layer[i]];
      if (layer == layer1) neighbors = graph.outEdges(v.index);
      else neighbors = graph.inEdges(v.index);
      neighbors = neighbors.map(inv_neighbor);
      med[v.index] = +median(neighbors);
    }
    layer.sort(barycenter_sort);
    for (let i = 0; i < layer.length; i++) inv_layer = inverse_permutation(layer);
    crossings = count_crossings(graph, layer1, layer2);
    if (crossings < best_crossings) {
      best_crossings = crossings;
      best_layer1 = layer1.slice();
      best_layer2 = layer2.slice();
      best_iter = iter;
      max_iter = Math.max(max_iter, iter + 2); // we improved so go on
    }
  }
  if (debug) {
    console.log(`Best iter: ${best_iter}`);
  }

  return [best_layer1, best_layer2, best_crossings];
}
{'fraction_non_alphanumeric': 0.1506500469106018, 'fraction_numerical': 0.02251708886208283, 'mean_word_length': 3.046637744034707, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 17, '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': '6577441', 'n_tokens_mistral': 2746, 'n_tokens_neox': 2584, 'n_words': 731}