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

library graphlib.layout.normalize;

import "../graph.dart" show Graph, Edge;
import "util.dart" as util;

/// Breaks any long edges in the graph into short segments that span 1 layer
/// each. This operation is undoable with the denormalize function.
///
/// Pre-conditions:
///
///    1. The input graph is a DAG.
///    2. Each node in the graph has a "rank" property.
///
/// Post-condition:
///
///    1. All edges in the graph have a length of 1.
///    2. Dummy nodes are added where edges have been split into segments.
///    3. The graph is augmented with a "dummyChains" attribute which contains
///       the first dummy in each chain of dummy nodes produced.
run(Graph g) {
  g.graph()["dummyChains"] = [];
  g.edges.forEach((edge) { normalizeEdge(g, edge); });
}

normalizeEdge(Graph g, Edge e) {
  var v = e.v,
      vRank = g.node(v)["rank"],
      w = e.w,
      wRank = g.node(w)["rank"],
      name = e.name,
      edgeLabel = g.edgeObj(e),
      labelRank = edgeLabel["labelRank"];

  if (wRank == vRank + 1) return;

  g.removeEdgeObj(e);

  var dummy, attrs, i = 0;
  for (++vRank; vRank < wRank; ++i, ++vRank) {
    edgeLabel.points = [];
    attrs = {
      "width": 0, "height": 0,
      "edgeLabel": edgeLabel, "edgeObj": e,
      "rank": vRank
    };
    dummy = util.addDummyNode(g, "edge", attrs, "_d");
    if (vRank == labelRank) {
      attrs["width"] = edgeLabel["width"];
      attrs["height"] = edgeLabel["height"];
      attrs["dummy"] = "edge-label";
      attrs["labelpos"] = edgeLabel["labelpos"];
    }
    g.setEdge(v, dummy, { "weight": edgeLabel["weight"] }, name);
    if (i == 0) {
      g.graph()["dummyChains"].add(dummy);
    }
    v = dummy;
  }

  g.setEdge(v, w, { "weight": edgeLabel["weight"] }, name);
}

undo(Graph g) {
  g.graph()["dummyChains"].forEach((v) {
    Map node = g.node(v),
      origLabel = node["edgeLabel"];
    g.setEdge(node["edgeObj"], origLabel);
    while (node["dummy"] != null) {
      var w = g.successors(v).first;
      g.removeNode(v);
      origLabel["points"].add({ "x": node["x"], "y": node["y"] });
      if (node["dummy"] == "edge-label") {
        origLabel["x"] = node["x"];
        origLabel["y"] = node["y"];
        origLabel["width"] = node["width"];
        origLabel["height"] = node["height"];
      }
      v = w;
      node = g.node(v);
    }
  });
}