<commit_before>var util = require("../util"),
    components = require("graphlib").alg.components,
    PriorityQueue = require("graphlib").data.PriorityQueue,
    Set = require("graphlib").data.Set,
    Digraph = require("graphlib").Digraph;

module.exports = function(g, debugLevel) {
  var timer = util.createTimer(debugLevel >= 1);
  timer.wrap("Rank phase", function() {
    initRank(g);

    components(g).forEach(function(cmpt) {
      var subgraph = g.subgraph(cmpt);
      var tree = feasibleTree(subgraph);
      while (true) {
        var e = leaveEdge(tree);
        if (e == null) break;
        var f = enterEdge(subgraph, tree, e);
        exchange(g, tree, e, f);
      }
      normalize(subgraph);
      // balance(subgraph);
    });
  })();
};

function initRank(g) {
  var minRank = {};
  var pq = new PriorityQueue();

  g.eachNode(function(u) {
    pq.add(u, g.inEdges(u).length);
    minRank[u] = 0;
  });

  while (pq.size() > 0) {
    var minId = pq.min();
    if (pq.priority(minId) > 0) {
      throw new Error("Input graph is not acyclic: " + g.toString());
    }
    pq.removeMin();

    var rank = minRank[minId];
    g.node(minId).rank = rank;

    g.outEdges(minId).forEach(function(e) {<commit_msg>Start on assigning nodes to ranks<commit_after>var util = require("../util"),
    components = require("graphlib").alg.components,
    PriorityQueue = require("graphlib").data.PriorityQueue,
    Set = require("graphlib").data.Set,
    Digraph = require("graphlib").Digraph;

module.exports = function(g, debugLevel) {
  var timer = util.createTimer(debugLevel >= 1);
  timer.wrap("Rank phase", function() {
    var reduced = combineRanks(g);

    initRank(reduced);

    components(reduced).forEach(function(cmpt) {
      var subgraph = reduced.subgraph(cmpt);
      var tree = feasibleTree(subgraph);
      while (true) {
        var e = leaveEdge(tree);
        if (e == null) break;
        var f = enterEdge(subgraph, tree, e);
        exchange(reduced, tree, e, f);
      }
      normalize(subgraph);
    });

    expandRanks(reduced);
  })();
};

// If there are rank constraints on nodes, then build a condensed graph,
// with one node per rank set.  Modify edges to that the minimum rank
// will be ranked before any others and the maximum rank will be ranked
// after any others.
function combineRanks(g) {
  var hasRankConstraint = false;
  var ranks = {};
  var uid = 1;
  g.eachNode(function(n, value) {
    if (value.hasOwnProperty('rank')) {
      hasRankConstraint = true;
      var r = value.rank;
      if (!ranks.hasOwnProperty(r)) {
        ranks[r] = [];
      }
      ranks[r].push(n);
    } else {
      // Nodes with no rank constraint get their own rank id
      var ur = 'unconstrained_rank_' + uid++;
      ranks[ur] = [n];
      if (g.node(n)) {
        g.node(n).rank = ur;
      } else {
        g.node(n, {rank: ur});
      }
    }
  });

  if (hasRankConstraint) {
    var reduced = new Digraph();
    reduced.graph({originalGraph: g});
    // Create one node for each rank, containing the ids of all nodes in
    // that rank as its value.
    for (var r in ranks) {
      reduced.addNode(r.toString(), {originals: ranks[r]});
    }

    // Add edges for each rank crossing edge in the original graph.
    g.eachEdge(function(id, source, target, value) {
      var source_rank = g.node(source).rank;
      var target_rank = g.node(target).rank;
      if (source_rank != target_rank) {
        reduce.addEdge(null, source_rank, target_rank);
      }
    });

    // Reverse in-edges into the minimum rank node and out-edges from
    // the maximum rank node.
    function reverse(edges) {
      for (var e in edges) {
        var edge = edges[e];
        var source = reduced.source(edges[e]);
        var target = reduced.target(edges[e]);
        reduced.delEdge(edges[e]);
        reduced.addEdge(edges[e], target, source, {reversed: true});
      }
    };

    reverse(reduced.inEdges('min'));
    reverse(reduced.outEdges('max'));

    // Add edges from 'min' to any node without in-edges and from any node
    // without out-edges to 'max'.
    reduced.eachNode(function(n, value) {
      if (n != 'min' && reduced.inEdges(n).length == 0) {
        reduced.addEdge(null, 'min', n);
      }
      if (n != 'max' && reduced.outEdges(n).length == 0) {
        reduced.addEdge(null, n, 'max');
      }
    });
    return reduced;
  } else {
    return g;
  }
}

function expandRanks(reduced) {
  if (reduced.graph() && reduced.graph().originalGraph) {
    // Copy ranks from reduced graph nodes to original graph
    // nodes.
    var expanded = reduced.graph().originalGraph;
    reduced.eachNode(function(n, value) {
      for (var n in value.originals) {
        expanded.node(value.originals[n]).rank = value.rank;
      }
    });
    return expanded;
  } else {
    return reduced;
  }
}

function initRank(g) {
  var minRank = {};
  var pq = new PriorityQueue();

  g.eachNode(function(u) {
    pq.add(u, g.inEdges(u).length);
    minRank[u] = 0;
  });

  while (pq.size() > 0) {
    var minId = pq.min();
    if (pq.priority(minId) > 0) {
      throw new Error("Input graph is not acyclic: " + g.toString());
    }
    pq.removeMin();

    var rank = minRank[minId];
    g.node(minId).rank = rank;

    g.outEdges(minId).forEach(function(e) {
{'fraction_non_alphanumeric': 0.15081905479194124, 'fraction_numerical': 0.002071173037092826, 'mean_word_length': 2.628415300546448, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, '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': '3261031', 'n_tokens_mistral': 1770, 'n_tokens_neox': 1719, 'n_words': 440}