Update dependencies - add graphlib for mondrian
Modify importer/importer.py: add func as local dependency
Change-Id: I6ee8908e81b1e2179f6efdec9402ce6f11702dcc
diff --git a/importer/importer.py b/importer/importer.py
index e9ca32e..46df943 100755
--- a/importer/importer.py
+++ b/importer/importer.py
@@ -26,6 +26,7 @@
LOCAL_PACKAGES = {
'analyzer': '//dart/pkg/analyzer',
'flutter': '//lib/flutter/packages/flutter',
+ 'func' : '//dart/third_party/pkg/func',
'kernel': '//dart/pkg/kernel',
'linter': '//dart/third_party/pkg/linter',
'typed_mock': '//dart/pkg/typed_mock',
diff --git a/pub/graphlib/.gitignore b/pub/graphlib/.gitignore
new file mode 100644
index 0000000..ca47b0d
--- /dev/null
+++ b/pub/graphlib/.gitignore
@@ -0,0 +1,6 @@
+.DS_Store
+.idea
+.pub/
+build/
+packages
+pubspec.lock
diff --git a/pub/graphlib/BUILD.gn b/pub/graphlib/BUILD.gn
new file mode 100644
index 0000000..1932fbc
--- /dev/null
+++ b/pub/graphlib/BUILD.gn
@@ -0,0 +1,16 @@
+# This file is generated by importer.py for graphlib-0.0.3
+
+import("//build/dart/dart_package.gni")
+
+dart_package("graphlib") {
+ package_name = "graphlib"
+
+ source_dir = "lib"
+
+ disable_analysis = true
+
+ deps = [
+ "//third_party/dart-pkg/pub/charted",
+ "//third_party/dart-pkg/pub/browser",
+ ]
+}
diff --git a/pub/graphlib/LICENSE b/pub/graphlib/LICENSE
new file mode 100644
index 0000000..1bc3ff7
--- /dev/null
+++ b/pub/graphlib/LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2012-2015 Chris Pettitt
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/pub/graphlib/README.md b/pub/graphlib/README.md
new file mode 100644
index 0000000..341137b
--- /dev/null
+++ b/pub/graphlib/README.md
@@ -0,0 +1,10 @@
+# Graphlib
+
+Graphlib is a Dart library that provides data structures for undirected
+and directed multi-graphs along with algorithms that can be used with them.
+
+# License
+
+Graphlib is licensed under the terms of the MIT License. See the
+[LICENSE](LICENSE) file
+aor details.
diff --git a/pub/graphlib/lib/charted.dart b/pub/graphlib/lib/charted.dart
new file mode 100644
index 0000000..e17a1d8
--- /dev/null
+++ b/pub/graphlib/lib/charted.dart
@@ -0,0 +1,3 @@
+library graphlib.charted;
+
+export "src/layout/charted/render.dart";
diff --git a/pub/graphlib/lib/graphlib.dart b/pub/graphlib/lib/graphlib.dart
new file mode 100644
index 0000000..62521e9
--- /dev/null
+++ b/pub/graphlib/lib/graphlib.dart
@@ -0,0 +1,9 @@
+/// The graphlib library.
+///
+library graphlib;
+
+export 'src/graph.dart' show Graph, Edge, GraphException;
+export 'src/alg/alg.dart';
+export 'src/layout/layout.dart' show layout;
+
+export 'src/write.dart' show writeDot;
diff --git a/pub/graphlib/lib/src/alg/alg.dart b/pub/graphlib/lib/src/alg/alg.dart
new file mode 100644
index 0000000..0ad429a
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/alg.dart
@@ -0,0 +1,10 @@
+library graphlib.alg;
+
+export "dfs.dart" show dfs, preorder, postorder;
+export "dijkstra.dart" show dijkstra, dijkstraAll;
+export "components.dart";
+export "common.dart" show AlgorithmException, Path;
+export "tarjan.dart" show findCycles, tarjan;
+export "floyd_warshall.dart" show floydWarshall;
+export "prim.dart";
+export "topsort.dart" show topsort, isAcyclic, CycleException;
diff --git a/pub/graphlib/lib/src/alg/common.dart b/pub/graphlib/lib/src/alg/common.dart
new file mode 100644
index 0000000..1ad2004
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/common.dart
@@ -0,0 +1,32 @@
+library graphlib.alg.common;
+
+import "../graph.dart" show Edge;
+
+final weightFunc DEFAULT_WEIGHT_FUNC = (_) => 1;
+
+typedef num weightFunc(Edge e);
+typedef List<Edge> edgeFunc(v);
+
+class AlgorithmException implements Exception {
+ final String message;
+ AlgorithmException(this.message);
+ String toString() => message;
+}
+
+class Path<U> {
+ num distance;
+ U predecessor;
+ Path({this.distance: 0.0, this.predecessor});
+ bool operator ==(Path other) {
+ if (other == null) {
+ return false;
+ }
+ if (distance != other.distance) {
+ return false;
+ }
+ if (predecessor != other.predecessor) {
+ return false;
+ }
+ return true;
+ }
+}
diff --git a/pub/graphlib/lib/src/alg/components.dart b/pub/graphlib/lib/src/alg/components.dart
new file mode 100644
index 0000000..bf50660
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/components.dart
@@ -0,0 +1,27 @@
+library graphlib.alg.components;
+
+import "../graph.dart";
+
+List<List> components(Graph g) {
+ List<List> cmpts = [];
+ final visited = {};
+ List cmpt;
+
+ dfs(v) {
+ if (visited.containsKey(v)) return;
+ visited[v] = true;
+ cmpt.add(v);
+ g.successors(v).forEach(dfs);
+ g.predecessors(v).forEach(dfs);
+ }
+
+ g.nodes.forEach((v) {
+ cmpt = [];
+ dfs(v);
+ if (cmpt.length != 0) {
+ cmpts.add(cmpt);
+ }
+ });
+
+ return cmpts;
+}
diff --git a/pub/graphlib/lib/src/alg/dfs.dart b/pub/graphlib/lib/src/alg/dfs.dart
new file mode 100644
index 0000000..7d040c9
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/dfs.dart
@@ -0,0 +1,42 @@
+library graphlib.alg.dfs;
+
+import "../graph.dart";
+import "common.dart";
+
+/// A helper that preforms a pre- or post-order traversal on the input graph
+/// and returns the nodes in the order they were visited. This algorithm treats
+/// the input as undirected.
+///
+/// Order must be one of "pre" or "post".
+List dfs(Graph g, List vs, String order) {
+ final acc = [],
+ visited = {};
+ vs.forEach((v) {
+ if (!g.hasNode(v)) {
+ throw new AlgorithmException("Graph does not have node: $v");
+ }
+
+ _doDfs(g, v, order == "post", visited, acc);
+ });
+ return acc;
+}
+
+_doDfs(Graph g, v, bool postorder, Map visited, List acc) {
+ if (!visited.containsKey(v)) {
+ visited[v] = true;
+
+ if (!postorder) { acc.add(v); }
+ g.neighbors(v).forEach((w) {
+ _doDfs(g, w, postorder, visited, acc);
+ });
+ if (postorder) { acc.add(v); }
+ }
+}
+
+List preorder(Graph g, List vs) {
+ return dfs(g, vs, "pre");
+}
+
+List postorder(Graph g, List vs) {
+ return dfs(g, vs, "post");
+}
diff --git a/pub/graphlib/lib/src/alg/dijkstra.dart b/pub/graphlib/lib/src/alg/dijkstra.dart
new file mode 100644
index 0000000..f36c9a7
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/dijkstra.dart
@@ -0,0 +1,63 @@
+library graphlib.alg.dijkstra;
+
+import "../graph.dart";
+import "../data/priority_queue.dart";
+import "common.dart";
+
+Map<dynamic, Path> dijkstra(Graph g, source, [weightFunc weightFn, edgeFunc edgeFn]) {
+ return _runDijkstra(g, source.toString(),
+ weightFn == null ? DEFAULT_WEIGHT_FUNC : weightFn,
+ edgeFn == null ? (v) => g.outEdges(v) : edgeFn);
+}
+
+Map<dynamic, Path> _runDijkstra(Graph g, source, weightFunc weightFn, edgeFunc edgeFn) {
+ Map<dynamic, Path> results = {};
+ final pq = new PriorityQueue();
+ var v, vEntry;
+
+ updateNeighbors(Edge edge) {
+ final w = edge.v != v ? edge.v : edge.w,
+ wEntry = results[w],
+ weight = weightFn(edge);
+ final distance = (vEntry.distance != null ? vEntry.distance : 0.0) +
+ (weight != null ? weight : 0.0);
+
+ if (weight < 0) {
+ throw new AlgorithmException("dijkstra does not allow negative edge weights. "
+ "Bad edge: $edge Weight: $weight");
+ }
+
+ if (wEntry.distance != null && distance < wEntry.distance) {
+ wEntry.distance = distance;
+ wEntry.predecessor = v;
+ pq.decrease(w, distance);
+ }
+ };
+
+ g.nodes.forEach((v) {
+ var distance = v == source ? 0 : double.INFINITY;
+ results[v] = new Path(distance: distance);
+ pq.add(v, distance);
+ });
+
+ while (pq.length > 0) {
+ v = pq.removeMin();
+ vEntry = results[v];
+ if (vEntry.distance == double.INFINITY) {
+ break;
+ }
+
+ List<Edge> edges = edgeFn(v);
+ edges.forEach(updateNeighbors);
+ }
+
+ return results;
+}
+
+Map<dynamic, Map<dynamic, Path>> dijkstraAll(Graph g, [weightFunc weightFn, edgeFunc edgeFn]) {
+ var results = {};
+ g.nodes.forEach((v) {
+ results[v] = dijkstra(g, v, weightFn, edgeFn);
+ });
+ return results;
+}
diff --git a/pub/graphlib/lib/src/alg/floyd_warshall.dart b/pub/graphlib/lib/src/alg/floyd_warshall.dart
new file mode 100644
index 0000000..9ef7456
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/floyd_warshall.dart
@@ -0,0 +1,49 @@
+library graphlib.alg.floyd_warshall;
+
+import "../graph.dart";
+import "common.dart";
+
+Map<dynamic, Map<dynamic, Path>> floydWarshall(Graph g, [weightFunc weightFn, edgeFunc edgeFn]) {
+ return _runFloydWarshall(g,
+ weightFn == null ? DEFAULT_WEIGHT_FUNC : weightFn,
+ edgeFn == null ? (v) => g.outEdges(v) : edgeFn);
+}
+
+Map _runFloydWarshall(Graph g, weightFunc weightFn, edgeFunc edgeFn) {
+ Map<dynamic, Map<dynamic, Path>> results = {};
+ final nodes = g.nodes;
+
+ nodes.forEach((v) {
+ results[v] = {};
+ results[v][v] = new Path(distance: 0);
+ nodes.forEach((w) {
+ if (v != w) {
+ results[v][w] = new Path(distance: double.INFINITY);
+ }
+ });
+ edgeFn(v).forEach((Edge edge) {
+ var w = edge.v == v ? edge.w : edge.v,
+ d = weightFn(edge);
+ results[v][w] = new Path(distance: d, predecessor: v);
+ });
+ });
+
+ nodes.forEach((k) {
+ var rowK = results[k];
+ nodes.forEach((i) {
+ var rowI = results[i];
+ nodes.forEach((j) {
+ var ik = rowI[k];
+ var kj = rowK[j];
+ var ij = rowI[j];
+ var altDistance = ik.distance + kj.distance;
+ if (altDistance < ij.distance) {
+ ij.distance = altDistance;
+ ij.predecessor = kj.predecessor;
+ }
+ });
+ });
+ });
+
+ return results;
+}
diff --git a/pub/graphlib/lib/src/alg/prim.dart b/pub/graphlib/lib/src/alg/prim.dart
new file mode 100644
index 0000000..31b4d1c
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/prim.dart
@@ -0,0 +1,52 @@
+library graphlib.alg.prim;
+
+import "../data/priority_queue.dart" show PriorityQueue;
+import "../graph.dart" show Graph, Edge;
+import "common.dart";
+
+Graph prim(Graph g, weightFunc weightFn) {
+ final result = new Graph(),
+ parents = {},
+ pq = new PriorityQueue();
+ var v;
+
+ updateNeighbors(Edge edge) {
+ var w = edge.v == v ? edge.w : edge.v,
+ pri = pq.priority(w);
+ if (pri != null) {
+ var edgeWeight = weightFn(edge);
+ if (edgeWeight < pri) {
+ parents[w] = v;
+ pq.decrease(w, edgeWeight);
+ }
+ }
+ }
+
+ if (g.nodeCount == 0) {
+ return result;
+ }
+
+ g.nodes.forEach((v) {
+ pq.add(v, double.INFINITY);
+ result.setNode(v);
+ });
+
+ // Start from an arbitrary node
+ pq.decrease(g.nodes.first, 0);
+
+ bool init = false;
+ while (pq.length > 0) {
+ v = pq.removeMin();
+ if (parents.containsKey(v)) {
+ result.setEdge(v, parents[v]);
+ } else if (init) {
+ throw new AlgorithmException("Input graph is not connected: $g");
+ } else {
+ init = true;
+ }
+
+ g.nodeEdges(v).forEach(updateNeighbors);
+ }
+
+ return result;
+}
diff --git a/pub/graphlib/lib/src/alg/tarjan.dart b/pub/graphlib/lib/src/alg/tarjan.dart
new file mode 100644
index 0000000..2f74f49
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/tarjan.dart
@@ -0,0 +1,52 @@
+library graphlib.alg.tarjan;
+
+import "dart:math" as Math;
+import "../graph.dart" show Graph;
+
+List<List> tarjan(Graph g) {
+ var index = 0;
+ final stack = [],
+ visited = {}, // node id -> { onStack, lowlink, index }
+ results = [];
+
+ dfs(v) {
+ final entry = visited[v] = {
+ "onStack": true,
+ "lowlink": index,
+ "index": index++
+ };
+ stack.add(v);
+
+ g.successors(v).forEach((w) {
+ if (!visited.containsKey(w)) {
+ dfs(w);
+ entry["lowlink"] = Math.min(entry["lowlink"], visited[w]["lowlink"]);
+ } else if (visited[w]["onStack"]) {
+ entry["lowlink"] = Math.min(entry["lowlink"], visited[w]["index"]);
+ }
+ });
+
+ if (entry["lowlink"] == entry["index"]) {
+ final cmpt = [];
+ var w;
+ do {
+ w = stack.removeLast();
+ visited[w]["onStack"] = false;
+ cmpt.add(w);
+ } while (v != w);
+ results.add(cmpt);
+ }
+ }
+
+ g.nodes.forEach((v) {
+ if (!visited.containsKey(v)) {
+ dfs(v);
+ }
+ });
+
+ return results;
+}
+
+List<List> findCycles(Graph g) {
+ return tarjan(g).where((cmpt) => cmpt.length > 1).toList();
+}
diff --git a/pub/graphlib/lib/src/alg/topsort.dart b/pub/graphlib/lib/src/alg/topsort.dart
new file mode 100644
index 0000000..fc1c354
--- /dev/null
+++ b/pub/graphlib/lib/src/alg/topsort.dart
@@ -0,0 +1,46 @@
+library graphlib.alg.topsort;
+
+import "../graph.dart" show Graph;
+
+List topsort(Graph g) {
+ final visited = {},
+ stack = {},
+ results = [];
+
+ visit(node) {
+ if (stack.containsKey(node)) {
+ throw new CycleException();
+ }
+
+ if (!visited.containsKey(node)) {
+ stack[node] = true;
+ visited[node] = true;
+ g.predecessors(node).forEach(visit);
+ stack.remove(node);
+ results.add(node);
+ }
+ }
+
+ g.sinks.forEach(visit);
+
+ if (visited.length != g.nodeCount) {
+ throw new CycleException();
+ }
+
+ return results;
+}
+
+bool isAcyclic(Graph g) {
+ try {
+ topsort(g);
+ } on CycleException catch (e) {
+ return false;
+ }
+ return true;
+}
+
+class CycleException implements Exception {
+ final String message;
+ CycleException([this.message = ""]);
+ String toString() => message;
+}
diff --git a/pub/graphlib/lib/src/data/priority_queue.dart b/pub/graphlib/lib/src/data/priority_queue.dart
new file mode 100644
index 0000000..0b89293
--- /dev/null
+++ b/pub/graphlib/lib/src/data/priority_queue.dart
@@ -0,0 +1,117 @@
+library graphlib.data.priority_queue;
+
+/// A min-priority queue data structure. This algorithm is derived from Cormen,
+/// et al., "Introduction to Algorithms". The basic idea of a min-priority
+/// queue is that you can efficiently (in O(1) time) get the smallest key in
+/// the queue. Adding and removing elements takes O(log n) time. A key can
+/// have its priority decreased in O(log n) time.
+class PriorityQueue<T> {
+ List<Map<String, dynamic>> _arr = [];
+ Map<T, int> _keyIndices = {};
+
+ /// Returns the number of elements in the queue. Takes `O(1)` time.
+ int get length => _arr.length;
+
+ /// Returns the keys that are in the queue. Takes `O(n)` time.
+ List<T> get keys => _arr.map((Map x) => x['key']).toList();
+
+ /// Returns `true` if [key] is in the queue and `false` if not.
+ bool has(T key) => _keyIndices.containsKey(key);
+
+ /// Returns the priority for [key]. If [key] is not present in the queue
+ /// then this function returns `null`. Takes `O(1)` time.
+ num priority(T key) {
+ if (_keyIndices.containsKey(key)) {
+ var index = _keyIndices[key];
+ return _arr[index]['priority'];
+ }
+ return null;
+ }
+
+ /// Returns the key for the minimum element in this queue. If the queue is
+ /// empty this function throws a [PriorityQueueException]. Takes `O(1)` time.
+ T min() {
+ if (length == 0) {
+ throw new PriorityQueueException("Queue underflow");
+ }
+ return this._arr[0]['key'];
+ }
+
+ /// Inserts a new key into the priority queue. If the key already exists in
+ /// the queue this function returns `false`; otherwise it will return `true`.
+ /// Takes `O(n)` time.
+ bool add(T key, num priority) {
+ if (!_keyIndices.containsKey(key)) {
+ final index = _arr.length;
+ _keyIndices[key] = index;
+ _arr.add({'key': key, 'priority': priority});
+ _decrease(index);
+ return true;
+ }
+ return false;
+ }
+
+ /// Removes and returns the smallest key in the queue. Takes `O(log n)` time.
+ T removeMin() {
+ _swap(0, _arr.length - 1);
+ final min = _arr.removeLast();
+ _keyIndices.remove(min['key']);
+ _heapify(0);
+ return min['key'];
+ }
+
+ /// Decreases the priority for [key] to [priority]. If the new priority is
+ /// greater than the previous priority, this function will throw a [PriorityQueueException].
+ void decrease(T key, num priority) {
+ final index = _keyIndices[key];
+ if (priority > _arr[index]['priority']) {
+ throw new PriorityQueueException("New priority is greater than current priority. " +
+ "Key: $key Old: ${_arr[index]['priority']} New: $priority");
+ }
+ _arr[index]['priority'] = priority;
+ _decrease(index);
+ }
+
+ void _heapify(int i) {
+ int l = 2 * i,
+ r = l + 1,
+ largest = i;
+ if (l < _arr.length) {
+ largest = _arr[l]['priority'] < _arr[largest]['priority'] ? l : largest;
+ if (r < _arr.length) {
+ largest = _arr[r]['priority'] < _arr[largest]['priority'] ? r : largest;
+ }
+ if (largest != i) {
+ _swap(i, largest);
+ _heapify(largest);
+ }
+ }
+ }
+
+ void _decrease(int index) {
+ num priority = _arr[index]['priority'];
+ while (index != 0) {
+ final parent = index >> 1;
+ if (_arr[parent]['priority'] < priority) {
+ break;
+ }
+ _swap(index, parent);
+ index = parent;
+ }
+ }
+
+ void _swap(int i, int j) {
+ var origArrI = _arr[i];
+ var origArrJ = _arr[j];
+ _arr[i] = origArrJ;
+ _arr[j] = origArrI;
+ _keyIndices[origArrJ['key']] = i;
+ _keyIndices[origArrI['key']] = j;
+ }
+}
+
+class PriorityQueueException implements Exception {
+ final String message;
+ PriorityQueueException(this.message);
+ String toString() => message;
+}
diff --git a/pub/graphlib/lib/src/graph.dart b/pub/graphlib/lib/src/graph.dart
new file mode 100644
index 0000000..abd6005
--- /dev/null
+++ b/pub/graphlib/lib/src/graph.dart
@@ -0,0 +1,465 @@
+library graphlib.graph;
+
+import 'dart:math' show PI, E;
+const undefined = PI * E;
+
+const DEFAULT_EDGE_NAME = "\x00",
+ GRAPH_NODE = "\x00",
+ EDGE_KEY_DELIM = "\x01";
+
+typedef nodeLabelFn(v);
+typedef edgeLabelFn(v, w, name);
+
+// Implementation notes:
+//
+// * Node id query functions should return string ids for the nodes
+// * Edge id query functions should return an "edgeObj", edge object, that is
+// composed of enough information to uniquely identify an edge: {v, w, name}.
+// * Internally we use an "edgeId", a stringified form of the edgeObj, to
+// reference edges. This is because we need a performant way to look these
+// edges up and, object properties, which have string keys, are the closest
+// we're going to get to a performant hashtable in JavaScript.
+
+class Graph {
+ final bool _isDirected, _isMultigraph, _isCompound;
+
+ // Label for the graph itself
+ var _label;
+
+ // Defaults to be set when creating a new node
+ nodeLabelFn _defaultNodeLabelFn = (v) => null;
+
+ // Defaults to be set when creating a new edge
+ edgeLabelFn _defaultEdgeLabelFn = (v, w, name) => null;
+
+ // v -> label
+ final Map _nodes = {};
+
+ // v -> parent
+ Map _parent;
+
+ // v -> children
+ Map _children;
+
+ // v -> edgeObj
+ final Map<dynamic, Map<dynamic, Edge>> _in = {};
+
+ // u -> v -> Number
+ final Map _preds = {};
+
+ // v -> edgeObj
+ final Map<dynamic, Map<dynamic, Edge>> _out = {};
+
+ // v -> w -> Number
+ final Map _sucs = {};
+
+ // e -> edgeObj
+ final Map _edgeObjs = {};
+
+ // e -> label
+ final Map _edgeLabels = {};
+
+ Graph({bool directed: true, bool multigraph: false, bool compound: false}) :
+ _isDirected = directed, _isMultigraph = multigraph, _isCompound = compound {
+ if (_isCompound) {
+ // v -> parent
+ _parent = {};
+
+ // v -> children
+ _children = {};
+ _children[GRAPH_NODE] = {};
+ }
+ }
+
+ /* Number of nodes in the graph. Should only be changed by the implementation. */
+ int _nodeCount = 0;
+
+ /* Number of edges in the graph. Should only be changed by the implementation. */
+ int _edgeCount = 0;
+
+
+ /* === Graph functions ========= */
+
+ bool get isDirected => _isDirected;
+
+ bool get isMultigraph => _isMultigraph;
+
+ bool get isCompound => _isCompound;
+
+ setGraph(label) {
+ _label = label;
+ }
+
+ graph() => _label;
+
+
+ /* === Node functions ========== */
+
+ setDefaultNodeLabel(newDefault) {
+ defaultNodeLabelFn = (v) => newDefault;
+ }
+
+ void set defaultNodeLabelFn(nodeLabelFn newDefault) {
+ _defaultNodeLabelFn = newDefault;
+ }
+
+ int get nodeCount => _nodeCount;
+
+ Iterable get nodes => _nodes.keys;
+
+ Iterable get sources {
+ return nodes.where((v) {
+ return _in[v].isEmpty;
+ });
+ }
+
+ Iterable get sinks {
+ return nodes.where((v) {
+ return _out[v].isEmpty;
+ });
+ }
+
+ setNodes(List vs, [value=undefined]) {
+ vs.forEach((v) {
+ setNode(v, value);
+ });
+ }
+
+ setNode(v, [value=undefined]) {
+ if (_nodes.containsKey(v)) {
+ if (value != undefined) {
+ _nodes[v] = value;
+ }
+ return;
+ }
+
+ _nodes[v] = value != undefined ? value : _defaultNodeLabelFn(v);
+ if (_isCompound) {
+ _parent[v] = GRAPH_NODE;
+ _children[v] = {};
+ _children[GRAPH_NODE][v] = true;
+ }
+ _in[v] = {};
+ _preds[v] = {};
+ _out[v] = {};
+ _sucs[v] = {};
+ ++_nodeCount;
+ }
+
+ node(v) => _nodes[v];
+
+ hasNode(v) => _nodes.containsKey(v);
+
+ removeNode(v) {
+ if (_nodes.containsKey(v)) {
+ var removeEdge = (e) {
+ this.removeEdgeObj(_edgeObjs[e]);
+ };
+ _nodes.remove(v);
+ if (_isCompound) {
+ _removeFromParentsChildList(v);
+ _parent.remove(v);
+ children(v).toList().forEach((child) {
+ setParent(child);
+ });
+ _children.remove(v);
+ }
+ _in[v].keys.toList().forEach(removeEdge);
+ _in.remove(v);
+ _preds.remove(v);
+ _out[v].keys.toList().forEach(removeEdge);
+ _out.remove(v);
+ _sucs.remove(v);
+ --_nodeCount;
+ }
+ }
+
+ setParent(v, [parent=null]) {
+ if (!_isCompound) {
+ throw new GraphException("Cannot set parent in a non-compound graph");
+ }
+
+ if (parent == null) {
+ parent = GRAPH_NODE;
+ } else {
+ for (var ancestor = parent; ancestor != null; ancestor = this.parent(ancestor)) {
+ if (ancestor == v) {
+ throw new GraphException("Setting $parent as parent of $v would create create a cycle");
+ }
+ }
+
+ setNode(parent);
+ }
+
+ setNode(v);
+ _removeFromParentsChildList(v);
+ _parent[v] = parent;
+ _children[parent][v] = true;
+ }
+
+ _removeFromParentsChildList(v) => _children[this._parent[v]].remove(v);
+
+ parent(v) {
+ if (_isCompound) {
+ var parent = _parent[v];
+ if (parent != GRAPH_NODE) {
+ return parent;
+ }
+ }
+ }
+
+ Iterable children([vv = null]) {
+ var v = vv == null ? GRAPH_NODE : vv;
+ if (_isCompound) {
+ if (_children.containsKey(v)) {
+ return _children[v].keys;
+ }
+ } else if (vv == null) {
+ return nodes;
+ } else if (hasNode(v)) {
+ return [];
+ }
+ return null;
+ }
+
+ Iterable predecessors(v) {
+ if (_preds.containsKey(v)) {
+ return _preds[v].keys;
+ }
+ return null;
+ }
+
+ Iterable successors(v) {
+ if (_sucs.containsKey(v)) {
+ return _sucs[v].keys;
+ }
+ return null;
+ }
+
+ neighbors(v) {
+ var preds = predecessors(v);
+ if (preds != null) {
+ return union([preds, successors(v)]);
+ }
+ }
+
+ /* === Edge functions ========== */
+
+ setDefaultEdgeLabel(newDefault) {
+ defaultEdgeLabelFn = (v, w, name) => newDefault;
+ }
+
+ void set defaultEdgeLabelFn(edgeLabelFn newDefault) {
+ _defaultEdgeLabelFn = newDefault;
+ }
+
+ int get edgeCount => _edgeCount;
+
+ Iterable<Edge> get edges => _edgeObjs.values;
+
+ setPath(List vs, [value=undefined]) {
+ vs.reduce((v, w) {
+ if (value != undefined) {
+ setEdge(v, w, value);
+ } else {
+ setEdge(v, w);
+ }
+ return w;
+ });
+ }
+
+ setEdgeObj(Edge edge, [value=undefined]) => setEdge(edge.v, edge.w, value, edge.name);
+
+ setEdge(v, w, [value=undefined, name=null]) {
+ //setEdge({ v, w, [name] }, [value])
+ //setEdge() {
+ var /*v, w, name, value,*/
+ valueSpecified = value != undefined;
+
+ v = v.toString();
+ w = w.toString();
+ if (name != null) {
+ name = name.toString();
+ }
+
+ var e = edgeArgsToId(_isDirected, v, w, name);
+ if (_edgeLabels.containsKey(e)) {
+ if (valueSpecified) {
+ _edgeLabels[e] = value;
+ }
+ return;
+ }
+
+ if (name != null && !_isMultigraph) {
+ throw new GraphException("Cannot set a named edge when isMultigraph = false");
+ }
+
+ // It didn't exist, so we need to create it.
+ // First ensure the nodes exist.
+ setNode(v);
+ setNode(w);
+
+ _edgeLabels[e] = valueSpecified ? value : _defaultEdgeLabelFn(v, w, name);
+
+ var edgeObj = edgeArgsToObj(_isDirected, v, w, name);
+ // Ensure we add undirected edges in a consistent way.
+ v = edgeObj.v;
+ w = edgeObj.w;
+
+ //Object.freeze(edgeObj);
+ _edgeObjs[e] = edgeObj;
+ incrementOrInitEntry(_preds[w], v);
+ incrementOrInitEntry(_sucs[v], w);
+ _in[w][e] = edgeObj;
+ _out[v][e] = edgeObj;
+ _edgeCount++;
+ }
+
+ edgeObj(Edge edge) {
+ return _edgeLabels[edgeObjToId(_isDirected, edge)];
+ }
+
+ edge(v, w, [name=null]) {
+ return _edgeLabels[edgeArgsToId(_isDirected, v, w, name)];
+ }
+
+ bool hasEdgeObj(Edge edge) {
+ return _edgeLabels.containsKey(edgeObjToId(_isDirected, edge));
+ }
+
+ bool hasEdge(v, w, [name=null]) {
+ return _edgeLabels.containsKey(edgeArgsToId(_isDirected, v, w, name));
+ }
+
+ removeEdgeObj(Edge edge) {
+ _removeEdge(edgeObjToId(_isDirected, edge));
+ }
+
+ removeEdge(v, w, [name=null]) {
+ _removeEdge(edgeArgsToId(_isDirected, v, w, name));
+ }
+
+ _removeEdge(e) {
+ if (_edgeObjs.containsKey(e)) {
+ var edge = _edgeObjs[e];
+ var v = edge.v;
+ var w = edge.w;
+ _edgeLabels.remove(e);
+ _edgeObjs.remove(e);
+ decrementOrRemoveEntry(_preds[w], v);
+ decrementOrRemoveEntry(_sucs[v], w);
+ _in[w].remove(e);
+ _out[v].remove(e);
+ _edgeCount--;
+ }
+ }
+
+ Iterable<Edge> inEdges(v, [u=null]) {
+ if (_in.containsKey(v)) {
+ Map<dynamic, Edge> inV = _in[v];
+ Iterable<Edge> edges = inV.values;
+ if (u == null) {
+ return edges.toList();
+ }
+ return edges.where((edge) => edge.v == u).toList();
+ }
+ return null;
+ }
+
+ Iterable<Edge> outEdges(v, [w=null]) {
+ if (_out.containsKey(v)) {
+ Map<dynamic, Edge> outV = _out[v];
+ List<Edge> edges = outV.values.toList();
+ if (w == null) {
+ return new List<Edge>.from(edges);
+ }
+ return edges.where((Edge edge) => edge.w == w).toList();
+ }
+ return null;
+ }
+
+ Iterable<Edge> nodeEdges(v, [w=null]) {
+ var inEdges = this.inEdges(v, w);
+ if (inEdges != null) {
+ return inEdges.toList()..addAll(outEdges(v, w));
+ }
+ return null;
+ }
+}
+
+incrementOrInitEntry(Map map, k) {
+ if (map.containsKey(k)) {
+ map[k]++;
+ } else {
+ map[k] = 1;
+ }
+}
+
+decrementOrRemoveEntry(Map map, k) {
+ if (--map[k] == 0) { map.remove(k); }
+}
+
+edgeArgsToId(bool isDirected, v, w, [name=null]) {
+ if (!isDirected && v.compareTo(w) > 0) {
+ var tmp = v;
+ v = w;
+ w = tmp;
+ }
+ return v.toString() + EDGE_KEY_DELIM + w.toString() + EDGE_KEY_DELIM +
+ (name == null ? DEFAULT_EDGE_NAME : name.toString());
+}
+
+Edge edgeArgsToObj(bool isDirected, v, w, [name=null]) {
+ if (!isDirected && v.compareTo(w) > 0) {
+ var tmp = v;
+ v = w;
+ w = tmp;
+ }
+ //var edgeObj = { v: v, w: w };
+ var edgeObj = new Edge(v, w, name);
+ /*if (name != undefined) {
+ edgeObj.name = name;
+ }*/
+ return edgeObj;
+}
+
+edgeObjToId(bool isDirected, Edge edgeObj) {
+ return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name);
+}
+
+class Edge {
+ final dynamic v, w, name;
+ Edge(this.v, this.w, [this.name]);
+ bool operator ==(other) {
+ if (other == null) {
+ return false;
+ }
+ if (other is! Edge) {
+ return false;
+ }
+ if (other.v != v) {
+ return false;
+ }
+ if (other.w != w) {
+ return false;
+ }
+ if (other.name != name) {
+ return false;
+ }
+ return true;
+ }
+}
+
+class GraphException implements Exception {
+ final String message;
+ GraphException(this.message);
+ String toString() => message;
+}
+
+Iterable union(Iterable<Iterable> sets) {
+ var s = new Set();
+ for (var ss in sets) {
+ s = s.union(ss.toSet());
+ }
+ return s;
+}
diff --git a/pub/graphlib/lib/src/layout/acyclic.dart b/pub/graphlib/lib/src/layout/acyclic.dart
new file mode 100644
index 0000000..5665a8c
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/acyclic.dart
@@ -0,0 +1,61 @@
+library graphlib.layout.acyclic;
+
+import "../graph.dart" show Graph, Edge;
+import "greedy_fas.dart" show greedyFAS;
+import "util.dart" show uniqueId;
+
+run(Graph g) {
+ weightFn(Graph g) {
+ return (Edge e) => g.edgeObj(e)["weight"];
+ }
+
+ Iterable fas = (g.graph()["acyclicer"] == "greedy"
+ ? greedyFAS(g, weightFn(g))
+ : dfsFAS(g));
+ fas.forEach((Edge e) {
+ Map label = g.edgeObj(e);
+ g.removeEdgeObj(e);
+ label["forwardName"] = e.name;
+ label["reversed"] = true;
+ g.setEdge(e.w, e.v, label, uniqueId("rev"));
+ });
+}
+
+List dfsFAS(Graph g) {
+ final fas = [],
+ stack = {},
+ visited = {};
+
+ dfs(v) {
+ if (visited.containsKey(v)) {
+ return;
+ }
+ visited[v] = true;
+ stack[v] = true;
+ g.outEdges(v).forEach((e) {
+ if (stack.containsKey(e.w)) {
+ fas.add(e);
+ } else {
+ dfs(e.w);
+ }
+ });
+ stack.remove(v);
+ }
+
+ g.nodes.forEach(dfs);
+ return fas;
+}
+
+undo(Graph g) {
+ g.edges.forEach((Edge e) {
+ Map label = g.edgeObj(e);
+ if (label["reversed"]) {
+ g.removeEdgeObj(e);
+
+ var forwardName = label["forwardName"];
+ label.remove("reversed");
+ label.remove("forwardName");
+ g.setEdge(e.w, e.v, label, forwardName);
+ }
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/add_border_segments.dart b/pub/graphlib/lib/src/layout/add_border_segments.dart
new file mode 100644
index 0000000..bb96c26
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/add_border_segments.dart
@@ -0,0 +1,38 @@
+library graphlib.layout.add_border_segments;
+
+import "../graph.dart" show Graph;
+import "util.dart" as util;
+
+addBorderSegments(Graph g) {
+ dfs(v) {
+ final children = g.children(v);
+ Map node = g.node(v);
+ if (children.length != 0) {
+ children.forEach(dfs);
+ }
+
+ if (node.containsKey("minRank")) {
+ node["borderLeft"] = [];
+ node["borderRight"] = [];
+ for (var rank = node["minRank"], maxRank = node["maxRank"] + 1;
+ rank < maxRank;
+ ++rank) {
+ _addBorderNode(g, "borderLeft", "_bl", v, node, rank);
+ _addBorderNode(g, "borderRight", "_br", v, node, rank);
+ }
+ }
+ }
+
+ g.children().forEach(dfs);
+}
+
+_addBorderNode(Graph g, String prop, String prefix, sg, Map sgNode, rank) {
+ var label = { "width": 0, "height": 0, "rank": rank },
+ prev = sgNode[prop][rank - 1],
+ curr = util.addDummyNode(g, "border", label, prefix);
+ sgNode[prop][rank] = curr;
+ g.setParent(curr, sg);
+ if (prev) {
+ g.setEdge(prev, curr, { "weight": 1 });
+ }
+}
diff --git a/pub/graphlib/lib/src/layout/charted/arrows.dart b/pub/graphlib/lib/src/layout/charted/arrows.dart
new file mode 100644
index 0000000..2f8deee
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/arrows.dart
@@ -0,0 +1,39 @@
+library graphlib.layout.charted.arrows;
+
+import 'util.dart' as util;
+
+normal(parent, id, edge, type) {
+ var marker = parent.append("marker")
+ .attr("id", id)
+ .attr("viewBox", "0 0 10 10")
+ .attr("refX", 9)
+ .attr("refY", 5)
+ .attr("markerUnits", "strokeWidth")
+ .attr("markerWidth", 8)
+ .attr("markerHeight", 6)
+ .attr("orient", "auto");
+
+ var path = marker.append("path")
+ .attr("d", "M 0 0 L 10 5 L 0 10 z")
+ .style("stroke-width", 1)
+ .style("stroke-dasharray", "1,0");
+ util.applyStyle(path, edge[type + "Style"]);
+}
+
+vee(parent, id, edge, type) {
+ var marker = parent.append("marker")
+ .attr("id", id)
+ .attr("viewBox", "0 0 10 10")
+ .attr("refX", 9)
+ .attr("refY", 5)
+ .attr("markerUnits", "strokeWidth")
+ .attr("markerWidth", 8)
+ .attr("markerHeight", 6)
+ .attr("orient", "auto");
+
+ var path = marker.append("path")
+ .attr("d", "M 0 0 L 10 5 L 0 10 L 4 5 z")
+ .style("stroke-width", 1)
+ .style("stroke-dasharray", "1,0");
+ util.applyStyle(path, edge[type + "Style"]);
+}
diff --git a/pub/graphlib/lib/src/layout/charted/create_clusters.dart b/pub/graphlib/lib/src/layout/charted/create_clusters.dart
new file mode 100644
index 0000000..676320c
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/create_clusters.dart
@@ -0,0 +1,33 @@
+library graphlib.layout.charted.create_clusters;
+
+import 'util.dart' as util;
+
+createClusters(selection, g) {
+ var clusters = g.nodes().filter((v) { return util.isSubgraph(g, v); }),
+ svgClusters = selection.selectAll("g.cluster")
+ .data(clusters, (v) { return v; });
+
+ svgClusters.enter()
+ .append("g")
+ .attr("class", "cluster")
+ .style("opacity", 0)
+ .append("rect");
+ util.applyTransition(svgClusters.exit(), g)
+ .style("opacity", 0)
+ .remove();
+
+ util.applyTransition(svgClusters, g)
+ .style("opacity", 1);
+
+ util.applyTransition(svgClusters.selectAll("rect"), g)
+ .attr("width", (v) { return g.node(v).width; })
+ .attr("height", (v) { return g.node(v).height; })
+ .attr("x", (v) {
+ var node = g.node(v);
+ return node.x - node.width / 2;
+ })
+ .attr("y", (v) {
+ var node = g.node(v);
+ return node.y - node.height / 2;
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/charted/create_edge_labels.dart b/pub/graphlib/lib/src/layout/charted/create_edge_labels.dart
new file mode 100644
index 0000000..20fc8c0
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/create_edge_labels.dart
@@ -0,0 +1,31 @@
+library graphlib.layout.charted.create_edge_labels;
+
+import 'label/add_label.dart';
+import 'util.dart' as util;
+
+createEdgeLabels(selection, g) {
+ var svgEdgeLabels = selection.selectAll("g.edgeLabel")
+ .data(g.edges(), (e) { return util.edgeToId(e); })
+ .classed("update", true);
+
+ svgEdgeLabels.selectAll("*").remove();
+ svgEdgeLabels.enter()
+ .append("g")
+ .classed("edgeLabel", true)
+ .style("opacity", 0);
+ svgEdgeLabels.each((e) {
+ var edge = g.edge(e),
+ label = addLabel(d3.select(self), g.edge(e), 0, 0).classed("label", true),
+ bbox = label.node().getBBox();
+
+ if (edge.labelId) { label.attr("id", edge.labelId); }
+ if (!edge.containsKey("width")) { edge.width = bbox.width; }
+ if (!edge.containsKey("height")) { edge.height = bbox.height; }
+ });
+
+ util.applyTransition(svgEdgeLabels.exit(), g)
+ .style("opacity", 0)
+ .remove();
+
+ return svgEdgeLabels;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/create_edge_paths.dart b/pub/graphlib/lib/src/layout/charted/create_edge_paths.dart
new file mode 100644
index 0000000..d3db8ba
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/create_edge_paths.dart
@@ -0,0 +1,113 @@
+library graphlib.layout.charted.create_edge_paths;
+
+import 'intersect/intersect.dart';
+import 'util.dart' as util;
+
+createEdgePaths(selection, g, arrows) {
+ var svgPaths = selection.selectAll("g.edgePath")
+ .data(g.edges(), (e) { return util.edgeToId(e); })
+ .classed("update", true);
+
+ enter(svgPaths, g);
+ exit(svgPaths, g);
+
+ util.applyTransition(svgPaths, g)
+ .style("opacity", 1);
+
+ svgPaths.selectAll("path.path")
+ .each((e) {
+ var edge = g.edge(e);
+ edge.arrowheadId = _.uniqueId("arrowhead");
+
+ var domEdge = d3.select(self)
+ .attr("marker-end", () {
+ return "url(#" + edge.arrowheadId + ")";
+ })
+ .style("fill", "none");
+
+ util.applyTransition(domEdge, g)
+ .attr("d", (e) { return calcPoints(g, e); });
+
+ if (edge.id) { domEdge.attr("id", edge.id); }
+ util.applyStyle(domEdge, edge.style);
+ });
+
+ svgPaths.selectAll("defs *").remove();
+ svgPaths.selectAll("defs")
+ .each((e) {
+ var edge = g.edge(e),
+ arrowhead = arrows[edge.arrowhead];
+ arrowhead(d3.select(self), edge.arrowheadId, edge, "arrowhead");
+ });
+
+ return svgPaths;
+}
+
+calcPoints(g, e) {
+ var edge = g.edge(e),
+ tail = g.node(e.v),
+ head = g.node(e.w),
+ points = edge.points.slice(1, edge.points.length - 1);
+ points.unshift(intersectNode(tail, points[0]));
+ points.push(intersectNode(head, points[points.length - 1]));
+
+ return createLine(edge, points);
+}
+
+createLine(edge, points) {
+ var line = d3.svg.line()
+ .x((d) { return d.x; })
+ .y((d) { return d.y; });
+
+ if (_.has(edge, "lineInterpolate")) {
+ line.interpolate(edge.lineInterpolate);
+ }
+
+ if (_.has(edge, "lineTension")) {
+ line.tension(Number(edge.lineTension));
+ }
+
+ return line(points);
+}
+
+getCoords(elem) {
+ var bbox = elem.getBBox(),
+ matrix = elem.getTransformToElement(elem.ownerSVGElement)
+ .translate(bbox.width / 2, bbox.height / 2);
+ return { "x": matrix.e, "y": matrix.f };
+}
+
+enter(svgPaths, g) {
+ var svgPathsEnter = svgPaths.enter()
+ .append("g")
+ .attr("class", "edgePath")
+ .style("opacity", 0);
+ svgPathsEnter.append("path")
+ .attr("class", "path")
+ .attr("d", (e) {
+ var edge = g.edge(e),
+ sourceElem = g.node(e.v).elem,
+ points = _.range(edge.points.length).map(() { return getCoords(sourceElem); });
+ return createLine(edge, points);
+ });
+ svgPathsEnter.append("defs");
+}
+
+exit(svgPaths, g) {
+ var svgPathExit = svgPaths.exit();
+ util.applyTransition(svgPathExit, g)
+ .style("opacity", 0)
+ .remove();
+
+ util.applyTransition(svgPathExit.select("path.path"), g)
+ .attr("d", (e) {
+ var source = g.node(e.v);
+
+ if (source) {
+ var points = _.range(self.pathSegList.length).map(() { return source; });
+ return createLine({}, points);
+ } else {
+ return d3.select(self).attr("d");
+ }
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/charted/create_nodes.dart b/pub/graphlib/lib/src/layout/charted/create_nodes.dart
new file mode 100644
index 0000000..d754970
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/create_nodes.dart
@@ -0,0 +1,53 @@
+library graphlib.layout.charted.create_nodes;
+
+import 'label/add_label.dart';
+import 'util.dart' as util;
+
+createNodes(selection, g, shapes) {
+ var simpleNodes = g.nodes().filter((v) { return !util.isSubgraph(g, v); });
+ var svgNodes = selection.selectAll("g.node")
+ .data(simpleNodes, (v) { return v; })
+ .classed("update", true);
+
+ svgNodes.selectAll("*").remove();
+ svgNodes.enter()
+ .append("g")
+ .attr("class", "node")
+ .style("opacity", 0);
+ svgNodes.each((v) {
+ var node = g.node(v),
+ thisGroup = d3.select(self),
+ labelGroup = thisGroup.append("g").attr("class", "label"),
+ labelDom = addLabel(labelGroup, node),
+ shape = shapes[node.shape],
+ bbox = _.pick(labelDom.node().getBBox(), "width", "height");
+
+ node.elem = self;
+
+ if (node.id) { thisGroup.attr("id", node.id); }
+ if (node.labelId) { labelGroup.attr("id", node.labelId); }
+ util.applyClass(thisGroup, node["class"], (thisGroup.classed("update") ? "update " : "") + "node");
+
+ if (_.has(node, "width")) { bbox.width = node.width; }
+ if (_.has(node, "height")) { bbox.height = node.height; }
+
+ bbox.width += node.paddingLeft + node.paddingRight;
+ bbox.height += node.paddingTop + node.paddingBottom;
+ labelGroup.attr("transform", "translate(" +
+ ((node.paddingLeft - node.paddingRight) / 2) + "," +
+ ((node.paddingTop - node.paddingBottom) / 2) + ")");
+
+ var shapeSvg = shape(d3.select(self), bbox, node);
+ util.applyStyle(shapeSvg, node.style);
+
+ var shapeBBox = shapeSvg.node().getBBox();
+ node.width = shapeBBox.width;
+ node.height = shapeBBox.height;
+ });
+
+ util.applyTransition(svgNodes.exit(), g)
+ .style("opacity", 0)
+ .remove();
+
+ return svgNodes;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/intersect/intersect.dart b/pub/graphlib/lib/src/layout/charted/intersect/intersect.dart
new file mode 100644
index 0000000..b258bcb
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/intersect/intersect.dart
@@ -0,0 +1,36 @@
+library graphlib.layout.charted.intersect;
+
+export "line.dart";
+export "polygon.dart";
+export "rect.dart";
+
+intersectCircle(node, rx, point) {
+ return intersectEllipse(node, rx, rx, point);
+}
+
+intersectEllipse(node, rx, ry, point) {
+ // Formulae from: http://mathworld.wolfram.com/Ellipse-LineIntersection.html
+
+ var cx = node.x;
+ var cy = node.y;
+
+ var px = cx - point.x;
+ var py = cy - point.y;
+
+ var det = Math.sqrt(rx * rx * py * py + ry * ry * px * px);
+
+ var dx = Math.abs(rx * ry * px / det);
+ if (point.x < cx) {
+ dx = -dx;
+ }
+ var dy = Math.abs(rx * ry * py / det);
+ if (point.y < cy) {
+ dy = -dy;
+ }
+
+ return {x: cx + dx, y: cy + dy};
+}
+
+intersectNode(node, point) {
+ return node.intersect(point);
+}
diff --git a/pub/graphlib/lib/src/layout/charted/intersect/line.dart b/pub/graphlib/lib/src/layout/charted/intersect/line.dart
new file mode 100644
index 0000000..fae453e
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/intersect/line.dart
@@ -0,0 +1,68 @@
+library graphlib.layout.charted.intersect.line;
+
+/*
+ * Returns the point at which two lines, p and q, intersect or returns
+ * undefined if they do not intersect.
+ */
+intersectLine(p1, p2, q1, q2) {
+ // Algorithm from J. Avro, (ed.) Graphics Gems, No 2, Morgan Kaufmann, 1994,
+ // p7 and p473.
+
+ var a1, a2, b1, b2, c1, c2;
+ var r1, r2 , r3, r4;
+ var denom, offset, num;
+ var x, y;
+
+ // Compute a1, b1, c1, where line joining points 1 and 2 is F(x,y) = a1 x +
+ // b1 y + c1 = 0.
+ a1 = p2.y - p1.y;
+ b1 = p1.x - p2.x;
+ c1 = (p2.x * p1.y) - (p1.x * p2.y);
+
+ // Compute r3 and r4.
+ r3 = ((a1 * q1.x) + (b1 * q1.y) + c1);
+ r4 = ((a1 * q2.x) + (b1 * q2.y) + c1);
+
+ // Check signs of r3 and r4. If both point 3 and point 4 lie on
+ // same side of line 1, the line segments do not intersect.
+ if ((r3 != 0) && (r4 != 0) && sameSign(r3, r4)) {
+ return /*DONT_INTERSECT*/;
+ }
+
+ // Compute a2, b2, c2 where line joining points 3 and 4 is G(x,y) = a2 x + b2 y + c2 = 0
+ a2 = q2.y - q1.y;
+ b2 = q1.x - q2.x;
+ c2 = (q2.x * q1.y) - (q1.x * q2.y);
+
+ // Compute r1 and r2
+ r1 = (a2 * p1.x) + (b2 * p1.yy) + c2;
+ r2 = (a2 * p2.x) + (b2 * p2.y) + c2;
+
+ // Check signs of r1 and r2. If both point 1 and point 2 lie
+ // on same side of second line segment, the line segments do
+ // not intersect.
+ if ((r1 != 0) && (r2 != 0) && (sameSign(r1, r2))) {
+ return /*DONT_INTERSECT*/;
+ }
+
+ // Line segments intersect: compute intersection point.
+ denom = (a1 * b2) - (a2 * b1);
+ if (denom == 0) {
+ return /*COLLINEAR*/;
+ }
+
+ offset = (denom / 2).abs();
+
+ // The denom/2 is to get rounding instead of truncating. It
+ // is added or subtracted to the numerator, depending upon the
+ // sign of the numerator.
+ num = (b1 * c2) - (b2 * c1);
+ x = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom);
+
+ num = (a2 * c1) - (a1 * c2);
+ y = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom);
+
+ return { x: x, y: y };
+}
+
+sameSign(r1, r2) => r1 * r2 > 0;
diff --git a/pub/graphlib/lib/src/layout/charted/intersect/polygon.dart b/pub/graphlib/lib/src/layout/charted/intersect/polygon.dart
new file mode 100644
index 0000000..f115847
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/intersect/polygon.dart
@@ -0,0 +1,54 @@
+library graphlib.layout.charted.intersect.polygon;
+
+import "dart:math" as Math;
+import "line.dart";
+
+/// Returns the point ({x, y}) at which the point argument intersects with the
+/// node argument assuming that it has the shape specified by polygon.
+intersectPolygon(node, polyPoints, point) {
+ var x1 = node.x;
+ var y1 = node.y;
+
+ var intersections = [];
+
+ var minX = double.INFINITY,
+ minY = double.INFINITY;
+ polyPoints.forEach((entry) {
+ minX = Math.min(minX, entry.x);
+ minY = Math.min(minY, entry.y);
+ });
+
+ var left = x1 - node.width / 2 - minX;
+ var top = y1 - node.height / 2 - minY;
+
+ for (var i = 0; i < polyPoints.length; i++) {
+ var p1 = polyPoints[i];
+ var p2 = polyPoints[i < polyPoints.length - 1 ? i + 1 : 0];
+ var intersect = intersectLine(node, point,
+ {"x": left + p1.x, "y": top + p1.y}, {"x": left + p2.x, "y": top + p2.y});
+ if (intersect) {
+ intersections.push(intersect);
+ }
+ }
+
+ if (!intersections.length) {
+ print("NO INTERSECTION FOUND, RETURN NODE CENTER: $node");
+ return node;
+ }
+
+ if (intersections.length > 1) {
+ // More intersections, find the one nearest to edge end point
+ intersections.sort((p, q) {
+ var pdx = p.x - point.x,
+ pdy = p.y - point.y,
+ distp = Math.sqrt(pdx * pdx + pdy * pdy),
+
+ qdx = q.x - point.x,
+ qdy = q.y - point.y,
+ distq = Math.sqrt(qdx * qdx + qdy * qdy);
+
+ return (distp < distq) ? -1 : (distp == distq ? 0 : 1);
+ });
+ }
+ return intersections[0];
+}
diff --git a/pub/graphlib/lib/src/layout/charted/intersect/rect.dart b/pub/graphlib/lib/src/layout/charted/intersect/rect.dart
new file mode 100644
index 0000000..1c188d9
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/intersect/rect.dart
@@ -0,0 +1,32 @@
+library graphlib.layout.charted.intersect.rect;
+
+intersectRect(node, point) {
+ var x = node.x;
+ var y = node.y;
+
+ // Rectangle intersection algorithm from:
+ // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes
+ var dx = point.x - x;
+ var dy = point.y - y;
+ var w = node.width / 2;
+ var h = node.height / 2;
+
+ var sx, sy;
+ if (dy.abs() * w > dx.abs() * h) {
+ // Intersection is top or bottom of rect.
+ if (dy < 0) {
+ h = -h;
+ }
+ sx = dy == 0 ? 0 : h * dx / dy;
+ sy = h;
+ } else {
+ // Intersection is left or right of rect.
+ if (dx < 0) {
+ w = -w;
+ }
+ sx = w;
+ sy = dx == 0 ? 0 : w * dy / dx;
+ }
+
+ return {"x": x + sx, "y": y + sy};
+}
diff --git a/pub/graphlib/lib/src/layout/charted/label/add_html_label.dart b/pub/graphlib/lib/src/layout/charted/label/add_html_label.dart
new file mode 100644
index 0000000..4c89705
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/label/add_html_label.dart
@@ -0,0 +1,41 @@
+library graphlib.layout.charted.label.add_html_label;
+
+import "../util.dart" as util;
+
+addHtmlLabel(root, node) {
+ var fo = root
+ .append("foreignObject")
+ .attr("width", "100000");
+
+ var div = fo
+ .append("xhtml:div");
+
+ var label = node.label;
+ if (label is Function) {
+ div.insert(label);
+ } else if (label is Map) {
+ // Currently we assume this is a DOM object.
+ div.insert(() { return label; });
+ } else {
+ div.html(label);
+ }
+
+ util.applyStyle(div, node.labelStyle);
+ div.style("display", "inline-block");
+ // Fix for firefox
+ div.style("white-space", "nowrap");
+
+ // TODO find a better way to get dimensions for foreignObjects...
+ var w, h;
+ div
+ .each(() {
+ w = self.clientWidth;
+ h = self.clientHeight;
+ });
+
+ fo
+ .attr("width", w)
+ .attr("height", h);
+
+ return fo;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/label/add_label.dart b/pub/graphlib/lib/src/layout/charted/label/add_label.dart
new file mode 100644
index 0000000..d874732
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/label/add_label.dart
@@ -0,0 +1,23 @@
+library graphlib.layout.charted.label.add_label;
+
+import "add_html_label.dart";
+import "add_text_label.dart";
+
+addLabel(root, node) {
+ var label = node.label;
+ var labelSvg = root.append("g");
+
+ // Allow the label to be a string, a function that returns a DOM element, or
+ // a DOM element itself.
+ if (label is! String || node.labelType == "html") {
+ addHtmlLabel(labelSvg, node);
+ } else {
+ addTextLabel(labelSvg, node);
+ }
+
+ var labelBBox = labelSvg.node().getBBox();
+ labelSvg.attr("transform",
+ "translate(" + (-labelBBox.width / 2) + "," + (-labelBBox.height / 2) + ")");
+
+ return labelSvg;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/label/add_text_label.dart b/pub/graphlib/lib/src/layout/charted/label/add_text_label.dart
new file mode 100644
index 0000000..b71d611
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/label/add_text_label.dart
@@ -0,0 +1,43 @@
+library graphlib.layout.charted.label.add_text_label;
+
+import "../util.dart" as util;
+
+/// Attaches a text label to the specified root. Handles escape sequences.
+addTextLabel(root, node) {
+ var domNode = root.append("text");
+
+ var lines = processEscapeSequences(node.label).split("\n");
+ for (var i = 0; i < lines.length; i++) {
+ domNode
+ .append("tspan")
+ .attr("xml:space", "preserve")
+ .attr("dy", "1em")
+ .attr("x", "1")
+ .text(lines[i]);
+ }
+
+ util.applyStyle(domNode, node.labelStyle);
+
+ return domNode;
+}
+
+processEscapeSequences(text) {
+ var newText = "",
+ escaped = false,
+ ch;
+ for (var i = 0; i < text.length; ++i) {
+ ch = text[i];
+ if (escaped) {
+ switch(ch) {
+ case "n": newText += "\n"; break;
+ default: newText += ch;
+ }
+ escaped = false;
+ } else if (ch == "\\") {
+ escaped = true;
+ } else {
+ newText += ch;
+ }
+ }
+ return newText;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/position_edge_labels.dart b/pub/graphlib/lib/src/layout/charted/position_edge_labels.dart
new file mode 100644
index 0000000..8d2eb4a
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/position_edge_labels.dart
@@ -0,0 +1,18 @@
+library graphlib.layout.charted.position_edge_labels;
+
+import 'util.dart' as util;
+
+positionEdgeLabels(selection, g) {
+ var created = selection.filter(() { return !d3.select(self).classed("update"); });
+
+ translate(e) {
+ var edge = g.edge(e);
+ return _.has(edge, "x") ? "translate(" + edge.x + "," + edge.y + ")" : "";
+ }
+
+ created.attr("transform", translate);
+
+ util.applyTransition(selection, g)
+ .style("opacity", 1)
+ .attr("transform", translate);
+}
diff --git a/pub/graphlib/lib/src/layout/charted/position_nodes.dart b/pub/graphlib/lib/src/layout/charted/position_nodes.dart
new file mode 100644
index 0000000..6df48d9
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/position_nodes.dart
@@ -0,0 +1,18 @@
+library graphlib.layout.charted.position_nodes;
+
+import 'util.dart' as util;
+
+positionNodes(selection, g) {
+ var created = selection.filter(() { return !d3.select(self).classed("update"); });
+
+ translate(v) {
+ var node = g.node(v);
+ return "translate(" + node.x + "," + node.y + ")";
+ }
+
+ created.attr("transform", translate);
+
+ util.applyTransition(selection, g)
+ .style("opacity", 1)
+ .attr("transform", translate);
+}
diff --git a/pub/graphlib/lib/src/layout/charted/render.dart b/pub/graphlib/lib/src/layout/charted/render.dart
new file mode 100644
index 0000000..eb05605
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/render.dart
@@ -0,0 +1,122 @@
+library graphlib.layout.charted.render;
+
+import '../../graph.dart' show Graph;
+
+import "create_nodes.dart";
+import "create_clusters.dart";
+import "create_edge_labels.dart";
+import "create_edge_paths.dart";
+import "position_nodes.dart";
+import "position_edge_labels.dart";
+import "shapes.dart";
+import "arrows.dart";
+
+render(svg, g) {
+ preProcessGraph(g);
+
+ var outputGroup = createOrSelectGroup(svg, "output"),
+ clustersGroup = createOrSelectGroup(outputGroup, "clusters"),
+ edgePathsGroup = createOrSelectGroup(outputGroup, "edgePaths"),
+ edgeLabels = createEdgeLabels(createOrSelectGroup(outputGroup, "edgeLabels"), g),
+ nodes = createNodes(createOrSelectGroup(outputGroup, "nodes"), g, shapes);
+
+ layout(g);
+
+ positionNodes(nodes, g);
+ positionEdgeLabels(edgeLabels, g);
+ createEdgePaths(edgePathsGroup, g, arrows);
+ createClusters(clustersGroup, g);
+
+ postProcessGraph(g);
+}
+
+const NODE_DEFAULT_ATTRS = const {
+ "paddingLeft": 10,
+ "paddingRight": 10,
+ "paddingTop": 10,
+ "paddingBottom": 10,
+ "rx": 0,
+ "ry": 0,
+ "shape": "rect"
+};
+
+const EDGE_DEFAULT_ATTRS = const {
+ "arrowhead": "normal",
+ "lineInterpolate": "linear"
+};
+
+preProcessGraph(Graph g) {
+ g.nodes.forEach((v) {
+ var node = g.node(v);
+ if (!node.containsKey("label")) { node.label = v; }
+
+ if (node.containsKey("paddingX")) {
+ _.defaults(node, {
+ "paddingLeft": node.paddingX,
+ "paddingRight": node.paddingX
+ });
+ }
+
+ if (node.containsKey("paddingY")) {
+ _.defaults(node, {
+ "paddingTop": node.paddingY,
+ "paddingBottom": node.paddingY
+ });
+ }
+
+ if (node.containsKey("padding")) {
+ _.defaults(node, {
+ "paddingLeft": node.padding,
+ "paddingRight": node.padding,
+ "paddingTop": node.padding,
+ "paddingBottom": node.padding
+ });
+ }
+
+ _.defaults(node, NODE_DEFAULT_ATTRS);
+
+ ["paddingLeft", "paddingRight", "paddingTop", "paddingBottom"].forEach((k) {
+ node[k] = Number(node[k]);
+ });
+
+ // Save dimensions for restore during post-processing
+ if (node.containsKey("width")) { node._prevWidth = node.width; }
+ if (node.containsKey("height")) { node._prevHeight = node.height; }
+ });
+
+ g.edges.forEach((e) {
+ var edge = g.edge(e);
+ if (!edge.containsKey("label")) { edge.label = ""; }
+ _.defaults(edge, EDGE_DEFAULT_ATTRS);
+ });
+}
+
+postProcessGraph(g) {
+ g.nodes.forEach((v) {
+ var node = g.node(v);
+
+ // Restore original dimensions
+ if (node.containsKey("_prevWidth")) {
+ node.width = node._prevWidth;
+ } else {
+ node.remove("width");
+ }
+
+ if (node.containsKey("_prevHeight")) {
+ node.height = node._prevHeight;
+ } else {
+ node.remove("height");
+ }
+
+ node.remove("_prevWidth");
+ node.remove("_prevHeight");
+ });
+}
+
+createOrSelectGroup(root, name) {
+ var selection = root.select("g." + name);
+ if (selection.empty()) {
+ selection = root.append("g").attr("class", name);
+ }
+ return selection;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/shapes.dart b/pub/graphlib/lib/src/layout/charted/shapes.dart
new file mode 100644
index 0000000..64b63ae
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/shapes.dart
@@ -0,0 +1,50 @@
+library graphlib.layout.charted.shapes;
+
+import "dart:math" as Math;
+import "intersect/intersect.dart";
+
+rect(parent, bbox, node) {
+ var shapeSvg = parent.insert("rect", ":first-child")
+ .attr("rx", node.rx)
+ .attr("ry", node.ry)
+ .attr("x", -bbox.width / 2)
+ .attr("y", -bbox.height / 2)
+ .attr("width", bbox.width)
+ .attr("height", bbox.height);
+
+ node.intersect = (point) {
+ return intersectRect(node, point);
+ };
+
+ return shapeSvg;
+}
+
+ellipse(parent, bbox, node) {
+ var rx = bbox.width / 2,
+ ry = bbox.height / 2,
+ shapeSvg = parent.insert("ellipse", ":first-child")
+ .attr("x", -bbox.width / 2)
+ .attr("y", -bbox.height / 2)
+ .attr("rx", rx)
+ .attr("ry", ry);
+
+ node.intersect = (point) {
+ return intersectEllipse(node, rx, ry, point);
+ };
+
+ return shapeSvg;
+}
+
+circle(parent, bbox, node) {
+ var r = Math.max(bbox.width, bbox.height) / 2,
+ shapeSvg = parent.insert("circle", ":first-child")
+ .attr("x", -bbox.width / 2)
+ .attr("y", -bbox.height / 2)
+ .attr("r", r);
+
+ node.intersect = (point) {
+ return intersectCircle(node, r, point);
+ };
+
+ return shapeSvg;
+}
diff --git a/pub/graphlib/lib/src/layout/charted/util.dart b/pub/graphlib/lib/src/layout/charted/util.dart
new file mode 100644
index 0000000..c373f61
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/charted/util.dart
@@ -0,0 +1,44 @@
+library graphlib.layout.charted.util;
+
+/// Returns true if the specified node in the graph is a subgraph node. A
+/// subgraph node is one that contains other nodes.
+isSubgraph(g, v) {
+ return !!g.children(v).length;
+}
+
+edgeToId(e) {
+ return escapeId(e.v) + ":" + escapeId(e.w) + ":" + escapeId(e.name);
+}
+
+final ID_DELIM = ":";
+
+escapeId(str) {
+ return str ? str.toString().replaceAll(ID_DELIM, "\\:") : "";
+}
+
+applyStyle(dom, styleFn) {
+ if (styleFn) {
+ dom.attr("style", styleFn);
+ }
+}
+
+applyClass(dom, classFn, otherClasses) {
+ if (classFn) {
+ dom
+ .attr("class", classFn)
+ .attr("class", otherClasses + " " + dom.attr("class"));
+ }
+}
+
+applyTransition(selection, g) {
+ var graph = g.graph();
+
+ if (graph is Map) {
+ var transition = graph["transition"];
+ if (transition is Function) {
+ return transition(selection);
+ }
+ }
+
+ return selection;
+}
diff --git a/pub/graphlib/lib/src/layout/coordinate_system.dart b/pub/graphlib/lib/src/layout/coordinate_system.dart
new file mode 100644
index 0000000..0fcd653
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/coordinate_system.dart
@@ -0,0 +1,67 @@
+library graphlib.layout.coordinate_system;
+
+import "../graph.dart" show Graph, Edge;
+
+adjust(Graph g) {
+ var rankDir = g.graph()["rankdir"].toLowerCase();
+ if (rankDir == "lr" || rankDir == "rl") {
+ _swapWidthHeight(g);
+ }
+}
+
+undo(Graph g) {
+ var rankDir = g.graph()["rankdir"].toLowerCase();
+ if (rankDir == "bt" || rankDir == "rl") {
+ _reverseY(g);
+ }
+
+ if (rankDir == "lr" || rankDir == "rl") {
+ _swapXY(g);
+ _swapWidthHeight(g);
+ }
+}
+
+_swapWidthHeight(Graph g) {
+ g.nodes.forEach((v) { _swapWidthHeightOne(g.node(v)); });
+ g.edges.forEach((e) { _swapWidthHeightOne(g.edgeObj(e)); });
+}
+
+_swapWidthHeightOne(Map attrs) {
+ var w = attrs["width"];
+ attrs["width"] = attrs["height"];
+ attrs["height"] = w;
+}
+
+_reverseY(Graph g) {
+ g.nodes.forEach((v) { _reverseYOne(g.node(v)); });
+
+ g.edges.forEach((Edge e) {
+ var edge = g.edgeObj(e);
+ edge["points"].forEach(_reverseYOne);
+ if (edge.containsKey("y")) {
+ _reverseYOne(edge);
+ }
+ });
+}
+
+_reverseYOne(Map attrs) {
+ attrs["y"] = -attrs["y"];
+}
+
+_swapXY(Graph g) {
+ g.nodes.forEach((v) { _swapXYOne(g.node(v)); });
+
+ g.edges.forEach((Edge e) {
+ var edge = g.edgeObj(e);
+ edge["points"].forEach(_swapXYOne);
+ if (edge.containsKey("x")) {
+ _swapXYOne(edge);
+ }
+ });
+}
+
+_swapXYOne(Map attrs) {
+ var x = attrs["x"];
+ attrs["x"] = attrs["y"];
+ attrs["y"] = x;
+}
diff --git a/pub/graphlib/lib/src/layout/debug.dart b/pub/graphlib/lib/src/layout/debug.dart
new file mode 100644
index 0000000..1e31105
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/debug.dart
@@ -0,0 +1,31 @@
+library graphlib.layout.debug;
+
+import "util.dart" as util;
+import "../graph.dart" show Graph;
+
+/* istanbul ignore next */
+Graph debugOrdering(Graph g) {
+ var layerMatrix = util.buildLayerMatrix(g);
+
+ var h = new Graph(compound: true, multigraph: true)..setGraph({});
+
+ g.nodes.forEach((v) {
+ h.setNode(v, { "label": v });
+ h.setParent(v, "layer" + g.node(v)["rank"]);
+ });
+
+ g.edges.forEach((e) {
+ h.setEdge(e.v, e.w, {}, e.name);
+ });
+
+ layerMatrix.forEach((layer, i) {
+ var layerV = "layer$i";
+ h.setNode(layerV, { "rank": "same" });
+ layer.reduce((u, v) {
+ h.setEdge(u, v, { "style": "invis" });
+ return v;
+ });
+ });
+
+ return h;
+}
diff --git a/pub/graphlib/lib/src/layout/greedy_fas.dart b/pub/graphlib/lib/src/layout/greedy_fas.dart
new file mode 100644
index 0000000..a3c3819
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/greedy_fas.dart
@@ -0,0 +1,120 @@
+library graphlib.layout.greedy_fas;
+
+import "dart:math" as Math;
+import "dart:collection" show Queue;
+import "../graph.dart" show Graph;
+import "../alg/common.dart" show weightFunc;
+import "util.dart" show flatten, range;
+
+/// A greedy heuristic for finding a feedback arc set for a graph. A feedback
+/// arc set is a set of edges that can be removed to make a graph acyclic.
+/// The algorithm comes from: P. Eades, X. Lin, and W. F. Smyth, "A fast and
+/// effective heuristic for the feedback arc set problem." This implementation
+/// adjusts that from the paper to allow for weighted edges.
+
+var DEFAULT_WEIGHT_FN = () => 1;
+
+List greedyFAS(Graph g, [weightFunc weightFn]) {
+ if (g.nodeCount <= 1) {
+ return [];
+ }
+ var state = buildState(g, weightFn == null ? DEFAULT_WEIGHT_FN : weightFn);
+ var results = _doGreedyFAS(state["graph"], state["buckets"], state["zeroIdx"]);
+
+ // Expand multi-edges
+ return results.map((e) => flatten(g.outEdges(e.v, e.w)));
+}
+
+_doGreedyFAS(Graph g, List<Queue> buckets, int zeroIdx) {
+ var results = [],
+ sources = buckets[buckets.length - 1],
+ sinks = buckets[0];
+
+ var entry;
+ while (g.nodeCount != 0) {
+ while ((entry = sinks.removeLast())) { removeNode(g, buckets, zeroIdx, entry); }
+ while ((entry = sources.removeLast())) { removeNode(g, buckets, zeroIdx, entry); }
+ if (g.nodeCount != 0) {
+ for (var i = buckets.length - 2; i > 0; --i) {
+ entry = buckets[i].removeLast();
+ if (entry) {
+ results.addAll(removeNode(g, buckets, zeroIdx, entry, true));
+ break;
+ }
+ }
+ }
+ }
+
+ return results;
+}
+
+List removeNode(Graph g, List<Queue> buckets, int zeroIdx, entry, [collectPredecessors=false]) {
+ var results = collectPredecessors ? [] : null;
+
+ g.inEdges(entry.v).forEach((edge) {
+ var weight = g.edgeObj(edge),
+ uEntry = g.node(edge.v);
+
+ if (collectPredecessors) {
+ results.add({ "v": edge.v, "w": edge.w });
+ }
+
+ uEntry.out -= weight;
+ assignBucket(buckets, zeroIdx, uEntry);
+ });
+
+ g.outEdges(entry.v).forEach((edge) {
+ var weight = g.edgeObj(edge),
+ w = edge.w,
+ wEntry = g.node(w);
+ wEntry["in"] -= weight;
+ assignBucket(buckets, zeroIdx, wEntry);
+ });
+
+ g.removeNode(entry.v);
+
+ return results;
+}
+
+Map buildState(Graph g, weightFn) {
+ var fasGraph = new Graph(),
+ maxIn = 0,
+ maxOut = 0;
+
+ g.nodes.forEach((v) {
+ fasGraph.setNode(v, { "v": v, "in": 0, "out": 0 });
+ });
+
+ // Aggregate weights on nodes, but also sum the weights across multi-edges
+ // into a single edge for the fasGraph.
+ g.edges.forEach((e) {
+ var prevWeight = fasGraph.edge(e.v, e.w);
+ if (prevWeight == null) {
+ prevWeight = 0;
+ }
+ var weight = weightFn(e),
+ edgeWeight = prevWeight + weight;
+ fasGraph.setEdge(e.v, e.w, edgeWeight);
+ maxOut = Math.max(maxOut, fasGraph.node(e.v)["out"] += weight);
+ maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight);
+ });
+
+ var buckets = range(maxOut + maxIn + 3).map((_) => new Queue());
+ var zeroIdx = maxIn + 1;
+
+ fasGraph.nodes.forEach((v) {
+ assignBucket(buckets, zeroIdx, fasGraph.node(v));
+ });
+
+ return { "graph": fasGraph, "buckets": buckets, "zeroIdx": zeroIdx };
+}
+
+assignBucket(List<Queue> buckets, zeroIdx, entry) {
+ if (!entry.out) {
+ buckets[0].add(entry);
+ } else if (!entry["in"]) {
+ buckets[buckets.length - 1].add(entry);
+ } else {
+ buckets[entry.out - entry["in"] + zeroIdx].add(entry);
+ }
+}
diff --git a/pub/graphlib/lib/src/layout/layout.dart b/pub/graphlib/lib/src/layout/layout.dart
new file mode 100644
index 0000000..e27dfb3
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/layout.dart
@@ -0,0 +1,389 @@
+library graphlib.layout;
+
+import "dart:math" as Math;
+import "acyclic.dart" as acyclic;
+import "normalize.dart" as normalize;
+import "rank/rank.dart";
+import "parent_dummy_chains.dart";
+import "util.dart" show removeEmptyRanks, normalizeRanks;
+import "nesting_graph.dart" as nestingGraph;
+import "add_border_segments.dart";
+import "coordinate_system.dart" as coordinateSystem;
+import "order/order.dart";
+import "position/position.dart";
+import "util.dart" as util;
+import "../graph.dart" show Graph;
+
+layout(Graph g, [bool debugTiming=false]) {
+ var time = debugTiming ? util.time : util.notime;
+ time("layout", () {
+ var layoutGraph = time(" buildLayoutGraph",
+ () { return buildLayoutGraph(g); });
+ time(" runLayout", () { runLayout(layoutGraph, time); });
+ time(" updateInputGraph", () { updateInputGraph(g, layoutGraph); });
+ });
+}
+
+runLayout(Graph g, time) {
+ time(" makeSpaceForEdgeLabels", () { makeSpaceForEdgeLabels(g); });
+ time(" removeSelfEdges", () { removeSelfEdges(g); });
+ time(" acyclic", () { acyclic.run(g); });
+ time(" nestingGraph.run", () { nestingGraph.run(g); });
+ time(" rank", () { rank(util.asNonCompoundGraph(g)); });
+ time(" injectEdgeLabelProxies", () { injectEdgeLabelProxies(g); });
+ time(" removeEmptyRanks", () { removeEmptyRanks(g); });
+ time(" nestingGraph.cleanup", () { nestingGraph.cleanup(g); });
+ time(" normalizeRanks", () { normalizeRanks(g); });
+ time(" assignRankMinMax", () { assignRankMinMax(g); });
+ time(" removeEdgeLabelProxies", () { removeEdgeLabelProxies(g); });
+ time(" normalize.run", () { normalize.run(g); });
+ time(" parentDummyChains", () { parentDummyChains(g); });
+ time(" addBorderSegments", () { addBorderSegments(g); });
+ time(" order", () { order(g); });
+ time(" insertSelfEdges", () { insertSelfEdges(g); });
+ time(" adjustCoordinateSystem", () { coordinateSystem.adjust(g); });
+ time(" position", () { position(g); });
+ time(" positionSelfEdges", () { positionSelfEdges(g); });
+ time(" removeBorderNodes", () { removeBorderNodes(g); });
+ time(" normalize.undo", () { normalize.undo(g); });
+ time(" fixupEdgeLabelCoords", () { fixupEdgeLabelCoords(g); });
+ time(" undoCoordinateSystem", () { coordinateSystem.undo(g); });
+ time(" translateGraph", () { translateGraph(g); });
+ time(" assignNodeIntersects", () { assignNodeIntersects(g); });
+ time(" reversePoints", () { reversePointsForReversedEdges(g); });
+ time(" acyclic.undo", () { acyclic.undo(g); });
+}
+
+/*
+ * Copies final layout information from the layout graph back to the input
+ * graph. This process only copies whitelisted attributes from the layout graph
+ * to the input graph, so it serves as a good place to determine what
+ * attributes can influence layout.
+ */
+updateInputGraph(Graph inputGraph, Graph layoutGraph) {
+ inputGraph.nodes.forEach((v) {
+ Map inputLabel = inputGraph.node(v),
+ layoutLabel = layoutGraph.node(v);
+
+ if (inputLabel != null) {
+ inputLabel["x"] = layoutLabel["x"];
+ inputLabel["y"] = layoutLabel["y"];
+
+ if (layoutGraph.children(v).length != 0) {
+ inputLabel["width"] = layoutLabel["width"];
+ inputLabel["height"] = layoutLabel["height"];
+ }
+ }
+ });
+
+ inputGraph.edges.forEach((e) {
+ Map inputLabel = inputGraph.edgeObj(e),
+ layoutLabel = layoutGraph.edgeObj(e);
+
+ inputLabel["points"] = layoutLabel["points"];
+ if (layoutLabel.containsKey("x")) {
+ inputLabel["x"] = layoutLabel["x"];
+ inputLabel["y"] = layoutLabel["y"];
+ }
+ });
+
+ inputGraph.graph()["width"] = layoutGraph.graph()["width"];
+ inputGraph.graph()["height"] = layoutGraph.graph()["height"];
+}
+
+const graphNumAttrs = const ["nodesep", "edgesep", "ranksep", "marginx", "marginy"],
+ graphDefaults = const { "ranksep": 50, "edgesep": 20, "nodesep": 50, "rankdir": "tb" },
+ graphAttrs = const ["acyclicer", "ranker", "rankdir", "align"],
+ nodeNumAttrs = const ["width", "height"],
+ nodeDefaults = const { "width": 0, "height": 0 },
+ edgeNumAttrs = const ["minlen", "weight", "width", "height", "labeloffset"],
+ edgeDefaults = const {
+ "minlen": 1, "weight": 1, "width": 0, "height": 0,
+ "labeloffset": 10, "labelpos": "r"
+ },
+ edgeAttrs = const ["labelpos"];
+
+/// Constructs a new graph from the input graph, which can be used for layout.
+/// This process copies only whitelisted attributes from the input graph to the
+/// layout graph. Thus this function serves as a good place to determine what
+/// attributes can influence layout.
+buildLayoutGraph(Graph inputGraph) {
+ var g = new Graph(multigraph: true, compound: true),
+ graph = canonicalize(inputGraph.graph());
+
+ g.setGraph(util.merge({},
+ [graphDefaults,
+ selectNumberAttrs(graph, graphNumAttrs),
+ util.pick(graph, graphAttrs)]));
+
+ inputGraph.nodes.forEach((v) {
+ var node = canonicalize(inputGraph.node(v));
+ g.setNode(v, util.defaults(selectNumberAttrs(node, nodeNumAttrs), nodeDefaults));
+ g.setParent(v, inputGraph.parent(v));
+ });
+
+ inputGraph.edges.forEach((e) {
+ var edge = canonicalize(inputGraph.edgeObj(e));
+ g.setEdge(e, util.merge({},
+ [edgeDefaults,
+ selectNumberAttrs(edge, edgeNumAttrs),
+ util.pick(edge, edgeAttrs)]));
+ });
+
+ return g;
+}
+
+/// This idea comes from the Gansner paper: to account for edge labels in our
+/// layout we split each rank in half by doubling minlen and halving ranksep.
+/// Then we can place labels at these mid-points between nodes.
+///
+/// We also add some minimal padding to the width to push the label for the edge
+/// away from the edge itself a bit.
+makeSpaceForEdgeLabels(Graph g) {
+ var graph = g.graph();
+ graph["ranksep"] /= 2;
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ edge["minlen"] *= 2;
+ if (edge["labelpos"].toLowerCase() != "c") {
+ if (graph["rankdir"] == "TB" || graph["rankdir"] == "BT") {
+ edge["width"] += edge["labeloffset"];
+ } else {
+ edge["height"] += edge["labeloffset"];
+ }
+ }
+ });
+}
+
+/// Creates temporary dummy nodes that capture the rank in which each edge's
+/// label is going to, if it has one of non-zero width and height. We do this
+/// so that we can safely remove empty ranks while preserving balance for the
+/// label's position.
+injectEdgeLabelProxies(Graph g) {
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ if (edge["width"] && edge["height"]) {
+ Map v = g.node(e.v),
+ w = g.node(e.w),
+ label = { "rank": (w["rank"] - v["rank"]) / 2 + v["rank"], "e": e };
+ util.addDummyNode(g, "edge-proxy", label, "_ep");
+ }
+ });
+}
+
+assignRankMinMax(Graph g) {
+ var maxRank = 0;
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ if (node["borderTop"]) {
+ node["minRank"] = g.node(node["borderTop"])["rank"];
+ node["maxRank"] = g.node(node["borderBottom"])["rank"];
+ maxRank = Math.max(maxRank, node["maxRank"]);
+ }
+ });
+ g.graph()["maxRank"] = maxRank;
+}
+
+removeEdgeLabelProxies(Graph g) {
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ if (node["dummy"] == "edge-proxy") {
+ g.edgeObj(node["e"])["labelRank"] = node["rank"];
+ g.removeNode(v);
+ }
+ });
+}
+
+translateGraph(Graph g) {
+ var minX = double.INFINITY,
+ maxX = 0,
+ minY = double.INFINITY,
+ maxY = 0,
+ graphLabel = g.graph(),
+ marginX = graphLabel["marginx"],
+ marginY = graphLabel["marginy"];
+ if (marginX == null) {
+ marginX = 0;
+ }
+ if (marginY == null) {
+ marginY = 0;
+ }
+
+ getExtremes(Map attrs) {
+ var x = attrs["x"],
+ y = attrs["y"],
+ w = attrs["width"],
+ h = attrs["height"];
+ minX = Math.min(minX, x - w / 2);
+ maxX = Math.max(maxX, x + w / 2);
+ minY = Math.min(minY, y - h / 2);
+ maxY = Math.max(maxY, y + h / 2);
+ }
+
+ g.nodes.forEach((v) { getExtremes(g.node(v)); });
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ if (edge.containsKey("x")) {
+ getExtremes(edge);
+ }
+ });
+
+ minX -= marginX;
+ minY -= marginY;
+
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ node["x"] -= minX;
+ node["y"] -= minY;
+ });
+
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ edge["points"].forEach((p) {
+ p.x -= minX;
+ p.y -= minY;
+ });
+ if (edge.containsKey("x")) { edge["x"] -= minX; }
+ if (edge.containsKey("y")) { edge["y"] -= minY; }
+ });
+
+ graphLabel["width"] = maxX - minX + marginX;
+ graphLabel["height"] = maxY - minY + marginY;
+}
+
+assignNodeIntersects(Graph g) {
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e),
+ nodeV = g.node(e.v),
+ nodeW = g.node(e.w),
+ p1, p2;
+ if (edge["points"] == null) {
+ edge["points"] = [];
+ p1 = nodeW;
+ p2 = nodeV;
+ } else {
+ p1 = edge["points"][0];
+ p2 = edge["points"][edge["points"].length - 1];
+ }
+ edge["points"].insert(0, util.intersectRect(nodeV, p1));
+ edge["points"].add(util.intersectRect(nodeW, p2));
+ });
+}
+
+fixupEdgeLabelCoords(Graph g) {
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ if (edge.containsKey("x")) {
+ if (edge["labelpos"] == "l" || edge["labelpos"] == "r") {
+ edge["width"] -= edge["labeloffset"];
+ }
+ switch (edge["labelpos"]) {
+ case "l": edge["x"] -= edge["width"] / 2 + edge["labeloffset"]; break;
+ case "r": edge["x"] += edge["width"] / 2 + edge["labeloffset"]; break;
+ }
+ }
+ });
+}
+
+reversePointsForReversedEdges(Graph g) {
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ if (edge["reversed"]) {
+ edge["points"].reverse();
+ }
+ });
+}
+
+removeBorderNodes(Graph g) {
+ g.nodes.forEach((v) {
+ if (g.children(v).length != 0) {
+ Map node = g.node(v),
+ t = g.node(node["borderTop"]),
+ b = g.node(node["borderBottom"]),
+ l = g.node(node["borderLeft"].last),
+ r = g.node(node["borderRight"].last);
+
+ node["width"] = (r["x"] - l["x"]).abs();
+ node["height"] = (b["y"] - t["y"]).abs();
+ node["x"] = l["x"] + node["width"] / 2;
+ node["y"] = t["y"] + node["height"] / 2;
+ }
+ });
+
+ g.nodes.forEach((v) {
+ if (g.node(v)["dummy"] == "border") {
+ g.removeNode(v);
+ }
+ });
+}
+
+removeSelfEdges(Graph g) {
+ g.edges.forEach((e) {
+ if (e.v == e.w) {
+ Map node = g.node(e.v);
+ if (!node["selfEdges"]) {
+ node["selfEdges"] = [];
+ }
+ node["selfEdges"].add({ "e": e, "label": g.edgeObj(e) });
+ g.removeEdgeObj(e);
+ }
+ });
+}
+
+insertSelfEdges(Graph g) {
+ var layers = util.buildLayerMatrix(g);
+ layers.forEach((layer) {
+ var orderShift = 0;
+ layer.forEach((v, i) {
+ Map node = g.node(v);
+ node["order"] = i + orderShift;
+ node["selfEdges"].forEach((Map selfEdge) {
+ util.addDummyNode(g, "selfedge", {
+ "width": selfEdge["label"].width,
+ "height": selfEdge["label"].height,
+ "rank": node["rank"],
+ "order": i + (++orderShift),
+ "e": selfEdge["e"],
+ "label": selfEdge["label"]
+ }, "_se");
+ });
+ node.remove("selfEdges");
+ });
+ });
+}
+
+positionSelfEdges(Graph g) {
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ if (node["dummy"] == "selfedge") {
+ Map selfNode = g.node(node["e"].v);
+ var x = selfNode["x"] + selfNode["width"] / 2,
+ y = selfNode["y"],
+ dx = node["x"] - x,
+ dy = selfNode["height"] / 2;
+ g.setEdge(node["e"], node["label"]);
+ g.removeNode(v);
+ node["label"]["points"] = [
+ { "x": x + 2 * dx / 3, "y": y - dy },
+ { "x": x + 5 * dx / 6, "y": y - dy },
+ { "x": x + dx , "y": y },
+ { "x": x + 5 * dx / 6, "y": y + dy },
+ { "x": x + 2 * dx / 3, "y": y + dy },
+ ];
+ node["label"]["x"] = node["x"];
+ node["label"]["y"] = node["y"];
+ }
+ });
+}
+
+Map selectNumberAttrs(Map obj, Iterable attrs) {
+ return util.mapValues(util.pick(obj, attrs), (k, v) => num.parse(k));
+}
+
+Map canonicalize(Map attrs) {
+ var newAttrs = {};
+ attrs.forEach((v, k) {
+ newAttrs[k.toLowerCase()] = v;
+ });
+ return newAttrs;
+}
diff --git a/pub/graphlib/lib/src/layout/lodash.dart b/pub/graphlib/lib/src/layout/lodash.dart
new file mode 100644
index 0000000..e7e7a9e
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/lodash.dart
@@ -0,0 +1,84 @@
+library graphlib.layout.util.lodash;
+
+import "dart:math" as Math;
+
+min(Iterable<num> l, [Comparable<num> fn(v)]) {
+ if (fn == null) {
+ fn = (a) => a;
+ }
+ return l.reduce((value, elem) => fn(value).compareTo(fn(elem)) < 0 ? value : elem);
+}
+
+max(Iterable<num> l, [Comparable<num> fn(v)]) {
+ if (fn == null) {
+ fn = (a) => a;
+ }
+ return l.reduce((value, elem) => fn(value).compareTo(fn(elem)) > 0 ? value : elem);
+}
+
+List flatten(Iterable a) => a.expand((i) => i).toList();
+
+Map pick(Map a, List keys) {
+ var b = {};
+ keys.forEach((key) {
+ if (a.containsKey(key)) {
+ b[key] = a[key];
+ }
+ });
+ return b;
+}
+
+Map mapValues(Map a, Comparable fn(k, v)) {
+ var b = {};
+ a.forEach((k, v) {
+ b[k] = fn(k, v);
+ });
+ return b;
+}
+
+Map defaults(Map a, Map defs) {
+ defs.forEach((k, v) {
+ if (!a.containsKey(k)) {
+ a[k] = v;
+ }
+ });
+ return defs;
+}
+
+//Map merge(Map dest, Map src, fn(a, b), self) {
+Map merge(Map dest, Iterable<Map> sources) {
+ sources.forEach((Map src) {
+ src.forEach((k, v) {
+ if (dest.containsKey(k)) {
+ dest[k] = v;
+ }
+ });
+ });
+ return dest;
+}
+
+List pluck(Iterable<Map> arr, key) {
+ var l = [];
+ arr.forEach((m) {
+ if (m.containsKey(key)) {
+ l.add(m[key]);
+ }
+ });
+ return l;
+}
+
+int nextId = 0;
+uniqueId(prefix) => "$prefix${++nextId}";
+
+List<int> range(int start, [int stop, int step=1]) {
+ if (stop == null) {
+ stop = start;
+ start = 0;
+ }
+ var length = Math.max(0, ((stop - start) / step).ceil());
+ return new List<int>.generate(length, (int i) {
+ var xi = start;
+ start += step;
+ return xi;
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/nesting_graph.dart b/pub/graphlib/lib/src/layout/nesting_graph.dart
new file mode 100644
index 0000000..e14880c
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/nesting_graph.dart
@@ -0,0 +1,129 @@
+library graphlib.layout.nesting_graph;
+
+import "../graph.dart" show Graph;
+import "util.dart" as util;
+
+/// A nesting graph creates dummy nodes for the tops and bottoms of subgraphs,
+/// adds appropriate edges to ensure that all cluster nodes are placed between
+/// these boundries, and ensures that the graph is connected.
+///
+/// In addition we ensure, through the use of the minlen property, that nodes
+/// and subgraph border nodes to not end up on the same rank.
+///
+/// Preconditions:
+///
+/// 1. Input graph is a DAG
+/// 2. Nodes in the input graph has a minlen attribute
+///
+/// Postconditions:
+///
+/// 1. Input graph is connected.
+/// 2. Dummy nodes are added for the tops and bottoms of subgraphs.
+/// 3. The minlen attribute for nodes is adjusted to ensure nodes do not
+/// get placed on the same rank as subgraph border nodes.
+///
+/// The nesting graph idea comes from Sander, "Layout of Compound Directed
+/// Graphs."
+run(Graph g) {
+ var root = util.addDummyNode(g, "root", {}, "_root"),
+ depths = treeDepths(g);
+ var height = util.max(depths.values) - 1,
+ nodeSep = 2 * height + 1;
+
+ g.graph().nestingRoot = root;
+
+ // Multiply minlen by nodeSep to align nodes on non-border ranks.
+ g.edges.forEach((e) { g.edgeObj(e)["minlen"] *= nodeSep; });
+
+ // Calculate a weight that is sufficient to keep subgraphs vertically compact
+ var weight = sumWeights(g) + 1;
+
+ // Create border nodes and link them up
+ g.children().forEach((child) {
+ dfs(g, root, nodeSep, weight, height, depths, child);
+ });
+
+ // Save the multiplier for node layers for later removal of empty border
+ // layers.
+ g.graph()["nodeRankFactor"] = nodeSep;
+}
+
+dfs(Graph g, root, num nodeSep, num weight, num height, Map depths, v) {
+ var children = g.children(v);
+ if (children.length == 0) {
+ if (v != root) {
+ g.setEdge(root, v, { "weight": 0, "minlen": nodeSep });
+ }
+ return;
+ }
+
+ var top = util.addBorderNode(g, "_bt"),
+ bottom = util.addBorderNode(g, "_bb"),
+ label = g.node(v);
+
+ g.setParent(top, v);
+ label.borderTop = top;
+ g.setParent(bottom, v);
+ label.borderBottom = bottom;
+
+ children.forEach((child) {
+ dfs(g, root, nodeSep, weight, height, depths, child);
+
+ var childNode = g.node(child),
+ childTop = childNode.borderTop ? childNode.borderTop : child,
+ childBottom = childNode.borderBottom ? childNode.borderBottom : child,
+ thisWeight = childNode.borderTop ? weight : 2 * weight,
+ minlen = childTop != childBottom ? 1 : height - depths[v] + 1;
+
+ g.setEdge(top, childTop, {
+ "weight": thisWeight,
+ "minlen": minlen,
+ "nestingEdge": true
+ });
+
+ g.setEdge(childBottom, bottom, {
+ "weight": thisWeight,
+ "minlen": minlen,
+ "nestingEdge": true
+ });
+ });
+
+ if (g.parent(v) == null) {
+ g.setEdge(root, top, { "weight": 0, "minlen": height + depths[v] });
+ }
+}
+
+Map treeDepths(Graph g) {
+ var depths = {};
+ dfs(v, depth) {
+ var children = g.children(v);
+ if (children != null && children.length != 0) {
+ children.forEach((child) {
+ dfs(child, depth + 1);
+ });
+ }
+ depths[v] = depth;
+ }
+ g.children().forEach((v) { dfs(v, 1); });
+ return depths;
+}
+
+num sumWeights(Graph g) {
+ num acc = 0;
+ g.edges.forEach((e) {
+ return acc + g.edgeObj(e)["weight"];
+ });
+ return acc;
+}
+
+cleanup(Graph g) {
+ Map graphLabel = g.graph();
+ g.removeNode(graphLabel["nestingRoot"]);
+ graphLabel.remove("nestingRoot");
+ g.edges.forEach((e) {
+ Map edge = g.edgeObj(e);
+ if (edge["nestingEdge"]) {
+ g.removeEdgeObj(e);
+ }
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/normalize.dart b/pub/graphlib/lib/src/layout/normalize.dart
new file mode 100644
index 0000000..01c99be
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/normalize.dart
@@ -0,0 +1,82 @@
+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);
+ }
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/order/add_subgraph_constraints.dart b/pub/graphlib/lib/src/layout/order/add_subgraph_constraints.dart
new file mode 100644
index 0000000..0855cc8
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/add_subgraph_constraints.dart
@@ -0,0 +1,53 @@
+library graphlib.layout.order.add_subgraph_constraints;
+
+import "../../graph.dart" show Graph;
+
+addSubgraphConstraints(Graph g, Graph cg, Iterable vs) {
+ var prev = {},
+ rootPrev;
+
+ vs.forEach((v) {
+ var child = g.parent(v),
+ parent,
+ prevChild;
+ while (child != null) {
+ parent = g.parent(child);
+ if (parent != null) {
+ prevChild = prev[parent];
+ prev[parent] = child;
+ } else {
+ prevChild = rootPrev;
+ rootPrev = child;
+ }
+ if (prevChild != null && prevChild != child) {
+ cg.setEdge(prevChild, child);
+ return;
+ }
+ child = parent;
+ }
+ });
+
+ /*
+ function dfs(v) {
+ var children = v ? g.children(v) : g.children();
+ if (children.length) {
+ var min = Number.POSITIVE_INFINITY,
+ subgraphs = [];
+ _.each(children, function(child) {
+ var childMin = dfs(child);
+ if (g.children(child).length) {
+ subgraphs.push({ v: child, order: childMin });
+ }
+ min = Math.min(min, childMin);
+ });
+ _.reduce(_.sortBy(subgraphs, "order"), function(prev, curr) {
+ cg.setEdge(prev.v, curr.v);
+ return curr;
+ });
+ return min;
+ }
+ return g.node(v).order;
+ }
+ dfs(undefined);
+ */
+}
diff --git a/pub/graphlib/lib/src/layout/order/barycenter.dart b/pub/graphlib/lib/src/layout/order/barycenter.dart
new file mode 100644
index 0000000..0016b31
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/barycenter.dart
@@ -0,0 +1,27 @@
+library graphlib.layout.order.barycenter;
+
+import "../../graph.dart" show Graph;
+
+List<Map> barycenter(Graph g, Iterable movable) {
+ return movable.map((v) {
+ var inV = g.inEdges(v);
+ if (inV.length == 0) {
+ return { "v": v };
+ } else {
+ var result = { "sum": 0, "weight": 0 };
+ inV.forEach((e) {
+ Map edge = g.edgeObj(e),
+ nodeU = g.node(e.v);
+ var order = nodeU.containsKey("order") ? nodeU["order"] : 1;
+ result["sum"] += (edge["weight"] * order);
+ result["weight"] += edge["weight"];
+ });
+
+ return {
+ "v": v,
+ "barycenter": result["sum"] / result["weight"],
+ "weight": result["weight"]
+ };
+ }
+ }).toList();
+}
diff --git a/pub/graphlib/lib/src/layout/order/build_layer_graph.dart b/pub/graphlib/lib/src/layout/order/build_layer_graph.dart
new file mode 100644
index 0000000..08653ea
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/build_layer_graph.dart
@@ -0,0 +1,75 @@
+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;
+}
diff --git a/pub/graphlib/lib/src/layout/order/cross_count.dart b/pub/graphlib/lib/src/layout/order/cross_count.dart
new file mode 100644
index 0000000..0b34e7a
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/cross_count.dart
@@ -0,0 +1,65 @@
+library graphlib.layout.order.cross_count;
+
+import "../../graph.dart" show Graph;
+import "../util.dart" show flatten, range;
+
+/// A function that takes a layering (an array of layers, each with an array of
+/// ordererd nodes) and a graph and returns a weighted crossing count.
+///
+/// Pre-conditions:
+///
+/// 1. Input graph must be simple (not a multigraph), directed, and include
+/// only simple edges.
+/// 2. Edges in the input graph must have assigned weights.
+///
+/// Post-conditions:
+///
+/// 1. The graph and layering matrix are left unchanged.
+///
+/// This algorithm is derived from Barth, et al., "Bilayer Cross Counting."
+int crossCount(Graph g, List layering) {
+ var cc = 0;
+ for (var i = 1; i < layering.length; ++i) {
+ cc += twoLayerCrossCount(g, layering[i-1], layering[i]);
+ }
+ return cc;
+}
+
+int twoLayerCrossCount(Graph g, Iterable northLayer, Iterable southLayer) {
+ // Sort all of the edges between the north and south layers by their position
+ // in the north layer and then the south. Map these edges to the position of
+ // their head in the south layer.
+ var southPos = new Map.fromIterables(southLayer, range(southLayer.length));
+ var southEntries = flatten(northLayer.map((v) {
+ return g.outEdges(v).map((e) {
+ return { "pos": southPos[e.w], "weight": g.edgeObj(e)["weight"] };
+ }).toList()..sort((Map a, Map b) {
+ return a["pos"].compareTo(b["pos"]);
+ });
+ }));
+
+ // Build the accumulator tree
+ var firstIndex = 1;
+ while (firstIndex < southLayer.length) firstIndex <<= 1;
+ var treeSize = 2 * firstIndex - 1;
+ firstIndex -= 1;
+ var tree = new List.generate(treeSize, (_) => 0);
+
+ // Calculate the weighted crossings
+ var cc = 0;
+ /*_.each(*/southEntries.forEach((Map entry) {
+ var index = entry["pos"] + firstIndex;
+ tree[index] += entry["weight"];
+ var weightSum = 0;
+ while (index > 0) {
+ if (index % 2 != 0) {
+ weightSum += tree[index + 1];
+ }
+ index = (index - 1) >> 1;
+ tree[index] += entry["weight"];
+ }
+ cc += entry["weight"] * weightSum;
+ })/*)*/;
+
+ return cc;
+}
diff --git a/pub/graphlib/lib/src/layout/order/init_order.dart b/pub/graphlib/lib/src/layout/order/init_order.dart
new file mode 100644
index 0000000..a286f09
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/init_order.dart
@@ -0,0 +1,40 @@
+library graphlib.layout.order.init_order;
+
+import "../../graph.dart" show Graph;
+import "../util.dart" show min, max, range;
+
+/// Assigns an initial order value for each node by performing a DFS search
+/// starting from nodes in the first rank. Nodes are assigned an order in their
+/// rank as they are first visited.
+///
+/// This approach comes from Gansner, et al., "A Technique for Drawing Directed
+/// Graphs."
+///
+/// Returns a layering matrix with an array per layer and each layer sorted by
+/// the order of its nodes.
+List<List> initOrder(Graph g) {
+ var visited = {},
+ simpleNodes = g.nodes.where((v) {
+ return g.children(v).length == 0;
+ }).toList();
+ var maxRank = max(simpleNodes.map((v) {
+ var rank = g.node(v)["rank"];
+ return rank;
+ }));
+ var layers = range(maxRank + 1).map((_) => []).toList();
+
+ dfs(v) {
+ if (visited.containsKey(v)) return;
+ visited[v] = true;
+ var node = g.node(v);
+ layers[node["rank"]].add(v);
+ g.successors(v).forEach(dfs);
+ }
+
+ var orderedVs = simpleNodes..sort((a, b) {
+ return g.node(a)["rank"].compareTo(g.node(b)["rank"]);
+ });
+ orderedVs.forEach(dfs);
+
+ return layers;
+}
diff --git a/pub/graphlib/lib/src/layout/order/order.dart b/pub/graphlib/lib/src/layout/order/order.dart
new file mode 100644
index 0000000..13963d6
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/order.dart
@@ -0,0 +1,78 @@
+library graphlib.layout.order;
+
+import "init_order.dart" show initOrder;
+import "cross_count.dart" show crossCount;
+import "sort_subgraph.dart" show sortSubgraph;
+import "build_layer_graph.dart" show buildLayerGraph;
+import "add_subgraph_constraints.dart" show addSubgraphConstraints;
+import "../../graph.dart" show Graph;
+import "../util.dart" as util;
+
+/// Applies heuristics to minimize edge crossings in the graph and sets the best
+/// order solution as an order attribute on each node.
+///
+/// Pre-conditions:
+///
+/// 1. Graph must be DAG
+/// 2. Graph nodes must be objects with a "rank" attribute
+/// 3. Graph edges must have the "weight" attribute
+///
+/// Post-conditions:
+///
+/// 1. Graph nodes will have an "order" attribute based on the results of the
+/// algorithm.
+order(Graph g) {
+ var maxRank = util.maxRank(g),
+ downLayerGraphs = _buildLayerGraphs(g, util.range(1, maxRank + 1), "inEdges"),
+ upLayerGraphs = _buildLayerGraphs(g, util.range(maxRank - 1, -1, -1), "outEdges");
+
+ var layering = initOrder(g);
+ _assignOrder(g, layering);
+
+ var bestCC = double.INFINITY;
+ List<List> best;
+
+ for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {
+ _sweepLayerGraphs(i % 2 != 0 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2);
+
+ layering = util.buildLayerMatrix(g);
+ var cc = crossCount(g, layering);
+ if (cc < bestCC) {
+ lastBest = 0;
+ //best = _.cloneDeep(layering);
+ best = new List<List>.generate(layering.length, (i) => layering[i].toList());
+ bestCC = cc;
+ }
+ }
+
+ _assignOrder(g, best);
+}
+
+Iterable _buildLayerGraphs(Graph g, Iterable ranks, relationship) {
+ return ranks.map((rank) {
+ return buildLayerGraph(g, rank, relationship);
+ });
+}
+
+_sweepLayerGraphs(Iterable layerGraphs, biasRight) {
+ var cg = new Graph();
+ layerGraphs.forEach((lg) {
+ var root = lg.graph()["root"];
+ var sorted = sortSubgraph(lg, root, cg, biasRight);
+ int i = 0;
+ sorted["vs"].forEach((v) {
+ lg.node(v)["order"] = i;
+ i++;
+ });
+ addSubgraphConstraints(lg, cg, sorted["vs"]);
+ });
+}
+
+_assignOrder(Graph g, List<List> layering) {
+ layering.forEach((layer) {
+ int i = 0;
+ layer.forEach((v) {
+ g.node(v)["order"] = i++;
+ });
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/order/resolve_conflicts.dart b/pub/graphlib/lib/src/layout/order/resolve_conflicts.dart
new file mode 100644
index 0000000..21013e7
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/resolve_conflicts.dart
@@ -0,0 +1,120 @@
+library graphlib.layout.order.resolve_conflicts;
+
+import "dart:math" as Math;
+import "../../graph.dart" show Graph;
+import "../util.dart" as util;
+
+/// Given a list of entries of the form {v, barycenter, weight} and a
+/// constraint graph this function will resolve any conflicts between the
+/// constraint graph and the barycenters for the entries. If the barycenters for
+/// an entry would violate a constraint in the constraint graph then we coalesce
+/// the nodes in the conflict into a new node that respects the contraint and
+/// aggregates barycenter and weight information.
+///
+/// This implementation is based on the description in Forster, "A Fast and
+/// Simple Hueristic for Constrained Two-Level Crossing Reduction," thought it
+/// differs in some specific details.
+///
+/// Pre-conditions:
+///
+/// 1. Each entry has the form {v, barycenter, weight}, or if the node has
+/// no barycenter, then {v}.
+///
+/// Returns:
+///
+/// A new list of entries of the form {vs, i, barycenter, weight}. The list
+/// `vs` may either be a singleton or it may be an aggregation of nodes
+/// ordered such that they do not violate constraints from the constraint
+/// graph. The property `i` is the lowest original index of any of the
+/// elements in `vs`.
+List<Map> resolveConflicts(Iterable<Map> entries, Graph cg) {
+ var mappedEntries = {};
+ int i = 0;
+ entries.forEach((entry) {
+ var tmp = mappedEntries[entry["v"]] = {
+ "indegree": 0,
+ "in": [],
+ "out": [],
+ "vs": [entry["v"]],
+ "i": i
+ };
+ if (entry["barycenter"] != null) {
+ tmp["barycenter"] = entry["barycenter"];
+ tmp["weight"] = entry["weight"];
+ }
+ i++;
+ });
+
+ cg.edges.forEach((e) {
+ Map entryV = mappedEntries[e.v],
+ entryW = mappedEntries[e.w];
+ if (entryV != null && entryW != null) {
+ entryW["indegree"]++;
+ entryV["out"].add(mappedEntries[e.w]);
+ }
+ });
+
+ var sourceSet = mappedEntries.values.where((entry) {
+ return entry["indegree"] == null || entry["indegree"] == 0;
+ }).toList();
+
+ return doResolveConflicts(sourceSet);
+}
+
+List<Map> doResolveConflicts(List<Map> sourceSet) {
+ var entries = [];
+
+ handleIn(Map vEntry) {
+ return (Map uEntry) {
+ if (uEntry.containsKey("merged") && uEntry["merged"]) {
+ return;
+ }
+ if (uEntry["barycenter"] == null ||
+ vEntry["barycenter"] == null ||
+ uEntry["barycenter"] >= vEntry["barycenter"]) {
+ mergeEntries(vEntry, uEntry);
+ }
+ };
+ }
+
+ handleOut(Map vEntry) {
+ return (Map wEntry) {
+ wEntry["in"].add(vEntry);
+ if (--wEntry["indegree"] == 0) {
+ sourceSet.add(wEntry);
+ }
+ };
+ }
+
+ while (sourceSet.length != 0) {
+ Map entry = sourceSet.removeLast();
+ entries.add(entry);
+ entry["in"].reversed.forEach(handleIn(entry));
+ entry["out"].forEach(handleOut(entry));
+ }
+
+ return entries.where((entry) => !entry.containsKey("merged") || entry["merged"] == false).map((Map entry) {
+ return util.pick(entry, ["vs", "i", "barycenter", "weight"]);
+ }).toList();
+}
+
+mergeEntries(Map target, Map source) {
+ var sum = 0,
+ weight = 0;
+
+ if (target.containsKey("weight")) {
+ sum += target["barycenter"] * target["weight"];
+ weight += target["weight"];
+ }
+
+ if (source.containsKey("weight")) {
+ sum += source["barycenter"] * source["weight"];
+ weight += source["weight"];
+ }
+
+ target["vs"] = source["vs"].toList()..addAll(target["vs"]);
+ target["barycenter"] = sum / weight;
+ target["weight"] = weight;
+ target["i"] = Math.min(source["i"], target["i"]);
+ source["merged"] = true;
+}
diff --git a/pub/graphlib/lib/src/layout/order/sort.dart b/pub/graphlib/lib/src/layout/order/sort.dart
new file mode 100644
index 0000000..3d94ca6
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/sort.dart
@@ -0,0 +1,58 @@
+library graphlib.layout.order.sort;
+
+import "../util.dart" as util;
+
+Map sort(entries, [bool biasRight=false]) {
+ Map parts = util.partition(entries, (entry) {
+ return entry.containsKey("barycenter");
+ });
+ var sortable = parts["lhs"];
+ var unsortable = parts["rhs"]..sort((entryA, entryB) {
+ return -entryA["i"].compareTo(-entryB["i"]);
+ });
+ var vs = [],
+ sum = 0,
+ weight = 0,
+ vsIndex = 0;
+
+ sortable.sort(compareWithBias(biasRight));
+
+ vsIndex = consumeUnsortable(vs, unsortable, vsIndex);
+
+ sortable.forEach((Map entry) {
+ vsIndex += entry["vs"].length;
+ vs.add(entry["vs"]);
+ sum += entry["barycenter"] * entry["weight"];
+ weight += entry["weight"];
+ vsIndex = consumeUnsortable(vs, unsortable, vsIndex);
+ });
+
+ var result = { "vs": util.flatten(vs) };
+ if (weight != 0) {
+ result["barycenter"] = sum / weight;
+ result["weight"] = weight;
+ }
+ return result;
+}
+
+int consumeUnsortable(List vs, List unsortable, int index) {
+ var last;
+ while (unsortable.length != 0 && (last = unsortable.last)["i"] <= index) {
+ unsortable.removeLast();
+ vs.add(last["vs"]);
+ index++;
+ }
+ return index;
+}
+
+compareWithBias(bool bias) {
+ return (Map entryV, Map entryW) {
+ if (entryV["barycenter"] < entryW["barycenter"]) {
+ return -1;
+ } else if (entryV["barycenter"] > entryW["barycenter"]) {
+ return 1;
+ }
+
+ return !bias ? entryV["i"] - entryW["i"] : entryW["i"] - entryV["i"];
+ };
+}
diff --git a/pub/graphlib/lib/src/layout/order/sort_subgraph.dart b/pub/graphlib/lib/src/layout/order/sort_subgraph.dart
new file mode 100644
index 0000000..9fd6ed9
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/order/sort_subgraph.dart
@@ -0,0 +1,77 @@
+library graphlib.layout.order.sort_subgraph;
+
+import "../../graph.dart" show Graph;
+import "../util.dart" as util;
+import "barycenter.dart" show barycenter;
+import "resolve_conflicts.dart" show resolveConflicts;
+import "sort.dart" show sort;
+
+Map sortSubgraph(Graph g, v, Graph cg, [bool biasRight=false]) {
+ var movable = g.children(v),
+ node = g.node(v),
+ bl = node != null ? node["borderLeft"] : null,
+ br = node != null ? node["borderRight"]: null,
+ subgraphs = {};
+
+ if (bl != null) {
+ movable = movable.where((w) {
+ return w != bl && w != br;
+ });
+ }
+
+ var barycenters = barycenter(g, movable);
+ barycenters.forEach((Map entry) {
+ if (g.children(entry["v"]).length != 0) {
+ var subgraphResult = sortSubgraph(g, entry["v"], cg, biasRight);
+ subgraphs[entry["v"]] = subgraphResult;
+ if (subgraphResult.containsKey("barycenter")) {
+ mergeBarycenters(entry, subgraphResult);
+ }
+ }
+ });
+
+ var entries = resolveConflicts(barycenters, cg);
+ expandSubgraphs(entries, subgraphs);
+
+ var result = sort(entries, biasRight);
+
+ if (bl != null) {
+ result["vs"] = util.flatten([bl, result["vs"], br]);
+ if (g.predecessors(bl).length != 0) {
+ Map blPred = g.node(g.predecessors(bl).first),
+ brPred = g.node(g.predecessors(br).first);
+ if (!result.containsKey("barycenter")) {
+ result["barycenter"] = 0;
+ result["weight"] = 0;
+ }
+ result["barycenter"] = (result["barycenter"] * result["weight"] +
+ blPred["order"] + brPred["order"]) / (result["weight"] + 2);
+ result["weight"] += 2;
+ }
+ }
+
+ return result;
+}
+
+expandSubgraphs(Iterable<Map> entries, subgraphs) {
+ entries.forEach((entry) {
+ entry["vs"] = util.flatten(entry["vs"].map((v) {
+ if (subgraphs[v] != null) {
+ return subgraphs[v]["vs"];
+ }
+ return v;
+ }));
+ });
+}
+
+mergeBarycenters(Map target, Map other) {
+ if (target["barycenter"] != null) {
+ target["barycenter"] = (target["barycenter"] * target["weight"] +
+ other["barycenter"] * other["weight"]) /
+ (target["weight"] + other["weight"]);
+ target["weight"] += other["weight"];
+ } else {
+ target["barycenter"] = other["barycenter"];
+ target["weight"] = other["weight"];
+ }
+}
diff --git a/pub/graphlib/lib/src/layout/parent_dummy_chains.dart b/pub/graphlib/lib/src/layout/parent_dummy_chains.dart
new file mode 100644
index 0000000..cdc1fc3
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/parent_dummy_chains.dart
@@ -0,0 +1,87 @@
+library graphlib.layout.parent_dummy_chains;
+
+import "dart:math" as Math;
+import "../graph.dart" show Graph, Edge;
+
+parentDummyChains(Graph g) {
+ var postorderNums = postorder(g);
+
+ g.graph()["dummyChains"].forEach((v) {
+ Map node = g.node(v);
+ Edge edgeObj = node["edgeObj"];
+ Map pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w);
+ var path = pathData["path"],
+ lca = pathData["lca"],
+ pathIdx = 0,
+ pathV = path[pathIdx],
+ ascending = true;
+
+ while (v != edgeObj.w) {
+ node = g.node(v);
+
+ if (ascending) {
+ while ((pathV = path[pathIdx]) != lca &&
+ g.node(pathV)["maxRank"] < node["rank"]) {
+ pathIdx++;
+ }
+
+ if (pathV == lca) {
+ ascending = false;
+ }
+ }
+
+ if (!ascending) {
+ while (pathIdx < path.length - 1 &&
+ g.node(pathV = path[pathIdx + 1]).minRank <= node["rank"]) {
+ pathIdx++;
+ }
+ pathV = path[pathIdx];
+ }
+
+ g.setParent(v, pathV);
+ v = g.successors(v).first;
+ }
+ });
+}
+
+/// Find a path from v to w through the lowest common ancestor (LCA). Return the
+/// full path and the LCA.
+Map findPath(Graph g, postorderNums, v, w) {
+ var vPath = [],
+ wPath = [],
+ low = Math.min(postorderNums[v]["low"], postorderNums[w]["low"]),
+ lim = Math.max(postorderNums[v]["lim"], postorderNums[w]["lim"]),
+ parent,
+ lca;
+
+ // Traverse up from v to find the LCA
+ parent = v;
+ do {
+ parent = g.parent(parent);
+ vPath.add(parent);
+ } while (parent &&
+ (postorderNums[parent]["low"] > low || lim > postorderNums[parent]["lim"]));
+ lca = parent;
+
+ // Traverse from w to LCA
+ parent = w;
+ while ((parent = g.parent(parent)) != lca) {
+ wPath.add(parent);
+ }
+
+ return { "path": vPath.concat(wPath.reverse()), "lca": lca };
+}
+
+Map postorder(Graph g) {
+ var result = {},
+ lim = 0;
+
+ dfs(v) {
+ var low = lim;
+ g.children(v).forEach(dfs);
+ result[v] = { "low": low, "lim": lim++ };
+ }
+ g.children().forEach(dfs);
+
+ return result;
+}
diff --git a/pub/graphlib/lib/src/layout/position/bk.dart b/pub/graphlib/lib/src/layout/position/bk.dart
new file mode 100644
index 0000000..deb4382
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/position/bk.dart
@@ -0,0 +1,377 @@
+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"];
diff --git a/pub/graphlib/lib/src/layout/position/position.dart b/pub/graphlib/lib/src/layout/position/position.dart
new file mode 100644
index 0000000..4bfc493
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/position/position.dart
@@ -0,0 +1,27 @@
+library graphlib.layout.position;
+
+import "../util.dart" as util;
+import "../../graph.dart" show Graph;
+import "bk.dart" show positionX;
+
+position(Graph g) {
+ g = util.asNonCompoundGraph(g);
+
+ _positionY(g);
+ positionX(g).forEach((x, v) {
+ g.node(v)["x"] = x;
+ });
+}
+
+_positionY(Graph g) {
+ var layering = util.buildLayerMatrix(g),
+ rankSep = g.graph()["ranksep"],
+ prevY = 0;
+ layering.forEach((layer) {
+ var maxHeight = util.max(layer.map((v) => g.node(v)["height"]));
+ layer.forEach((v) {
+ g.node(v)["y"] = prevY + maxHeight / 2;
+ });
+ prevY += maxHeight + rankSep;
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/rank/feasible_tree.dart b/pub/graphlib/lib/src/layout/rank/feasible_tree.dart
new file mode 100644
index 0000000..55f82a8
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/rank/feasible_tree.dart
@@ -0,0 +1,81 @@
+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;
+ });
+}
diff --git a/pub/graphlib/lib/src/layout/rank/network_simplex.dart b/pub/graphlib/lib/src/layout/rank/network_simplex.dart
new file mode 100644
index 0000000..0c445e5
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/rank/network_simplex.dart
@@ -0,0 +1,215 @@
+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"];
+}
diff --git a/pub/graphlib/lib/src/layout/rank/rank.dart b/pub/graphlib/lib/src/layout/rank/rank.dart
new file mode 100644
index 0000000..088c745
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/rank/rank.dart
@@ -0,0 +1,51 @@
+library graphlib.layout.rank;
+
+import 'util.dart' show longestPath, slack;
+import 'feasible_tree.dart' show feasibleTree;
+import 'network_simplex.dart' show networkSimplex;
+import "../../graph.dart" show Graph;
+
+/// Assigns a rank to each node in the input graph that respects the "minlen"
+/// constraint specified on edges between nodes.
+///
+/// This basic structure is derived from Gansner, et al., "A Technique for
+/// Drawing Directed Graphs."
+///
+/// Pre-conditions:
+///
+/// 1. Graph must be a connected DAG
+/// 2. Graph nodes must be objects
+/// 3. Graph edges must have "weight" and "minlen" attributes
+///
+/// Post-conditions:
+///
+/// 1. Graph nodes will have a "rank" attribute based on the results of the
+/// algorithm. Ranks can start at any index (including negative), we'll
+/// fix them up later.
+rank(Graph g) {
+ switch (g.graph()["ranker"]) {
+ case "network-simplex":
+ networkSimplexRanker(g);
+ break;
+ case "tight-tree":
+ tightTreeRanker(g);
+ break;
+ case "longest-path":
+ longestPathRanker(g);
+ break;
+ default:
+ networkSimplexRanker(g);
+ }
+}
+
+// A fast and simple ranker, but results are far from optimal.
+const longestPathRanker = longestPath;
+
+tightTreeRanker(Graph g) {
+ longestPath(g);
+ feasibleTree(g);
+}
+
+networkSimplexRanker(Graph g) {
+ networkSimplex(g);
+}
diff --git a/pub/graphlib/lib/src/layout/rank/util.dart b/pub/graphlib/lib/src/layout/rank/util.dart
new file mode 100644
index 0000000..ba3cdbb
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/rank/util.dart
@@ -0,0 +1,53 @@
+library graphlib.layout.rank.util;
+
+import "../../graph.dart" show Graph, Edge;
+import "../util.dart" show min;
+
+/// Initializes ranks for the input graph using the longest path algorithm. This
+/// algorithm scales well and is fast in practice, it yields rather poor
+/// solutions. Nodes are pushed to the lowest layer possible, leaving the bottom
+/// ranks wide and leaving edges longer than necessary. However, due to its
+/// speed, this algorithm is good for getting an initial ranking that can be fed
+/// into other algorithms.
+///
+/// This algorithm does not normalize layers because it will be used by other
+/// algorithms in most cases. If using this algorithm directly, be sure to
+/// run normalize at the end.
+///
+/// Pre-conditions:
+///
+/// 1. Input graph is a DAG.
+/// 2. Input graph node labels can be assigned properties.
+///
+/// Post-conditions:
+///
+/// 1. Each node will be assign an (unnormalized) "rank" property.
+longestPath(Graph g) {
+ var visited = {};
+
+ dfs(v) {
+ Map label = g.node(v);
+ if (visited.containsKey(v)) {
+ return label["rank"];
+ }
+ visited[v] = true;
+
+ var rank = min(g.outEdges(v).map((e) {
+ return dfs(e.w) - g.edgeObj(e)["minlen"];
+ }));
+
+ if (rank == double.INFINITY) {
+ rank = 0;
+ }
+
+ return (label["rank"] = rank);
+ }
+
+ g.sources.forEach(dfs);
+}
+
+/// Returns the amount of slack for the given edge. The slack is defined as the
+/// difference between the length of the edge and its minimum length.
+num slack(Graph g, Edge e) {
+ return g.node(e.w)["rank"] - g.node(e.v)["rank"] - g.edgeObj(e)["minlen"];
+}
diff --git a/pub/graphlib/lib/src/layout/util.dart b/pub/graphlib/lib/src/layout/util.dart
new file mode 100644
index 0000000..c5915d5
--- /dev/null
+++ b/pub/graphlib/lib/src/layout/util.dart
@@ -0,0 +1,241 @@
+library graphlib.layout.util;
+
+import "dart:math" as Math;
+import "dart:collection" show SplayTreeMap;
+import "../graph.dart" show Graph;
+
+import "lodash.dart";
+export "lodash.dart";
+
+//module.exports = {
+// addDummyNode: addDummyNode,
+// simplify: simplify,
+// asNonCompoundGraph: asNonCompoundGraph,
+// successorWeights: successorWeights,
+// predecessorWeights: predecessorWeights,
+// intersectRect: intersectRect,
+// buildLayerMatrix: buildLayerMatrix,
+// normalizeRanks: normalizeRanks,
+// removeEmptyRanks: removeEmptyRanks,
+// addBorderNode: addBorderNode,
+// maxRank: maxRank,
+// partition: partition,
+// time: time,
+// notime: notime
+//};
+
+/// Adds a dummy node to the graph and return v.
+addDummyNode(Graph g, type, Map attrs, name) {
+ var v;
+ do {
+ v = uniqueId(name);
+ } while (g.hasNode(v));
+
+ attrs["dummy"] = type;
+ g.setNode(v, attrs);
+ return v;
+}
+
+/// Returns a new graph with only simple edges. Handles aggregation of data
+/// associated with multi-edges.
+Graph simplify(Graph g) {
+ var simplified = new Graph()..setGraph(g.graph());
+ g.nodes.forEach((v) { simplified.setNode(v, g.node(v)); });
+ g.edges.forEach((e) {
+ Map simpleLabel = simplified.edge(e.v, e.w),
+ label = g.edgeObj(e);
+ if (simpleLabel == null) {
+ simpleLabel = { "weight": 0, "minlen": 1 };
+ }
+ simplified.setEdge(e.v, e.w, {
+ "weight": simpleLabel["weight"] + label["weight"],
+ "minlen": Math.max(simpleLabel["minlen"], label["minlen"])
+ });
+ });
+ return simplified;
+}
+
+Graph asNonCompoundGraph(Graph g) {
+ var simplified = new Graph(multigraph: g.isMultigraph)..setGraph(g.graph());
+ g.nodes.forEach((v) {
+ if (g.children(v).length == 0) {
+ simplified.setNode(v, g.node(v));
+ }
+ });
+ g.edges.forEach((e) {
+ simplified.setEdge(e, g.edgeObj(e));
+ });
+ return simplified;
+}
+
+Map successorWeights(Graph g) {
+ var weightMap = g.nodes.map((v) {
+ var sucs = {};
+ g.outEdges(v).forEach((e) {
+ if (!sucs.containsKey(e.w)) sucs[e.w] = 0;
+ sucs[e.w] = sucs[e.w] + g.edgeObj(e)["weight"];
+ });
+ return sucs;
+ });
+ return new Map.fromIterables(g.nodes, weightMap);
+}
+
+Map predecessorWeights(Graph g) {
+ var weightMap = g.nodes.map((v) {
+ var preds = {};
+ g.inEdges(v).forEach((e) {
+ if (!preds.containsKey(e.v)) preds[e.v] = 0;
+ preds[e.v] = preds[e.v] + g.edgeObj(e).weight;
+ });
+ return preds;
+ });
+ return new Map.fromIterables(g.nodes, weightMap);
+}
+
+/// Finds where a line starting at point ({x, y}) would intersect a rectangle
+/// ({x, y, width, height}) if it were pointing at the rectangle's center.
+Map intersectRect(Map rect, Map point) {
+ var x = rect["x"];
+ var y = rect["y"];
+
+ // Rectangle intersection algorithm from:
+ // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes
+ var dx = point["x"] - x;
+ var dy = point["y"] - y;
+ var w = rect["width"] / 2;
+ var h = rect["height"] / 2;
+
+ if (dx == 0 && dy == 0) {
+ throw new LayoutException("Not possible to find intersection inside of the rectangle");
+ }
+
+ var sx, sy;
+ if (dy.abs() * w > dx.abs() * h) {
+ // Intersection is top or bottom of rect.
+ if (dy < 0) {
+ h = -h;
+ }
+ sx = h * dx / dy;
+ sy = h;
+ } else {
+ // Intersection is left or right of rect.
+ if (dx < 0) {
+ w = -w;
+ }
+ sx = w;
+ sy = w * dy / dx;
+ }
+
+ return { "x": x + sx, "y": y + sy };
+}
+
+/// Given a DAG with each node assigned "rank" and "order" properties, this
+/// function will produce a matrix with the ids of each node.
+List buildLayerMatrix(Graph g) {
+ var layering = range(maxRank(g) + 1).map((_) => new SplayTreeMap()).toList();
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ var rank = node["rank"];
+ if (rank != null) {
+ layering[rank][node["order"]] = v;
+ }
+ });
+ return layering.map((SplayTreeMap m) => m.values.toList()).toList();
+}
+
+/// Adjusts the ranks for all nodes in the graph such that all nodes v have
+/// rank(v) >= 0 and at least one node w has rank(w) = 0.
+normalizeRanks(Graph g) {
+ var minimum = min(g.nodes.map((v) => g.node(v)["rank"]));
+ g.nodes.forEach((v) {
+ Map node = g.node(v);
+ if (node.containsKey("rank")) {
+ node["rank"] -= minimum;
+ }
+ });
+}
+
+removeEmptyRanks(Graph g) {
+ // Ranks may not start at 0, so we need to offset them
+ var offset = min(g.nodes.map((v) => g.node(v).rank));
+
+ var layers = new SplayTreeMap();
+ g.nodes.forEach((v) {
+ var rank = g.node(v)["rank"] - offset;
+ if (!layers.containsKey(rank)) {
+ layers[rank] = [];
+ }
+ layers[rank].add(v);
+ });
+
+ var delta = 0,
+ nodeRankFactor = g.graph()["nodeRankFactor"],
+ i = 0;
+ layers.values.forEach((vs) {
+ if (vs == null && i % nodeRankFactor != 0) {
+ --delta;
+ } else if (delta != 0) {
+ vs.forEach((v) { g.node(v)["rank"] += delta; });
+ }
+ i++;
+ });
+}
+
+addBorderNode(g, prefix, [rank, order]) {
+ var node = {
+ "width": 0,
+ "height": 0
+ };
+ if (rank != null) {
+ node["rank"] = rank;
+ }
+ if (order != null) {
+ node["order"] = order;
+ }
+ return addDummyNode(g, "border", node, prefix);
+}
+
+maxRank(g) {
+ return max(g.nodes.map((v) {
+ var rank = g.node(v)["rank"];
+ if (rank != null) {
+ return rank;
+ }
+ }));
+}
+
+/// Partition a collection into two groups: `lhs` and `rhs`. If the supplied
+/// function returns true for an entry it goes into `lhs`. Otherwise it goes
+/// into `rhs.
+Map partition(Iterable collection, Function fn) {
+ var result = { "lhs": [], "rhs": [] };
+ collection.forEach((value) {
+ if (fn(value)) {
+ result["lhs"].add(value);
+ } else {
+ result["rhs"].add(value);
+ }
+ });
+ return result;
+}
+
+/// Returns a new function that wraps `fn` with a timer. The wrapper logs the
+/// time it takes to execute the function.
+time(String name, Function fn, [log(String s) = print]) {
+ var start = new DateTime.now().millisecondsSinceEpoch;
+ try {
+ return fn();
+ } finally {
+ log("$name time: ${new DateTime.now().millisecondsSinceEpoch - start}ms");
+ }
+}
+
+notime(String name, Function fn) {
+ return fn();
+}
+
+class LayoutException implements Exception {
+ final String message;
+ LayoutException(this.message);
+ String toString() => message;
+}
diff --git a/pub/graphlib/lib/src/write.dart b/pub/graphlib/lib/src/write.dart
new file mode 100644
index 0000000..9f37fac
--- /dev/null
+++ b/pub/graphlib/lib/src/write.dart
@@ -0,0 +1,129 @@
+library graphlib.write;
+
+import 'graph.dart';
+
+final UNESCAPED_ID_PATTERN = new RegExp(r"^[a-zA-Z\200-\377_][a-zA-Z\200-\377_0-9]*$");
+
+String writeDot(Graph g) {
+ var ec = g.isDirected ? "->" : "--";
+ var writer = new _Writer();
+
+ if (!g.isMultigraph) {
+ writer.write("strict ");
+ }
+
+ writer.writeLine((g.isDirected ? "digraph" : "graph") + " {");
+ writer.indent();
+
+ var graphAttrs = g.graph();
+ if (graphAttrs is Map) {
+ graphAttrs.forEach((v, k) {
+ writer.writeLine("${id(k)}=${id(v)};");
+ });
+ }
+
+ _writeSubgraph(g, null, writer);
+
+ g.edges.forEach((edge) {
+ _writeEdge(g, edge, ec, writer);
+ });
+
+ writer.unindent();
+ writer.writeLine("}");
+
+ return writer.toString();
+}
+
+void _writeSubgraph(Graph g, v, _Writer writer) {
+ var children = g.isCompound ? g.children(v) : g.nodes;
+ children.forEach((w) {
+ if (!g.isCompound || g.children(w).isEmpty) {
+ _writeNode(g, w, writer);
+ } else {
+ writer.writeLine("subgraph " + id(w) + " {");
+ writer.indent();
+
+ if (g.node(w) is Map) {
+ g.node(w).forEach((val, key) {
+ writer.writeLine("${id(key)}=${id(val)};");
+ });
+ }
+
+ _writeSubgraph(g, w, writer);
+ writer.unindent();
+ writer.writeLine("}");
+ }
+ });
+}
+
+_writeNode(Graph g, v, _Writer writer) {
+ writer.write(id(v));
+ _writeAttrs(g.node(v), writer);
+ writer.writeLine();
+}
+
+void _writeEdge(Graph g, edge, String ec, _Writer writer) {
+ var v = edge.v,
+ w = edge.w,
+ attrs = g.edgeObj(edge);
+
+ writer.write("${id(v)} $ec ${id(w)}");
+ _writeAttrs(attrs, writer);
+ writer.writeLine();
+}
+
+void _writeAttrs(attrs, _Writer writer) {
+ if (attrs is Map) {
+ var attrStrs = attrs.keys.map((key) {
+ return "${id(key)}=${id(attrs[key])}";
+ });
+ if (attrStrs.isNotEmpty) {
+ writer.write(" [" + attrStrs.join(",") + "]");
+ }
+ }
+}
+
+id(obj) {
+ if (obj is num || UNESCAPED_ID_PATTERN.hasMatch(obj.toString())) {
+ return obj;
+ }
+
+ return "\"" + obj.toString().replaceAll("\"", "\\\"") + "\"";
+}
+
+// Helper object for making a pretty printer.
+class _Writer {
+ String _indent, _content;
+ bool _shouldIndent;
+
+ _Writer() {
+ _indent = "";
+ _content = "";
+ _shouldIndent = true;
+ }
+
+ static final INDENT = " ";
+
+ void indent() {
+ _indent += INDENT;
+ }
+
+ void unindent() {
+ _indent = _indent.substring(INDENT.length);
+ }
+
+ void writeLine([String line = '']) {
+ write(line + "\n");
+ _shouldIndent = true;
+ }
+
+ void write(String str) {
+ if (_shouldIndent) {
+ _shouldIndent = false;
+ _content += _indent;
+ }
+ _content += str;
+ }
+
+ String toString() => _content;
+}
diff --git a/pub/graphlib/pubspec.yaml b/pub/graphlib/pubspec.yaml
new file mode 100644
index 0000000..0a66ff1
--- /dev/null
+++ b/pub/graphlib/pubspec.yaml
@@ -0,0 +1,10 @@
+name: graphlib
+version: 0.0.3
+author: Richard Lincoln <r.w.lincoln@gmail.com>
+description: A directed and undirected multi-graph library.
+homepage: https://github.com/rwl/graphlib
+dependencies:
+ browser: '>=0.10.0+2 <0.11.0'
+ charted: '>=0.0.9 <0.1.0'
+dev_dependencies:
+ unittest: '>=0.11.4 <0.12.0'
