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

library graphlib.layout.rank.network_simplex;

import "feasible_tree.dart" show feasibleTree;
import "util.dart" show slack, longestPath;
import "../../alg/alg.dart" show preorder;
import "../../alg/alg.dart" show postorder;
import "../util.dart" show simplify, min;
import "../../graph.dart" show Graph, Edge;

const initRank = longestPath;

/// The network simplex algorithm assigns ranks to each node in the input graph
/// and iteratively improves the ranking to reduce the length of edges.
///
/// Preconditions:
///
///  1. The input graph must be a DAG.
///  2. All nodes in the graph must have an object value.
///  3. All edges in the graph must have "minlen" and "weight" attributes.
///
/// Postconditions:
///
///  1. All nodes in the graph will have an assigned "rank" attribute that has
///  been optimized by the network simplex algorithm. Ranks start at 0.
///
///
/// A rough sketch of the algorithm is as follows:
///
///  1. Assign initial ranks to each node. We use the longest path algorithm,
///  which assigns ranks to the lowest position possible. In general this
///  leads to very wide bottom ranks and unnecessarily long edges.
///  2. Construct a feasible tight tree. A tight tree is one such that all
///  edges in the tree have no slack (difference between length of edge
///  and minlen for the edge). This by itself greatly improves the assigned
///  rankings by shorting edges.
///  3. Iteratively find edges that have negative cut values. Generally a
///  negative cut value indicates that the edge could be removed and a new
///  tree edge could be added to produce a more compact graph.
///
/// Much of the algorithms here are derived from Gansner, et al., "A Technique
/// for Drawing Directed Graphs." The structure of the file roughly follows the
/// structure of the overall algorithm.
networkSimplex(Graph g) {
  g = simplify(g);
  initRank(g);
  var t = feasibleTree(g);
  initLowLimValues(t);
  initCutValues(t, g);

  var e, f;
  while ((e = leaveEdge(t)) != null) {
    f = enterEdge(t, g, e);
    exchangeEdges(t, g, e, f);
  }
}

/// Initializes cut values for all edges in the tree.
initCutValues(Graph t, Graph g) {
  var vs = postorder(t, t.nodes).toList();
  //vs = vs.getRange(0, vs.length - 1);
  vs.forEach((v) {
    assignCutValue(t, g, v);
  });
}

assignCutValue(Graph t, Graph g, child) {
  var childLab = t.node(child),
      parent = childLab["parent"];
  t.edge(child, parent)["cutvalue"] = calcCutValue(t, g, child);
}

/// Given the tight tree, its graph, and a child in the graph calculate and
/// return the cut value for the edge between the child and its parent.
num calcCutValue(Graph t, Graph g, child) {
  var childLab = t.node(child),
      parent = childLab["parent"],
      // True if the child is on the tail end of the edge in the directed graph
      childIsTail = true,
      // The graph's view of the tree edge we're inspecting
      graphEdge = g.edge(child, parent),
      // The accumulated cut value for the edge between this node and its parent
      cutValue = 0;

  if (graphEdge = null) {
    childIsTail = false;
    graphEdge = g.edge(parent, child);
  }

  cutValue = graphEdge["weight"];

  g.nodeEdges(child).forEach((e) {
    var isOutEdge = e.v == child,
        other = isOutEdge ? e.w : e.v;

    if (other != parent) {
      var pointsToHead = isOutEdge == childIsTail,
          otherWeight = g.edgeObj(e)["weight"];

      cutValue += pointsToHead ? otherWeight : -otherWeight;
      if (isTreeEdge(t, child, other)) {
        var otherCutValue = t.edge(child, other)["cutvalue"];
        cutValue += pointsToHead ? -otherCutValue : otherCutValue;
      }
    }
  });

  return cutValue;
}

initLowLimValues(Graph tree, [root=null]) {
  if (root == null) {
    root = tree.nodes.first;
  }
  dfsAssignLowLim(tree, {}, 1, root);
}

int dfsAssignLowLim(Graph tree, Map visited, int nextLim, v, [parent=null]) {
  var low = nextLim,
      label = tree.node(v);

  visited[v] = true;
  tree.neighbors(v).foreach((w) {
    if (!visited.containsKey(w)) {
      nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v);
    }
  });

  label["low"] = low;
  label["lim"] = nextLim++;
  if (parent != null) {
    label["parent"] = parent;
  } else {
    // TODO should be able to remove this when we incrementally update low lim
    label.remove("parent");
  }

  return nextLim;
}

Edge leaveEdge(Graph tree) {
  return tree.edges.firstWhere((e) {
    return tree.edgeObj(e)["cutvalue"] < 0;
  });
}

Edge enterEdge(Graph t, Graph g, Edge edge) {
  var v = edge.v,
      w = edge.w;

  // For the rest of this function we assume that v is the tail and w is the
  // head, so if we don't have this edge in the graph we should flip it to
  // match the correct orientation.
  if (!g.hasEdge(v, w)) {
    v = edge.w;
    w = edge.v;
  }

  var vLabel = t.node(v),
      wLabel = t.node(w),
      tailLabel = vLabel,
      flip = false;

  // If the root is in the tail of the edge then we need to flip the logic that
  // checks for the head and tail nodes in the candidates function below.
  if (vLabel["lim"] > wLabel["lim"]) {
    tailLabel = wLabel;
    flip = true;
  }

  var candidates = g.edges.where((edge) {
    return flip == isDescendant(t, t.node(edge.v), tailLabel) &&
           flip != isDescendant(t, t.node(edge.w), tailLabel);
  });

  return min(candidates, (edge) => slack(g, edge));
}

exchangeEdges(Graph t, Graph g, Edge e, Edge f) {
  var v = e.v,
      w = e.w;
  t.removeEdge(v, w);
  t.setEdge(f.v, f.w, {});
  initLowLimValues(t);
  initCutValues(t, g);
  updateRanks(t, g);
}

updateRanks(Graph t, Graph g) {
  var root = t.nodes.firstWhere((v) => g.node(v)["parent"] == null),
      vs = preorder(t, root);
  vs = vs.getRange(1, vs.length - 1);
  vs.forEach((v) {
    var parent = t.node(v)["parent"],
        edge = g.edge(v, parent),
        flipped = false;

    if (edge == null) {
      edge = g.edge(parent, v);
      flipped = true;
    }

    g.node(v)["rank"] = g.node(parent)["rank"] + (flipped ? edge["minlen"] : -edge["minlen"]);
  });
}

/// Returns true if the edge is in the tree.
bool isTreeEdge(Graph tree, u, v) {
  return tree.hasEdge(u, v);
}

/// Returns true if the specified node is descendant of the root node per the
/// assigned low and lim attributes in the tree.
bool isDescendant(Graph tree, Map vLabel, Map rootLabel) {
  return rootLabel["low"] <= vLabel["lim"] && vLabel["lim"] <= rootLabel["lim"];
}