pub/graphlib/lib/src/layout/position/bk.dart - third_party/dart-pkg - Git at Google

 library graphlib.layout.position.bk;

 import "dart:math" as Math;
 import "../../graph.dart" show Graph;
 import "../util.dart" as util;

 // This module provides coordinate assignment based on Brandes and Köpf, "Fast
 // and Simple Horizontal Coordinate Assignment."

 /// Marks all edges in the graph with a type-1 conflict with the "type1Conflict"
 /// property. A type-1 conflict is one where a non-inner segment crosses an
 /// inner segment. An inner segment is an edge with both incident nodes marked
 /// with the "dummy" property.
 ///
 /// This algorithm scans layer by layer, starting with the second, for type-1
 /// conflicts between the current layer and the previous layer. For each layer
 /// it scans the nodes from left to right until it reaches one that is incident
 /// on an inner segment. It then scans predecessors to determine if they have
 /// edges that cross that inner segment. At the end a final scan is done for all
 /// nodes on the current rank to see if they cross the last visited inner
 /// segment.
 ///
 /// This algorithm (safely) assumes that a dummy node will only be incident on a
 /// single node in the layers being scanned.
 Map findType1Conflicts(Graph g, Iterable layering) {
   var conflicts = {};

   visitLayer(Map prevLayer, List layer) {
     var
       // last visited node in the previous layer that is incident on an inner
       // segment.
       k0 = 0,
       // Tracks the last node in this layer scanned for crossings with a type-1
       // segment.
       scanPos = 0,
       prevLayerLength = prevLayer.length,
       lastNode = layer.last;

     int i = 0;
     layer.forEach((v) {
       var w = findOtherInnerSegmentNode(g, v),
           k1 = w ? g.node(w).order : prevLayerLength;

       if (w || v == lastNode) {
         layer.getRange(scanPos, i +1).forEach((scanNode) {
           g.predecessors(scanNode).forEach((u) {
             var uLabel = g.node(u),
                 uPos = uLabel.order;
             if ((uPos < k0 || k1 < uPos) &&
                 !(uLabel["dummy"] && g.node(scanNode)["dummy"])) {
               addConflict(conflicts, u, scanNode);
             }
           });
         });
         scanPos = i + 1;
         k0 = k1;
       }
       i++;
     });

     return layer;
   }

   layering.reduce(visitLayer);
   return conflicts;
 }

 Map findType2Conflicts(Graph g, Iterable layering) {
   var conflicts = {};

   scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) {
     var v;
     util.range(southPos, southEnd).forEach((i) {
       v = south[i];
       if (g.node(v)["dummy"]) {
         g.predecessors(v).forEach((u) {
           Map uNode = g.node(u);
           if (uNode["dummy"] &&
               (uNode["order"] < prevNorthBorder || uNode["order"] > nextNorthBorder)) {
             addConflict(conflicts, u, v);
           }
         });
       }
     });
   }


   visitLayer(north, south) {
     var prevNorthPos = -1,
         nextNorthPos,
         southPos = 0;

     south.forEach((v, southLookahead) {
       if (g.node(v).dummy == "border") {
         var predecessors = g.predecessors(v);
         if (predecessors.length != 0) {
           nextNorthPos = g.node(predecessors[0])["order"];
           scan(south, southPos, southLookahead, prevNorthPos, nextNorthPos);
           southPos = southLookahead;
           prevNorthPos = nextNorthPos;
         }
       }
       scan(south, southPos, south.length, nextNorthPos, north.length);
     });

     return south;
   }

   layering.reduce(visitLayer);
   return conflicts;
 }

 findOtherInnerSegmentNode(Graph g, v) {
   if (g.node(v)["dummy"]) {
     return g.predecessors(v).firstWhere((u) {
       return g.node(u)["dummy"];
     });
   }
 }

 addConflict(Map conflicts, v, w) {
   if (v > w) {
     var tmp = v;
     v = w;
     w = tmp;
   }

   var conflictsV = conflicts[v];
   if (!conflictsV) {
     conflicts[v] = conflictsV = {};
   }
   conflictsV[w] = true;
 }

 bool hasConflict(Map conflicts, v, w) {
   if (v > w) {
     var tmp = v;
     v = w;
     w = tmp;
   }
   return conflicts[v].containsKey(w);
 }

 /// Try to align nodes into vertical "blocks" where possible. This algorithm
 /// attempts to align a node with one of its median neighbors. If the edge
 /// connecting a neighbor is a type-1 conflict then we ignore that possibility.
 /// If a previous node has already formed a block with a node after the node
 /// we're trying to form a block with, we also ignore that possibility - our
 /// blocks would be split in that scenario.
 Map verticalAlignment(Graph g, Iterable layering, Map conflicts, Iterable neighborFn(v)) {
   var root = {},
       align = {},
       pos = {};

   // We cache the position here based on the layering because the graph and
   // layering may be out of sync. The layering matrix is manipulated to
   // generate different extreme alignments.
   layering.forEach((layer) {
     layer.forEach((v, order) {
       root[v] = v;
       align[v] = v;
       pos[v] = order;
     });
   });

   layering.forEach((layer) {
     var prevIdx = -1;
     layer.forEach((v) {
       var ws = neighborFn(v);
       if (ws.length != 0) {
         ws = ws.sort((w) => pos[w]);
         var mp = (ws.length - 1) / 2;
         for (var i = mp.floor(), il = mp.ceil(); i <= il; ++i) {
           var w = ws[i];
           if (align[v] == v &&
               prevIdx < pos[w] &&
               !hasConflict(conflicts, v, w)) {
             align[w] = v;
             align[v] = root[v] = root[w];
             prevIdx = pos[w];
           }
         }
       }
     });
   });

   return { "root": root, "align": align };
 }

 Map horizontalCompaction(Graph g, Iterable layering, root, align, [bool reverseSep=false]) {
   // We use local variables for these parameters instead of manipulating the
   // graph because it becomes more verbose to access them in a chained manner.
   var shift = {},
       shiftNeighbor = {},
       sink = {},
       xs = {},
       pred = {},
       graphLabel = g.graph(),
       sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep);

   layering.forEach((layer) {
     layer.forEach((v, order) {
       sink[v] = v;
       shift[v] = double.INFINITY;
       pred[v] = layer[order - 1];
     });
   });

   g.nodes.forEach((v) {
     if (root[v] == v) {
       placeBlock(g, layering, sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, v);
     }
   });

   layering.forEach((layer) {
     layer.forEach((v) {
       xs[v] = xs[root[v]];
       // This line differs from the source paper. See
       // http://www.inf.uni-konstanz.de/~brandes/publications/ for details.
       if (v == root[v] && shift[sink[root[v]]] < double.INFINITY) {
         xs[v] += shift[sink[root[v]]];

         // Cascade shifts as necessary
         var w = shiftNeighbor[sink[root[v]]];
         if (w && shift[w] != double.INFINITY) {
           xs[v] += shift[w];
         }
       }
     });
   });

   return xs;
 }

 placeBlock(Graph g, layering, Function sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, v) {
   if (xs.containsKey(v)) return;
   xs[v] = 0;

   var w = v,
       u;
   do {
     if (pred[w]) {
       u = root[pred[w]];
       placeBlock(g, layering, sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, u);
       if (sink[v] == v) {
         sink[v] = sink[u];
       }

       var delta = sepFn(g, w, pred[w]);
       if (sink[v] != sink[u]) {
         shift[sink[u]] = Math.min(shift[sink[u]], xs[v] - xs[u] - delta);
         shiftNeighbor[sink[u]] = sink[v];
       } else {
         xs[v] = Math.max(xs[v], xs[u] + delta);
       }
     }
     w = align[w];
   } while (w != v);
 }

 /// Returns the alignment that has the smallest width of the given alignments.
 Map findSmallestWidthAlignment(Graph g, Map<String, Map> xss) {
   return util.min(xss.values, (Map xs) {
     var min = util.min(xs.keys, (v) => xs[v] - width(g, v) / 2),
         max = util.max(xs.keys, (v) => xs[v] + width(g, v) / 2);
     return max - min;
   });
 }

 /// Align the coordinates of each of the layout alignments such that
 /// left-biased alignments have their minimum coordinate at the same point as
 /// the minimum coordinate of the smallest width alignment and right-biased
 /// alignments have their maximum coordinate at the same point as the maximum
 /// coordinate of the smallest width alignment.
 alignCoordinates(Map<String, Map> xss, Map alignTo) {
   var alignToMin = util.min(alignTo.values),
       alignToMax = util.max(alignTo.values);

   ["u", "d"].forEach((vert) {
     ["l", "r"].forEach((horiz) {
       var alignment = vert + horiz,
           delta;
       Map xs = xss[alignment];
       if (xs == alignTo) return;

       delta = horiz == "l" ? alignToMin - util.min(xs.values) : alignToMax - util.max(xs.values);

       if (delta) {
         xss[alignment] = util.mapValues(xs, (x, _) => x + delta);
       }
     });
   });
 }

 balance(Map<String, Map> xss, [align]) {
   return util.mapValues(xss["ul"], (_, v) {
     if (align != null) {
       return xss[align.toLowerCase()][v];
     } else {
       var xs = util.pluck(xss.values, v)..sort();
       return (xs[1] + xs[2]) / 2;
     }
   });
 }

 positionX(Graph g) {
   var layering = util.buildLayerMatrix(g);
   var conflicts = util.merge({}, [findType1Conflicts(g, layering),
                           findType2Conflicts(g, layering)]);

   Map<String, Map> xss = {};
   var adjustedLayering;
   ["u", "d"].forEach((vert) {
     adjustedLayering = vert == "u" ? layering : layering.reversed.toList();
     ["l", "r"].forEach((horiz) {
       if (horiz == "r") {
         adjustedLayering = adjustedLayering.map((inner) {
           return inner.values.reverse();
         });
       }

       var neighborFn = (v) => (vert == "u" ? g.predecessors(v) : g.successors(v));
       var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn);
       Map xs = horizontalCompaction(g, adjustedLayering,
                                     align["root"], align["align"],
                                     horiz == "r");
       if (horiz == "r") {
         xs = util.mapValues(xs, (_, x) => -x);
       }
       xss[vert + horiz] = xs;
     });
   });

   var smallestWidth = findSmallestWidthAlignment(g, xss);
   alignCoordinates(xss, smallestWidth);
   return balance(xss, g.graph()["align"]);
 }

 sep(nodeSep, edgeSep, bool reverseSep) {
   return (Graph g, v, w) {
     Map vLabel = g.node(v),
         wLabel = g.node(w);
     var sum = 0,
         delta;

     sum += vLabel["width"] / 2;
     if (vLabel.containsKey("labelpos")) {
       switch (vLabel["labelpos"].toLowerCase()) {
         case "l": delta = -vLabel["width"] / 2; break;
         case "r": delta = vLabel["width"] / 2; break;
       }
     }
     if (delta != 0) {
       sum += reverseSep ? delta : -delta;
     }
     delta = 0;

     sum += (vLabel["dummy"] ? edgeSep : nodeSep) / 2;
     sum += (wLabel["dummy"] ? edgeSep : nodeSep) / 2;

     sum += wLabel["width"] / 2;
     if (wLabel.containsKey("labelpos")) {
       switch (wLabel["labelpos"].toLowerCase()) {
         case "l": delta = wLabel["width"] / 2; break;
         case "r": delta = -wLabel["width"] / 2; break;
       }
     }
     if (delta != 0) {
       sum += reverseSep ? delta : -delta;
     }
     delta = 0;

     return sum;
   };
 }

 width(Graph g, v) => g.node(v)["width"];
	library graphlib.layout.position.bk;

	import "dart:math" as Math;
	import "../../graph.dart" show Graph;
	import "../util.dart" as util;

	// This module provides coordinate assignment based on Brandes and Köpf, "Fast
	// and Simple Horizontal Coordinate Assignment."

	/// Marks all edges in the graph with a type-1 conflict with the "type1Conflict"
	/// property. A type-1 conflict is one where a non-inner segment crosses an
	/// inner segment. An inner segment is an edge with both incident nodes marked
	/// with the "dummy" property.
	///
	/// This algorithm scans layer by layer, starting with the second, for type-1
	/// conflicts between the current layer and the previous layer. For each layer
	/// it scans the nodes from left to right until it reaches one that is incident
	/// on an inner segment. It then scans predecessors to determine if they have
	/// edges that cross that inner segment. At the end a final scan is done for all
	/// nodes on the current rank to see if they cross the last visited inner
	/// segment.
	///
	/// This algorithm (safely) assumes that a dummy node will only be incident on a
	/// single node in the layers being scanned.
	Map findType1Conflicts(Graph g, Iterable layering) {
	var conflicts = {};

	visitLayer(Map prevLayer, List layer) {
	var
	// last visited node in the previous layer that is incident on an inner
	// segment.
	k0 = 0,
	// Tracks the last node in this layer scanned for crossings with a type-1
	// segment.
	scanPos = 0,
	prevLayerLength = prevLayer.length,
	lastNode = layer.last;

	int i = 0;
	layer.forEach((v) {
	var w = findOtherInnerSegmentNode(g, v),
	k1 = w ? g.node(w).order : prevLayerLength;

	if (w \|\| v == lastNode) {
	layer.getRange(scanPos, i +1).forEach((scanNode) {
	g.predecessors(scanNode).forEach((u) {
	var uLabel = g.node(u),
	uPos = uLabel.order;
	if ((uPos < k0 \|\| k1 < uPos) &&
	!(uLabel["dummy"] && g.node(scanNode)["dummy"])) {
	addConflict(conflicts, u, scanNode);
	}
	});
	});
	scanPos = i + 1;
	k0 = k1;
	}
	i++;
	});

	return layer;
	}

	layering.reduce(visitLayer);
	return conflicts;
	}

	Map findType2Conflicts(Graph g, Iterable layering) {
	var conflicts = {};

	scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) {
	var v;
	util.range(southPos, southEnd).forEach((i) {
	v = south[i];
	if (g.node(v)["dummy"]) {
	g.predecessors(v).forEach((u) {
	Map uNode = g.node(u);
	if (uNode["dummy"] &&
	(uNode["order"] < prevNorthBorder \|\| uNode["order"] > nextNorthBorder)) {
	addConflict(conflicts, u, v);
	}
	});
	}
	});
	}


	visitLayer(north, south) {
	var prevNorthPos = -1,
	nextNorthPos,
	southPos = 0;

	south.forEach((v, southLookahead) {
	if (g.node(v).dummy == "border") {
	var predecessors = g.predecessors(v);
	if (predecessors.length != 0) {
	nextNorthPos = g.node(predecessors[0])["order"];
	scan(south, southPos, southLookahead, prevNorthPos, nextNorthPos);
	southPos = southLookahead;
	prevNorthPos = nextNorthPos;
	}
	}
	scan(south, southPos, south.length, nextNorthPos, north.length);
	});

	return south;
	}

	layering.reduce(visitLayer);
	return conflicts;
	}

	findOtherInnerSegmentNode(Graph g, v) {
	if (g.node(v)["dummy"]) {
	return g.predecessors(v).firstWhere((u) {
	return g.node(u)["dummy"];
	});
	}
	}

	addConflict(Map conflicts, v, w) {
	if (v > w) {
	var tmp = v;
	v = w;
	w = tmp;
	}

	var conflictsV = conflicts[v];
	if (!conflictsV) {
	conflicts[v] = conflictsV = {};
	}
	conflictsV[w] = true;
	}

	bool hasConflict(Map conflicts, v, w) {
	if (v > w) {
	var tmp = v;
	v = w;
	w = tmp;
	}
	return conflicts[v].containsKey(w);
	}

	/// Try to align nodes into vertical "blocks" where possible. This algorithm
	/// attempts to align a node with one of its median neighbors. If the edge
	/// connecting a neighbor is a type-1 conflict then we ignore that possibility.
	/// If a previous node has already formed a block with a node after the node
	/// we're trying to form a block with, we also ignore that possibility - our
	/// blocks would be split in that scenario.
	Map verticalAlignment(Graph g, Iterable layering, Map conflicts, Iterable neighborFn(v)) {
	var root = {},
	align = {},
	pos = {};

	// We cache the position here based on the layering because the graph and
	// layering may be out of sync. The layering matrix is manipulated to
	// generate different extreme alignments.
	layering.forEach((layer) {
	layer.forEach((v, order) {
	root[v] = v;
	align[v] = v;
	pos[v] = order;
	});
	});

	layering.forEach((layer) {
	var prevIdx = -1;
	layer.forEach((v) {
	var ws = neighborFn(v);
	if (ws.length != 0) {
	ws = ws.sort((w) => pos[w]);
	var mp = (ws.length - 1) / 2;
	for (var i = mp.floor(), il = mp.ceil(); i <= il; ++i) {
	var w = ws[i];
	if (align[v] == v &&
	prevIdx < pos[w] &&
	!hasConflict(conflicts, v, w)) {
	align[w] = v;
	align[v] = root[v] = root[w];
	prevIdx = pos[w];
	}
	}
	}
	});
	});

	return { "root": root, "align": align };
	}

	Map horizontalCompaction(Graph g, Iterable layering, root, align, [bool reverseSep=false]) {
	// We use local variables for these parameters instead of manipulating the
	// graph because it becomes more verbose to access them in a chained manner.
	var shift = {},
	shiftNeighbor = {},
	sink = {},
	xs = {},
	pred = {},
	graphLabel = g.graph(),
	sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep);

	layering.forEach((layer) {
	layer.forEach((v, order) {
	sink[v] = v;
	shift[v] = double.INFINITY;
	pred[v] = layer[order - 1];
	});
	});

	g.nodes.forEach((v) {
	if (root[v] == v) {
	placeBlock(g, layering, sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, v);
	}
	});

	layering.forEach((layer) {
	layer.forEach((v) {
	xs[v] = xs[root[v]];
	// This line differs from the source paper. See
	// http://www.inf.uni-konstanz.de/~brandes/publications/ for details.
	if (v == root[v] && shift[sink[root[v]]] < double.INFINITY) {
	xs[v] += shift[sink[root[v]]];

	// Cascade shifts as necessary
	var w = shiftNeighbor[sink[root[v]]];
	if (w && shift[w] != double.INFINITY) {
	xs[v] += shift[w];
	}
	}
	});
	});

	return xs;
	}

	placeBlock(Graph g, layering, Function sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, v) {
	if (xs.containsKey(v)) return;
	xs[v] = 0;

	var w = v,
	u;
	do {
	if (pred[w]) {
	u = root[pred[w]];
	placeBlock(g, layering, sepFn, root, align, shift, shiftNeighbor, sink, pred, xs, u);
	if (sink[v] == v) {
	sink[v] = sink[u];
	}

	var delta = sepFn(g, w, pred[w]);
	if (sink[v] != sink[u]) {
	shift[sink[u]] = Math.min(shift[sink[u]], xs[v] - xs[u] - delta);
	shiftNeighbor[sink[u]] = sink[v];
	} else {
	xs[v] = Math.max(xs[v], xs[u] + delta);
	}
	}
	w = align[w];
	} while (w != v);
	}

	/// Returns the alignment that has the smallest width of the given alignments.
	Map findSmallestWidthAlignment(Graph g, Map<String, Map> xss) {
	return util.min(xss.values, (Map xs) {
	var min = util.min(xs.keys, (v) => xs[v] - width(g, v) / 2),
	max = util.max(xs.keys, (v) => xs[v] + width(g, v) / 2);
	return max - min;
	});
	}

	/// Align the coordinates of each of the layout alignments such that
	/// left-biased alignments have their minimum coordinate at the same point as
	/// the minimum coordinate of the smallest width alignment and right-biased
	/// alignments have their maximum coordinate at the same point as the maximum
	/// coordinate of the smallest width alignment.
	alignCoordinates(Map<String, Map> xss, Map alignTo) {
	var alignToMin = util.min(alignTo.values),
	alignToMax = util.max(alignTo.values);

	["u", "d"].forEach((vert) {
	["l", "r"].forEach((horiz) {
	var alignment = vert + horiz,
	delta;
	Map xs = xss[alignment];
	if (xs == alignTo) return;

	delta = horiz == "l" ? alignToMin - util.min(xs.values) : alignToMax - util.max(xs.values);

	if (delta) {
	xss[alignment] = util.mapValues(xs, (x, _) => x + delta);
	}
	});
	});
	}

	balance(Map<String, Map> xss, [align]) {
	return util.mapValues(xss["ul"], (_, v) {
	if (align != null) {
	return xss[align.toLowerCase()][v];
	} else {
	var xs = util.pluck(xss.values, v)..sort();
	return (xs[1] + xs[2]) / 2;
	}
	});
	}

	positionX(Graph g) {
	var layering = util.buildLayerMatrix(g);
	var conflicts = util.merge({}, [findType1Conflicts(g, layering),
	findType2Conflicts(g, layering)]);

	Map<String, Map> xss = {};
	var adjustedLayering;
	["u", "d"].forEach((vert) {
	adjustedLayering = vert == "u" ? layering : layering.reversed.toList();
	["l", "r"].forEach((horiz) {
	if (horiz == "r") {
	adjustedLayering = adjustedLayering.map((inner) {
	return inner.values.reverse();
	});
	}

	var neighborFn = (v) => (vert == "u" ? g.predecessors(v) : g.successors(v));
	var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn);
	Map xs = horizontalCompaction(g, adjustedLayering,
	align["root"], align["align"],
	horiz == "r");
	if (horiz == "r") {
	xs = util.mapValues(xs, (_, x) => -x);
	}
	xss[vert + horiz] = xs;
	});
	});

	var smallestWidth = findSmallestWidthAlignment(g, xss);
	alignCoordinates(xss, smallestWidth);
	return balance(xss, g.graph()["align"]);
	}

	sep(nodeSep, edgeSep, bool reverseSep) {
	return (Graph g, v, w) {
	Map vLabel = g.node(v),
	wLabel = g.node(w);
	var sum = 0,
	delta;

	sum += vLabel["width"] / 2;
	if (vLabel.containsKey("labelpos")) {
	switch (vLabel["labelpos"].toLowerCase()) {
	case "l": delta = -vLabel["width"] / 2; break;
	case "r": delta = vLabel["width"] / 2; break;
	}
	}
	if (delta != 0) {
	sum += reverseSep ? delta : -delta;
	}
	delta = 0;

	sum += (vLabel["dummy"] ? edgeSep : nodeSep) / 2;
	sum += (wLabel["dummy"] ? edgeSep : nodeSep) / 2;

	sum += wLabel["width"] / 2;
	if (wLabel.containsKey("labelpos")) {
	switch (wLabel["labelpos"].toLowerCase()) {
	case "l": delta = wLabel["width"] / 2; break;
	case "r": delta = -wLabel["width"] / 2; break;
	}
	}
	if (delta != 0) {
	sum += reverseSep ? delta : -delta;
	}
	delta = 0;

	return sum;
	};
	}

	width(Graph g, v) => g.node(v)["width"];