pub/graphlib/lib/src/layout/order/build_layer_graph.dart

library graphlib.layout.order.build_layer_graph;

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

/// Constructs a graph that can be used to sort a layer of nodes. The graph will
/// contain all base and subgraph nodes from the request layer in their original
/// hierarchy and any edges that are incident on these nodes and are of the type
/// requested by the "relationship" parameter.
///
/// Nodes from the requested rank that do not have parents are assigned a root
/// node in the output graph, which is set in the root graph attribute. This
/// makes it easy to walk the hierarchy of movable nodes during ordering.
///
/// Pre-conditions:
///
///    1. Input graph is a DAG
///    2. Base nodes in the input graph have a rank attribute
///    3. Subgraph nodes in the input graph has minRank and maxRank attributes
///    4. Edges have an assigned weight
///
/// Post-conditions:
///
///    1. Output graph has all nodes in the movable rank with preserved
///       hierarchy.
///    2. Root nodes in the movable layer are made children of the node
///       indicated by the root attribute of the graph.
///    3. Non-movable nodes incident on movable nodes, selected by the
///       relationship parameter, are included in the graph (without hierarchy).
///    4. Edges incident on movable nodes, selected by the relationship
///       parameter, are added to the output graph.
///    5. The weights for copied edges are aggregated as need, since the output
///       graph is not a multi-graph.
buildLayerGraph(Graph g, rank, relationship) {
  var root = createRootNode(g),
      result = new Graph(compound: true)
        ..setGraph({ "root": root })
        ..defaultNodeLabelFn = (v) => g.node(v);

  g.nodes.forEach((v) {
    var node = g.node(v),
        parent = g.parent(v);

    var minRank = node.containsKey("minRank") ? node["minRank"] : 0.0;
    var maxRank = node.containsKey("maxRank") ? node["maxRank"] : 0.0;
    if (node["rank"] == rank || minRank <= rank && rank <= maxRank) {
      result.setNode(v);
      result.setParent(v, parent != null ? parent : root);

      // This assumes we have only short edges!
      var edges = relationship == "inEdges" ? g.inEdges(v) : g.outEdges(v);
      edges.forEach((Edge e) {
        var u = e.v == v ? e.w : e.v,
            edge = result.edge(u, v),
            weight = edge != null ? edge["weight"] : 0;
        result.setEdge(u, v, { "weight": g.edgeObj(e)["weight"] + weight });
      });

      if (node.containsKey("minRank")) {
        result.setNode(v, {
          "borderLeft": node["borderLeft"][rank],
          "borderRight": node["borderRight"][rank]
        });
      }
    }
  });

  return result;
}

String createRootNode(Graph g) {
  var v;
  while (g.hasNode((v = uniqueId("_root"))));
  return v;
}