pub/graphlib/lib/src/layout/rank/rank.dart

library graphlib.layout.rank;

import 'util.dart' show longestPath, slack;
import 'feasible_tree.dart' show feasibleTree;
import 'network_simplex.dart' show networkSimplex;
import "../../graph.dart" show Graph;

/// Assigns a rank to each node in the input graph that respects the "minlen"
/// constraint specified on edges between nodes.
///
/// This basic structure is derived from Gansner, et al., "A Technique for
/// Drawing Directed Graphs."
///
/// Pre-conditions:
///
///    1. Graph must be a connected DAG
///    2. Graph nodes must be objects
///    3. Graph edges must have "weight" and "minlen" attributes
///
/// Post-conditions:
///
///    1. Graph nodes will have a "rank" attribute based on the results of the
///       algorithm. Ranks can start at any index (including negative), we'll
///       fix them up later.
rank(Graph g) {
  switch (g.graph()["ranker"]) {
    case "network-simplex":
      networkSimplexRanker(g);
      break;
    case "tight-tree":
      tightTreeRanker(g);
      break;
    case "longest-path":
      longestPathRanker(g);
      break;
    default:
      networkSimplexRanker(g);
  }
}

// A fast and simple ranker, but results are far from optimal.
const longestPathRanker = longestPath;

tightTreeRanker(Graph g) {
  longestPath(g);
  feasibleTree(g);
}

networkSimplexRanker(Graph g) {
  networkSimplex(g);
}