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

library graphlib.layout.rank.feasible_tree;

import "../../graph.dart" show Graph;
import "util.dart" show slack;
import "../util.dart" as util;

/// Constructs a spanning tree with tight edges and adjusted the input node's
/// ranks to achieve this. A tight edge is one that is has a length that matches
/// its "minlen" attribute.
///
/// The basic structure for this function is derived from Gansner, et al., "A
/// Technique for Drawing Directed Graphs."
///
/// Pre-conditions:
///
///    1. Graph must be a DAG.
///    2. Graph must be connected.
///    3. Graph must have at least one node.
///    5. Graph nodes must have been previously assigned a "rank" property that
///       respects the "minlen" property of incident edges.
///    6. Graph edges must have a "minlen" property.
///
/// Post-conditions:
///
///    - Graph nodes will have their rank adjusted to ensure that all edges are
///      tight.
///
/// Returns a tree (undirected graph) that is constructed using only "tight"
/// edges.
Graph feasibleTree(Graph g) {
  var t = new Graph(directed: false);

  // Choose arbitrary node from which to start our tree
  var start = g.nodes.first,
      size = g.nodeCount;
  t.setNode(start, {});

  var edge, delta;
  while (tightTree(t, g) < size) {
    edge = findMinSlackEdge(t, g);
    delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge);
    shiftRanks(t, g, delta);
  }

  return t;
}

/// Finds a maximal tree of tight edges and returns the number of nodes in the
/// tree.
int tightTree(Graph t, Graph g) {
  dfs(v) {
    g.nodeEdges(v).forEach((e) {
      var edgeV = e.v,
          w = (v == edgeV) ? e.w : edgeV;
      if (!t.hasNode(w) && slack(g, e) == 0) {
        t.setNode(w, {});
        t.setEdge(v, w, {});
        dfs(w);
      }
    });
  }

  t.nodes.forEach(dfs);
  return t.nodeCount;
}

/// Finds the edge with the smallest slack that is incident on tree and returns
/// it.
findMinSlackEdge(Graph t, Graph g) {
  return util.min(g.edges, (e) {
    if (t.hasNode(e.v) != t.hasNode(e.w)) {
      return slack(g, e);
    }
  });
}

shiftRanks(Graph t, Graph g, num delta) {
  t.nodes.forEach((v) {
    g.node(v).rank += delta;
  });
}