Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/cola.min.js

Last active March 16, 2016 15:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save emeeks/af010660a43035aa8848 to your computer and use it in GitHub Desktop.
Save emeeks/af010660a43035aa8848 to your computer and use it in GitHub Desktop.
Download ZIP
Simple cola.js example with graph generator
Raw
readme.md

A simple cola.js example using its "y" flowLayout option. The graph is a generated nearly hierarchical (but cyclical) schematic social network of Imperial Roman politics.

Raw
cola.min.js
//Based on js_bintrees:
//
//https://github.com/vadimg/js_bintrees
//
//Copyright (C) 2011 by Vadim Graboys
//
//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.
RBTree = (function (window) {
var global = window;
var require = function(name) {
var fn = require.m[name];
if (fn.mod) {
return fn.mod.exports;
}
var mod = fn.mod = { exports: {} };
fn(mod, mod.exports);
return mod.exports;
};
require.m = {};
require.m['./treebase'] = function(module, exports) {
function TreeBase() {}
// removes all nodes from the tree
TreeBase.prototype.clear = function() {
this._root = null;
this.size = 0;
};
// returns node data if found, null otherwise
TreeBase.prototype.find = function(data) {
var res = this._root;
while(res !== null) {
var c = this._comparator(data, res.data);
if(c === 0) {
return res.data;
}
else {
res = res.get_child(c > 0);
}
}
return null;
};
// returns iterator to node if found, null otherwise
TreeBase.prototype.findIter = function(data) {
var res = this._root;
var iter = this.iterator();
while(res !== null) {
var c = this._comparator(data, res.data);
if(c === 0) {
iter._cursor = res;
return iter;
}
else {
iter._ancestors.push(res);
res = res.get_child(c > 0);
}
}
return null;
};
// Returns an interator to the tree node immediately before (or at) the element
TreeBase.prototype.lowerBound = function(data) {
return this._bound(data, this._comparator);
};
// Returns an interator to the tree node immediately after (or at) the element
TreeBase.prototype.upperBound = function(data) {
var cmp = this._comparator;
function reverse_cmp(a, b) {
return cmp(b, a);
}
return this._bound(data, reverse_cmp);
};
// returns null if tree is empty
TreeBase.prototype.min = function() {
var res = this._root;
if(res === null) {
return null;
}
while(res.left !== null) {
res = res.left;
}
return res.data;
};
// returns null if tree is empty
TreeBase.prototype.max = function() {
var res = this._root;
if(res === null) {
return null;
}
while(res.right !== null) {
res = res.right;
}
return res.data;
};
// returns a null iterator
// call next() or prev() to point to an element
TreeBase.prototype.iterator = function() {
return new Iterator(this);
};
// calls cb on each node's data, in order
TreeBase.prototype.each = function(cb) {
var it=this.iterator(), data;
while((data = it.next()) !== null) {
cb(data);
}
};
// calls cb on each node's data, in reverse order
TreeBase.prototype.reach = function(cb) {
var it=this.iterator(), data;
while((data = it.prev()) !== null) {
cb(data);
}
};
// used for lowerBound and upperBound
TreeBase.prototype._bound = function(data, cmp) {
var cur = this._root;
var iter = this.iterator();
while(cur !== null) {
var c = this._comparator(data, cur.data);
if(c === 0) {
iter._cursor = cur;
return iter;
}
iter._ancestors.push(cur);
cur = cur.get_child(c > 0);
}
for(var i=iter._ancestors.length - 1; i >= 0; --i) {
cur = iter._ancestors[i];
if(cmp(data, cur.data) > 0) {
iter._cursor = cur;
iter._ancestors.length = i;
return iter;
}
}
iter._ancestors.length = 0;
return iter;
};
function Iterator(tree) {
this._tree = tree;
this._ancestors = [];
this._cursor = null;
}
Iterator.prototype.data = function() {
return this._cursor !== null ? this._cursor.data : null;
};
// if null-iterator, returns first node
// otherwise, returns next node
Iterator.prototype.next = function() {
if(this._cursor === null) {
var root = this._tree._root;
if(root !== null) {
this._minNode(root);
}
}
else {
if(this._cursor.right === null) {
// no greater node in subtree, go up to parent
// if coming from a right child, continue up the stack
var save;
do {
save = this._cursor;
if(this._ancestors.length) {
this._cursor = this._ancestors.pop();
}
else {
this._cursor = null;
break;
}
} while(this._cursor.right === save);
}
else {
// get the next node from the subtree
this._ancestors.push(this._cursor);
this._minNode(this._cursor.right);
}
}
return this._cursor !== null ? this._cursor.data : null;
};
// if null-iterator, returns last node
// otherwise, returns previous node
Iterator.prototype.prev = function() {
if(this._cursor === null) {
var root = this._tree._root;
if(root !== null) {
this._maxNode(root);
}
}
else {
if(this._cursor.left === null) {
var save;
do {
save = this._cursor;
if(this._ancestors.length) {
this._cursor = this._ancestors.pop();
}
else {
this._cursor = null;
break;
}
} while(this._cursor.left === save);
}
else {
this._ancestors.push(this._cursor);
this._maxNode(this._cursor.left);
}
}
return this._cursor !== null ? this._cursor.data : null;
};
Iterator.prototype._minNode = function(start) {
while(start.left !== null) {
this._ancestors.push(start);
start = start.left;
}
this._cursor = start;
};
Iterator.prototype._maxNode = function(start) {
while(start.right !== null) {
this._ancestors.push(start);
start = start.right;
}
this._cursor = start;
};
module.exports = TreeBase;
};
require.m['__main__'] = function(module, exports) {
var TreeBase = require('./treebase');
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
this.red = true;
}
Node.prototype.get_child = function(dir) {
return dir ? this.right : this.left;
};
Node.prototype.set_child = function(dir, val) {
if(dir) {
this.right = val;
}
else {
this.left = val;
}
};
function RBTree(comparator) {
this._root = null;
this._comparator = comparator;
this.size = 0;
}
RBTree.prototype = new TreeBase();
// returns true if inserted, false if duplicate
RBTree.prototype.insert = function(data) {
var ret = false;
if(this._root === null) {
// empty tree
this._root = new Node(data);
ret = true;
this.size++;
}
else {
var head = new Node(undefined); // fake tree root
var dir = 0;
var last = 0;
// setup
var gp = null; // grandparent
var ggp = head; // grand-grand-parent
var p = null; // parent
var node = this._root;
ggp.right = this._root;
// search down
while(true) {
if(node === null) {
// insert new node at the bottom
node = new Node(data);
p.set_child(dir, node);
ret = true;
this.size++;
}
else if(is_red(node.left) && is_red(node.right)) {
// color flip
node.red = true;
node.left.red = false;
node.right.red = false;
}
// fix red violation
if(is_red(node) && is_red(p)) {
var dir2 = ggp.right === gp;
if(node === p.get_child(last)) {
ggp.set_child(dir2, single_rotate(gp, !last));
}
else {
ggp.set_child(dir2, double_rotate(gp, !last));
}
}
var cmp = this._comparator(node.data, data);
// stop if found
if(cmp === 0) {
break;
}
last = dir;
dir = cmp < 0;
// update helpers
if(gp !== null) {
ggp = gp;
}
gp = p;
p = node;
node = node.get_child(dir);
}
// update root
this._root = head.right;
}
// make root black
this._root.red = false;
return ret;
};
// returns true if removed, false if not found
RBTree.prototype.remove = function(data) {
if(this._root === null) {
return false;
}
var head = new Node(undefined); // fake tree root
var node = head;
node.right = this._root;
var p = null; // parent
var gp = null; // grand parent
var found = null; // found item
var dir = 1;
while(node.get_child(dir) !== null) {
var last = dir;
// update helpers
gp = p;
p = node;
node = node.get_child(dir);
var cmp = this._comparator(data, node.data);
dir = cmp > 0;
// save found node
if(cmp === 0) {
found = node;
}
// push the red node down
if(!is_red(node) && !is_red(node.get_child(dir))) {
if(is_red(node.get_child(!dir))) {
var sr = single_rotate(node, dir);
p.set_child(last, sr);
p = sr;
}
else if(!is_red(node.get_child(!dir))) {
var sibling = p.get_child(!last);
if(sibling !== null) {
if(!is_red(sibling.get_child(!last)) && !is_red(sibling.get_child(last))) {
// color flip
p.red = false;
sibling.red = true;
node.red = true;
}
else {
var dir2 = gp.right === p;
if(is_red(sibling.get_child(last))) {
gp.set_child(dir2, double_rotate(p, last));
}
else if(is_red(sibling.get_child(!last))) {
gp.set_child(dir2, single_rotate(p, last));
}
// ensure correct coloring
var gpc = gp.get_child(dir2);
gpc.red = true;
node.red = true;
gpc.left.red = false;
gpc.right.red = false;
}
}
}
}
}
// replace and remove if found
if(found !== null) {
found.data = node.data;
p.set_child(p.right === node, node.get_child(node.left === null));
this.size--;
}
// update root and make it black
this._root = head.right;
if(this._root !== null) {
this._root.red = false;
}
return found !== null;
};
function is_red(node) {
return node !== null && node.red;
}
function single_rotate(root, dir) {
var save = root.get_child(!dir);
root.set_child(!dir, save.get_child(dir));
save.set_child(dir, root);
root.red = true;
save.red = false;
return save;
}
function double_rotate(root, dir) {
root.set_child(!dir, single_rotate(root.get_child(!dir), !dir));
return single_rotate(root, dir);
}
module.exports = RBTree;
};
return require('__main__');
})(typeof module === 'undefined' ? window : module.exports);
var cola;
(function (cola) {
var packingOptions = {
PADDING: 10,
GOLDEN_SECTION: (1 + Math.sqrt(5)) / 2,
FLOAT_EPSILON: 0.0001,
MAX_INERATIONS: 100
};
// assign x, y to nodes while using box packing algorithm for disconnected graphs
function applyPacking(graphs, w, h, node_size, desired_ratio) {
if (desired_ratio === void 0) { desired_ratio = 1; }
var init_x = 0, init_y = 0, svg_width = w, svg_height = h, desired_ratio = typeof desired_ratio !== 'undefined' ? desired_ratio : 1, node_size = typeof node_size !== 'undefined' ? node_size : 0, real_width = 0, real_height = 0, min_width = 0, global_bottom = 0, line = [];
if (graphs.length == 0)
return;
/// that would take care of single nodes problem
// graphs.forEach(function (g) {
// if (g.array.length == 1) {
// g.array[0].x = 0;
// g.array[0].y = 0;
// }
// });
calculate_bb(graphs);
apply(graphs, desired_ratio);
put_nodes_to_right_positions(graphs);
// get bounding boxes for all separate graphs
function calculate_bb(graphs) {
graphs.forEach(function (g) {
calculate_single_bb(g);
});
function calculate_single_bb(graph) {
var min_x = Number.MAX_VALUE, min_y = Number.MAX_VALUE, max_x = 0, max_y = 0;
graph.array.forEach(function (v) {
var w = typeof v.width !== 'undefined' ? v.width : node_size;
var h = typeof v.height !== 'undefined' ? v.height : node_size;
w /= 2;
h /= 2;
max_x = Math.max(v.x + w, max_x);
min_x = Math.min(v.x - w, min_x);
max_y = Math.max(v.y + h, max_y);
min_y = Math.min(v.y - h, min_y);
});
graph.width = max_x - min_x;
graph.height = max_y - min_y;
}
}
//function plot(data, left, right, opt_x, opt_y) {
// // plot the cost function
// var plot_svg = d3.select("body").append("svg")
// .attr("width", function () { return 2 * (right - left); })
// .attr("height", 200);
// var x = d3.time.scale().range([0, 2 * (right - left)]);
// var xAxis = d3.svg.axis().scale(x).orient("bottom");
// plot_svg.append("g").attr("class", "x axis")
// .attr("transform", "translate(0, 199)")
// .call(xAxis);
// var lastX = 0;
// var lastY = 0;
// var value = 0;
// for (var r = left; r < right; r += 1) {
// value = step(data, r);
// // value = 1;
// plot_svg.append("line").attr("x1", 2 * (lastX - left))
// .attr("y1", 200 - 30 * lastY)
// .attr("x2", 2 * r - 2 * left)
// .attr("y2", 200 - 30 * value)
// .style("stroke", "rgb(6,120,155)");
// lastX = r;
// lastY = value;
// }
// plot_svg.append("circle").attr("cx", 2 * opt_x - 2 * left).attr("cy", 200 - 30 * opt_y)
// .attr("r", 5).style('fill', "rgba(0,0,0,0.5)");
//}
// actual assigning of position to nodes
function put_nodes_to_right_positions(graphs) {
graphs.forEach(function (g) {
// calculate current graph center:
var center = { x: 0, y: 0 };
g.array.forEach(function (node) {
center.x += node.x;
center.y += node.y;
});
center.x /= g.array.length;
center.y /= g.array.length;
// calculate current top left corner:
var corner = { x: center.x - g.width / 2, y: center.y - g.height / 2 };
var offset = { x: g.x - corner.x, y: g.y - corner.y };
// put nodes:
g.array.forEach(function (node) {
node.x = node.x + offset.x + svg_width / 2 - real_width / 2;
node.y = node.y + offset.y + svg_height / 2 - real_height / 2;
});
});
}
// starts box packing algorithm
// desired ratio is 1 by default
function apply(data, desired_ratio) {
var curr_best_f = Number.POSITIVE_INFINITY;
var curr_best = 0;
data.sort(function (a, b) { return b.height - a.height; });
min_width = data.reduce(function (a, b) {
return a.width < b.width ? a.width : b.width;
});
var left = x1 = min_width;
var right = x2 = get_entire_width(data);
var iterationCounter = 0;
var f_x1 = Number.MAX_VALUE;
var f_x2 = Number.MAX_VALUE;
var flag = -1; // determines which among f_x1 and f_x2 to recompute
var dx = Number.MAX_VALUE;
var df = Number.MAX_VALUE;
while ((dx > min_width) || df > packingOptions.FLOAT_EPSILON) {
if (flag != 1) {
var x1 = right - (right - left) / packingOptions.GOLDEN_SECTION;
var f_x1 = step(data, x1);
}
if (flag != 0) {
var x2 = left + (right - left) / packingOptions.GOLDEN_SECTION;
var f_x2 = step(data, x2);
}
dx = Math.abs(x1 - x2);
df = Math.abs(f_x1 - f_x2);
if (f_x1 < curr_best_f) {
curr_best_f = f_x1;
curr_best = x1;
}
if (f_x2 < curr_best_f) {
curr_best_f = f_x2;
curr_best = x2;
}
if (f_x1 > f_x2) {
left = x1;
x1 = x2;
f_x1 = f_x2;
flag = 1;
}
else {
right = x2;
x2 = x1;
f_x2 = f_x1;
flag = 0;
}
if (iterationCounter++ > 100) {
break;
}
}
// plot(data, min_width, get_entire_width(data), curr_best, curr_best_f);
step(data, curr_best);
}
// one iteration of the optimization method
// (gives a proper, but not necessarily optimal packing)
function step(data, max_width) {
line = [];
real_width = 0;
real_height = 0;
global_bottom = init_y;
for (var i = 0; i < data.length; i++) {
var o = data[i];
put_rect(o, max_width);
}
return Math.abs(get_real_ratio() - desired_ratio);
}
// looking for a position to one box
function put_rect(rect, max_width) {
var parent = undefined;
for (var i = 0; i < line.length; i++) {
if ((line[i].space_left >= rect.height) && (line[i].x + line[i].width + rect.width + packingOptions.PADDING - max_width) <= packingOptions.FLOAT_EPSILON) {
parent = line[i];
break;
}
}
line.push(rect);
if (parent !== undefined) {
rect.x = parent.x + parent.width + packingOptions.PADDING;
rect.y = parent.bottom;
rect.space_left = rect.height;
rect.bottom = rect.y;
parent.space_left -= rect.height + packingOptions.PADDING;
parent.bottom += rect.height + packingOptions.PADDING;
}
else {
rect.y = global_bottom;
global_bottom += rect.height + packingOptions.PADDING;
rect.x = init_x;
rect.bottom = rect.y;
rect.space_left = rect.height;
}
if (rect.y + rect.height - real_height > -packingOptions.FLOAT_EPSILON)
real_height = rect.y + rect.height - init_y;
if (rect.x + rect.width - real_width > -packingOptions.FLOAT_EPSILON)
real_width = rect.x + rect.width - init_x;
}
;
function get_entire_width(data) {
var width = 0;
data.forEach(function (d) { return width += d.width + packingOptions.PADDING; });
return width;
}
function get_real_ratio() {
return (real_width / real_height);
}
}
cola.applyPacking = applyPacking;
// seraration of disconnected graphs
// returns an array of {}
function separateGraphs(nodes, links) {
var marks = {};
var ways = {};
var graphs = [];
var clusters = 0;
for (var i = 0; i < links.length; i++) {
var link = links[i];
var n1 = link.source;
var n2 = link.target;
if (ways[n1.index])
ways[n1.index].push(n2);
else
ways[n1.index] = [n2];
if (ways[n2.index])
ways[n2.index].push(n1);
else
ways[n2.index] = [n1];
}
for (var i = 0; i < nodes.length; i++) {
var node = nodes[i];
if (marks[node.index])
continue;
explore_node(node, true);
}
function explore_node(n, is_new) {
if (marks[n.index] !== undefined)
return;
if (is_new) {
clusters++;
graphs.push({ array: [] });
}
marks[n.index] = clusters;
graphs[clusters - 1].array.push(n);
var adjacent = ways[n.index];
if (!adjacent)
return;
for (var j = 0; j < adjacent.length; j++) {
explore_node(adjacent[j], false);
}
}
return graphs;
}
cola.separateGraphs = separateGraphs;
})(cola || (cola = {}));
var cola;
(function (cola) {
var vpsc;
(function (vpsc) {
var PositionStats = (function () {
function PositionStats(scale) {
this.scale = scale;
this.AB = 0;
this.AD = 0;
this.A2 = 0;
}
PositionStats.prototype.addVariable = function (v) {
var ai = this.scale / v.scale;
var bi = v.offset / v.scale;
var wi = v.weight;
this.AB += wi * ai * bi;
this.AD += wi * ai * v.desiredPosition;
this.A2 += wi * ai * ai;
};
PositionStats.prototype.getPosn = function () {
return (this.AD - this.AB) / this.A2;
};
return PositionStats;
})();
vpsc.PositionStats = PositionStats;
var Constraint = (function () {
function Constraint(left, right, gap, equality) {
if (equality === void 0) { equality = false; }
this.left = left;
this.right = right;
this.gap = gap;
this.equality = equality;
this.active = false;
this.unsatisfiable = false;
this.left = left;
this.right = right;
this.gap = gap;
this.equality = equality;
}
Constraint.prototype.slack = function () {
return this.unsatisfiable ? Number.MAX_VALUE
: this.right.scale * this.right.position() - this.gap
- this.left.scale * this.left.position();
};
return Constraint;
})();
vpsc.Constraint = Constraint;
var Variable = (function () {
function Variable(desiredPosition, weight, scale) {
if (weight === void 0) { weight = 1; }
if (scale === void 0) { scale = 1; }
this.desiredPosition = desiredPosition;
this.weight = weight;
this.scale = scale;
this.offset = 0;
}
Variable.prototype.dfdv = function () {
return 2.0 * this.weight * (this.position() - this.desiredPosition);
};
Variable.prototype.position = function () {
return (this.block.ps.scale * this.block.posn + this.offset) / this.scale;
};
// visit neighbours by active constraints within the same block
Variable.prototype.visitNeighbours = function (prev, f) {
var ff = function (c, next) { return c.active && prev !== next && f(c, next); };
this.cOut.forEach(function (c) { return ff(c, c.right); });
this.cIn.forEach(function (c) { return ff(c, c.left); });
};
return Variable;
})();
vpsc.Variable = Variable;
var Block = (function () {
function Block(v) {
this.vars = [];
v.offset = 0;
this.ps = new PositionStats(v.scale);
this.addVariable(v);
}
Block.prototype.addVariable = function (v) {
v.block = this;
this.vars.push(v);
this.ps.addVariable(v);
this.posn = this.ps.getPosn();
};
// move the block where it needs to be to minimize cost
Block.prototype.updateWeightedPosition = function () {
this.ps.AB = this.ps.AD = this.ps.A2 = 0;
for (var i = 0, n = this.vars.length; i < n; ++i)
this.ps.addVariable(this.vars[i]);
this.posn = this.ps.getPosn();
};
Block.prototype.compute_lm = function (v, u, postAction) {
var _this = this;
var dfdv = v.dfdv();
v.visitNeighbours(u, function (c, next) {
var _dfdv = _this.compute_lm(next, v, postAction);
if (next === c.right) {
dfdv += _dfdv * c.left.scale;
c.lm = _dfdv;
}
else {
dfdv += _dfdv * c.right.scale;
c.lm = -_dfdv;
}
postAction(c);
});
return dfdv / v.scale;
};
Block.prototype.populateSplitBlock = function (v, prev) {
var _this = this;
v.visitNeighbours(prev, function (c, next) {
next.offset = v.offset + (next === c.right ? c.gap : -c.gap);
_this.addVariable(next);
_this.populateSplitBlock(next, v);
});
};
// traverse the active constraint tree applying visit to each active constraint
Block.prototype.traverse = function (visit, acc, v, prev) {
var _this = this;
if (v === void 0) { v = this.vars[0]; }
if (prev === void 0) { prev = null; }
v.visitNeighbours(prev, function (c, next) {
acc.push(visit(c));
_this.traverse(visit, acc, next, v);
});
};
// calculate lagrangian multipliers on constraints and
// find the active constraint in this block with the smallest lagrangian.
// if the lagrangian is negative, then the constraint is a split candidate.
Block.prototype.findMinLM = function () {
var m = null;
this.compute_lm(this.vars[0], null, function (c) {
if (!c.equality && (m === null || c.lm < m.lm))
m = c;
});
return m;
};
Block.prototype.findMinLMBetween = function (lv, rv) {
this.compute_lm(lv, null, function () { });
var m = null;
this.findPath(lv, null, rv, function (c, next) {
if (!c.equality && c.right === next && (m === null || c.lm < m.lm))
m = c;
});
return m;
};
Block.prototype.findPath = function (v, prev, to, visit) {
var _this = this;
var endFound = false;
v.visitNeighbours(prev, function (c, next) {
if (!endFound && (next === to || _this.findPath(next, v, to, visit))) {
endFound = true;
visit(c, next);
}
});
return endFound;
};
// Search active constraint tree from u to see if there is a directed path to v.
// Returns true if path is found.
Block.prototype.isActiveDirectedPathBetween = function (u, v) {
if (u === v)
return true;
var i = u.cOut.length;
while (i--) {
var c = u.cOut[i];
if (c.active && this.isActiveDirectedPathBetween(c.right, v))
return true;
}
return false;
};
// split the block into two by deactivating the specified constraint
Block.split = function (c) {
/* DEBUG
console.log("split on " + c);
console.assert(c.active, "attempt to split on inactive constraint");
DEBUG */
c.active = false;
return [Block.createSplitBlock(c.left), Block.createSplitBlock(c.right)];
};
Block.createSplitBlock = function (startVar) {
var b = new Block(startVar);
b.populateSplitBlock(startVar, null);
return b;
};
// find a split point somewhere between the specified variables
Block.prototype.splitBetween = function (vl, vr) {
/* DEBUG
console.assert(vl.block === this);
console.assert(vr.block === this);
DEBUG */
var c = this.findMinLMBetween(vl, vr);
if (c !== null) {
var bs = Block.split(c);
return { constraint: c, lb: bs[0], rb: bs[1] };
}
// couldn't find a split point - for example the active path is all equality constraints
return null;
};
Block.prototype.mergeAcross = function (b, c, dist) {
c.active = true;
for (var i = 0, n = b.vars.length; i < n; ++i) {
var v = b.vars[i];
v.offset += dist;
this.addVariable(v);
}
this.posn = this.ps.getPosn();
};
Block.prototype.cost = function () {
var sum = 0, i = this.vars.length;
while (i--) {
var v = this.vars[i], d = v.position() - v.desiredPosition;
sum += d * d * v.weight;
}
return sum;
};
return Block;
})();
vpsc.Block = Block;
var Blocks = (function () {
function Blocks(vs) {
this.vs = vs;
var n = vs.length;
this.list = new Array(n);
while (n--) {
var b = new Block(vs[n]);
this.list[n] = b;
b.blockInd = n;
}
}
Blocks.prototype.cost = function () {
var sum = 0, i = this.list.length;
while (i--)
sum += this.list[i].cost();
return sum;
};
Blocks.prototype.insert = function (b) {
/* DEBUG
console.assert(!this.contains(b), "blocks error: tried to reinsert block " + b.blockInd)
DEBUG */
b.blockInd = this.list.length;
this.list.push(b);
/* DEBUG
console.log("insert block: " + b.blockInd);
this.contains(b);
DEBUG */
};
Blocks.prototype.remove = function (b) {
/* DEBUG
console.log("remove block: " + b.blockInd);
console.assert(this.contains(b));
DEBUG */
var last = this.list.length - 1;
var swapBlock = this.list[last];
this.list.length = last;
if (b !== swapBlock) {
this.list[b.blockInd] = swapBlock;
swapBlock.blockInd = b.blockInd;
}
};
// merge the blocks on either side of the specified constraint, by copying the smaller block into the larger
// and deleting the smaller.
Blocks.prototype.merge = function (c) {
var l = c.left.block, r = c.right.block;
/* DEBUG
console.assert(l!==r, "attempt to merge within the same block");
DEBUG */
var dist = c.right.offset - c.left.offset - c.gap;
if (l.vars.length < r.vars.length) {
r.mergeAcross(l, c, dist);
this.remove(l);
}
else {
l.mergeAcross(r, c, -dist);
this.remove(r);
}
/* DEBUG
console.assert(Math.abs(c.slack()) < 1e-6, "Error: Constraint should be at equality after merge!");
console.log("merged on " + c);
DEBUG */
};
Blocks.prototype.forEach = function (f) {
this.list.forEach(f);
};
// useful, for example, after variable desired positions change.
Blocks.prototype.updateBlockPositions = function () {
this.list.forEach(function (b) { return b.updateWeightedPosition(); });
};
// split each block across its constraint with the minimum lagrangian
Blocks.prototype.split = function (inactive) {
var _this = this;
this.updateBlockPositions();
this.list.forEach(function (b) {
var v = b.findMinLM();
if (v !== null && v.lm < Solver.LAGRANGIAN_TOLERANCE) {
b = v.left.block;
Block.split(v).forEach(function (nb) { return _this.insert(nb); });
_this.remove(b);
inactive.push(v);
}
});
};
return Blocks;
})();
vpsc.Blocks = Blocks;
var Solver = (function () {
function Solver(vs, cs) {
this.vs = vs;
this.cs = cs;
this.vs = vs;
vs.forEach(function (v) {
v.cIn = [], v.cOut = [];
/* DEBUG
v.toString = () => "v" + vs.indexOf(v);
DEBUG */
});
this.cs = cs;
cs.forEach(function (c) {
c.left.cOut.push(c);
c.right.cIn.push(c);
/* DEBUG
c.toString = () => c.left + "+" + c.gap + "<=" + c.right + " slack=" + c.slack() + " active=" + c.active;
DEBUG */
});
this.inactive = cs.map(function (c) { c.active = false; return c; });
this.bs = null;
}
Solver.prototype.cost = function () {
return this.bs.cost();
};
// set starting positions without changing desired positions.
// Note: it throws away any previous block structure.
Solver.prototype.setStartingPositions = function (ps) {
this.inactive = this.cs.map(function (c) { c.active = false; return c; });
this.bs = new Blocks(this.vs);
this.bs.forEach(function (b, i) { return b.posn = ps[i]; });
};
Solver.prototype.setDesiredPositions = function (ps) {
this.vs.forEach(function (v, i) { return v.desiredPosition = ps[i]; });
};
/* DEBUG
private getId(v: Variable): number {
return this.vs.indexOf(v);
}
// sanity check of the index integrity of the inactive list
checkInactive(): void {
var inactiveCount = 0;
this.cs.forEach(c=> {
var i = this.inactive.indexOf(c);
console.assert(!c.active && i >= 0 || c.active && i < 0, "constraint should be in the inactive list if it is not active: " + c);
if (i >= 0) {
inactiveCount++;
} else {
console.assert(c.active, "inactive constraint not found in inactive list: " + c);
}
});
console.assert(inactiveCount === this.inactive.length, inactiveCount + " inactive constraints found, " + this.inactive.length + "in inactive list");
}
// after every call to satisfy the following should check should pass
checkSatisfied(): void {
this.cs.forEach(c=>console.assert(c.slack() >= vpsc.Solver.ZERO_UPPERBOUND, "Error: Unsatisfied constraint! "+c));
}
DEBUG */
Solver.prototype.mostViolated = function () {
var minSlack = Number.MAX_VALUE, v = null, l = this.inactive, n = l.length, deletePoint = n;
for (var i = 0; i < n; ++i) {
var c = l[i];
if (c.unsatisfiable)
continue;
var slack = c.slack();
if (c.equality || slack < minSlack) {
minSlack = slack;
v = c;
deletePoint = i;
if (c.equality)
break;
}
}
if (deletePoint !== n &&
(minSlack < Solver.ZERO_UPPERBOUND && !v.active || v.equality)) {
l[deletePoint] = l[n - 1];
l.length = n - 1;
}
return v;
};
// satisfy constraints by building block structure over violated constraints
// and moving the blocks to their desired positions
Solver.prototype.satisfy = function () {
if (this.bs == null) {
this.bs = new Blocks(this.vs);
}
/* DEBUG
console.log("satisfy: " + this.bs);
DEBUG */
this.bs.split(this.inactive);
var v = null;
while ((v = this.mostViolated()) && (v.equality || v.slack() < Solver.ZERO_UPPERBOUND && !v.active)) {
var lb = v.left.block, rb = v.right.block;
/* DEBUG
console.log("most violated is: " + v);
this.bs.contains(lb);
this.bs.contains(rb);
DEBUG */
if (lb !== rb) {
this.bs.merge(v);
}
else {
if (lb.isActiveDirectedPathBetween(v.right, v.left)) {
// cycle found!
v.unsatisfiable = true;
continue;
}
// constraint is within block, need to split first
var split = lb.splitBetween(v.left, v.right);
if (split !== null) {
this.bs.insert(split.lb);
this.bs.insert(split.rb);
this.bs.remove(lb);
this.inactive.push(split.constraint);
}
else {
/* DEBUG
console.log("unsatisfiable constraint found");
DEBUG */
v.unsatisfiable = true;
continue;
}
if (v.slack() >= 0) {
/* DEBUG
console.log("violated constraint indirectly satisfied: " + v);
DEBUG */
// v was satisfied by the above split!
this.inactive.push(v);
}
else {
/* DEBUG
console.log("merge after split:");
DEBUG */
this.bs.merge(v);
}
}
}
/* DEBUG
this.checkSatisfied();
DEBUG */
};
// repeatedly build and split block structure until we converge to an optimal solution
Solver.prototype.solve = function () {
this.satisfy();
var lastcost = Number.MAX_VALUE, cost = this.bs.cost();
while (Math.abs(lastcost - cost) > 0.0001) {
this.satisfy();
lastcost = cost;
cost = this.bs.cost();
}
return cost;
};
Solver.LAGRANGIAN_TOLERANCE = -1e-4;
Solver.ZERO_UPPERBOUND = -1e-10;
return Solver;
})();
vpsc.Solver = Solver;
})(vpsc = cola.vpsc || (cola.vpsc = {}));
})(cola || (cola = {}));
var __extends = this.__extends || function (d, b) {
for (var p in b) if (b.hasOwnProperty(p)) d[p] = b[p];
function __() { this.constructor = d; }
__.prototype = b.prototype;
d.prototype = new __();
};
///<reference path="vpsc.ts"/>
///<reference path="rbtree.d.ts"/>
var cola;
(function (cola) {
var vpsc;
(function (vpsc) {
function computeGroupBounds(g) {
g.bounds = typeof g.leaves !== "undefined" ?
g.leaves.reduce(function (r, c) { return c.bounds.union(r); }, Rectangle.empty()) :
Rectangle.empty();
if (typeof g.groups !== "undefined")
g.bounds = g.groups.reduce(function (r, c) { return computeGroupBounds(c).union(r); }, g.bounds);
g.bounds = g.bounds.inflate(g.padding);
return g.bounds;
}
vpsc.computeGroupBounds = computeGroupBounds;
var Rectangle = (function () {
function Rectangle(x, X, y, Y) {
this.x = x;
this.X = X;
this.y = y;
this.Y = Y;
}
Rectangle.empty = function () { return new Rectangle(Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY); };
Rectangle.prototype.cx = function () { return (this.x + this.X) / 2; };
Rectangle.prototype.cy = function () { return (this.y + this.Y) / 2; };
Rectangle.prototype.overlapX = function (r) {
var ux = this.cx(), vx = r.cx();
if (ux <= vx && r.x < this.X)
return this.X - r.x;
if (vx <= ux && this.x < r.X)
return r.X - this.x;
return 0;
};
Rectangle.prototype.overlapY = function (r) {
var uy = this.cy(), vy = r.cy();
if (uy <= vy && r.y < this.Y)
return this.Y - r.y;
if (vy <= uy && this.y < r.Y)
return r.Y - this.y;
return 0;
};
Rectangle.prototype.setXCentre = function (cx) {
var dx = cx - this.cx();
this.x += dx;
this.X += dx;
};
Rectangle.prototype.setYCentre = function (cy) {
var dy = cy - this.cy();
this.y += dy;
this.Y += dy;
};
Rectangle.prototype.width = function () {
return this.X - this.x;
};
Rectangle.prototype.height = function () {
return this.Y - this.y;
};
Rectangle.prototype.union = function (r) {
return new Rectangle(Math.min(this.x, r.x), Math.max(this.X, r.X), Math.min(this.y, r.y), Math.max(this.Y, r.Y));
};
/**
* return any intersection points between the given line and the sides of this rectangle
* @method lineIntersection
* @param x1 number first x coord of line
* @param y1 number first y coord of line
* @param x2 number second x coord of line
* @param y2 number second y coord of line
* @return any intersection points found
*/
Rectangle.prototype.lineIntersections = function (x1, y1, x2, y2) {
var sides = [[this.x, this.y, this.X, this.y],
[this.X, this.y, this.X, this.Y],
[this.X, this.Y, this.x, this.Y],
[this.x, this.Y, this.x, this.y]];
var intersections = [];
for (var i = 0; i < 4; ++i) {
var r = Rectangle.lineIntersection(x1, y1, x2, y2, sides[i][0], sides[i][1], sides[i][2], sides[i][3]);
if (r !== null)
intersections.push({ x: r.x, y: r.y });
}
return intersections;
};
/**
* return any intersection points between a line extending from the centre of this rectangle to the given point,
* and the sides of this rectangle
* @method lineIntersection
* @param x2 number second x coord of line
* @param y2 number second y coord of line
* @return any intersection points found
*/
Rectangle.prototype.rayIntersection = function (x2, y2) {
var ints = this.lineIntersections(this.cx(), this.cy(), x2, y2);
return ints.length > 0 ? ints[0] : null;
};
Rectangle.prototype.vertices = function () {
return [
{ x: this.x, y: this.y },
{ x: this.X, y: this.y },
{ x: this.X, y: this.Y },
{ x: this.x, y: this.Y },
{ x: this.x, y: this.y }];
};
Rectangle.lineIntersection = function (x1, y1, x2, y2, x3, y3, x4, y4) {
var dx12 = x2 - x1, dx34 = x4 - x3, dy12 = y2 - y1, dy34 = y4 - y3, denominator = dy34 * dx12 - dx34 * dy12;
if (denominator == 0)
return null;
var dx31 = x1 - x3, dy31 = y1 - y3, numa = dx34 * dy31 - dy34 * dx31, a = numa / denominator, numb = dx12 * dy31 - dy12 * dx31, b = numb / denominator;
if (a >= 0 && a <= 1 && b >= 0 && b <= 1) {
return {
x: x1 + a * dx12,
y: y1 + a * dy12
};
}
return null;
};
Rectangle.prototype.inflate = function (pad) {
return new Rectangle(this.x - pad, this.X + pad, this.y - pad, this.Y + pad);
};
return Rectangle;
})();
vpsc.Rectangle = Rectangle;
function makeEdgeBetween(link, source, target, ah) {
var si = source.rayIntersection(target.cx(), target.cy());
if (!si)
si = { x: source.cx(), y: source.cy() };
var ti = target.rayIntersection(source.cx(), source.cy());
if (!ti)
ti = { x: target.cx(), y: target.cy() };
var dx = ti.x - si.x, dy = ti.y - si.y, l = Math.sqrt(dx * dx + dy * dy), al = l - ah;
link.sourceIntersection = si;
link.targetIntersection = ti;
link.arrowStart = { x: si.x + al * dx / l, y: si.y + al * dy / l };
}
vpsc.makeEdgeBetween = makeEdgeBetween;
function makeEdgeTo(s, target, ah) {
var ti = target.rayIntersection(s.x, s.y);
if (!ti)
ti = { x: target.cx(), y: target.cy() };
var dx = ti.x - s.x, dy = ti.y - s.y, l = Math.sqrt(dx * dx + dy * dy);
return { x: ti.x - ah * dx / l, y: ti.y - ah * dy / l };
}
vpsc.makeEdgeTo = makeEdgeTo;
var Node = (function () {
function Node(v, r, pos) {
this.v = v;
this.r = r;
this.pos = pos;
this.prev = makeRBTree();
this.next = makeRBTree();
}
return Node;
})();
var Event = (function () {
function Event(isOpen, v, pos) {
this.isOpen = isOpen;
this.v = v;
this.pos = pos;
}
return Event;
})();
function compareEvents(a, b) {
if (a.pos > b.pos) {
return 1;
}
if (a.pos < b.pos) {
return -1;
}
if (a.isOpen) {
// open must come before close
return -1;
}
return 0;
}
function makeRBTree() {
return new RBTree(function (a, b) { return a.pos - b.pos; });
}
var xRect = {
getCentre: function (r) { return r.cx(); },
getOpen: function (r) { return r.y; },
getClose: function (r) { return r.Y; },
getSize: function (r) { return r.width(); },
makeRect: function (open, close, center, size) { return new Rectangle(center - size / 2, center + size / 2, open, close); },
findNeighbours: findXNeighbours
};
var yRect = {
getCentre: function (r) { return r.cy(); },
getOpen: function (r) { return r.x; },
getClose: function (r) { return r.X; },
getSize: function (r) { return r.height(); },
makeRect: function (open, close, center, size) { return new Rectangle(open, close, center - size / 2, center + size / 2); },
findNeighbours: findYNeighbours
};
function generateGroupConstraints(root, f, minSep, isContained) {
if (isContained === void 0) { isContained = false; }
var padding = root.padding, gn = typeof root.groups !== 'undefined' ? root.groups.length : 0, ln = typeof root.leaves !== 'undefined' ? root.leaves.length : 0, childConstraints = !gn ? []
: root.groups.reduce(function (ccs, g) { return ccs.concat(generateGroupConstraints(g, f, minSep, true)); }, []), n = (isContained ? 2 : 0) + ln + gn, vs = new Array(n), rs = new Array(n), i = 0, add = function (r, v) { rs[i] = r; vs[i++] = v; };
if (isContained) {
// if this group is contained by another, then we add two dummy vars and rectangles for the borders
var b = root.bounds, c = f.getCentre(b), s = f.getSize(b) / 2, open = f.getOpen(b), close = f.getClose(b), min = c - s + padding / 2, max = c + s - padding / 2;
root.minVar.desiredPosition = min;
add(f.makeRect(open, close, min, padding), root.minVar);
root.maxVar.desiredPosition = max;
add(f.makeRect(open, close, max, padding), root.maxVar);
}
if (ln)
root.leaves.forEach(function (l) { return add(l.bounds, l.variable); });
if (gn)
root.groups.forEach(function (g) {
var b = g.bounds;
add(f.makeRect(f.getOpen(b), f.getClose(b), f.getCentre(b), f.getSize(b)), g.minVar);
});
var cs = generateConstraints(rs, vs, f, minSep);
if (gn) {
vs.forEach(function (v) { v.cOut = [], v.cIn = []; });
cs.forEach(function (c) { c.left.cOut.push(c), c.right.cIn.push(c); });
root.groups.forEach(function (g) {
var gapAdjustment = (g.padding - f.getSize(g.bounds)) / 2;
g.minVar.cIn.forEach(function (c) { return c.gap += gapAdjustment; });
g.minVar.cOut.forEach(function (c) { c.left = g.maxVar; c.gap += gapAdjustment; });
});
}
return childConstraints.concat(cs);
}
function generateConstraints(rs, vars, rect, minSep) {
var i, n = rs.length;
var N = 2 * n;
console.assert(vars.length >= n);
var events = new Array(N);
for (i = 0; i < n; ++i) {
var r = rs[i];
var v = new Node(vars[i], r, rect.getCentre(r));
events[i] = new Event(true, v, rect.getOpen(r));
events[i + n] = new Event(false, v, rect.getClose(r));
}
events.sort(compareEvents);
var cs = new Array();
var scanline = makeRBTree();
for (i = 0; i < N; ++i) {
var e = events[i];
var v = e.v;
if (e.isOpen) {
scanline.insert(v);
rect.findNeighbours(v, scanline);
}
else {
// close event
scanline.remove(v);
var makeConstraint = function (l, r) {
var sep = (rect.getSize(l.r) + rect.getSize(r.r)) / 2 + minSep;
cs.push(new vpsc.Constraint(l.v, r.v, sep));
};
var visitNeighbours = function (forward, reverse, mkcon) {
var u, it = v[forward].iterator();
while ((u = it[forward]()) !== null) {
mkcon(u, v);
u[reverse].remove(v);
}
};
visitNeighbours("prev", "next", function (u, v) { return makeConstraint(u, v); });
visitNeighbours("next", "prev", function (u, v) { return makeConstraint(v, u); });
}
}
console.assert(scanline.size === 0);
return cs;
}
function findXNeighbours(v, scanline) {
var f = function (forward, reverse) {
var it = scanline.findIter(v);
var u;
while ((u = it[forward]()) !== null) {
var uovervX = u.r.overlapX(v.r);
if (uovervX <= 0 || uovervX <= u.r.overlapY(v.r)) {
v[forward].insert(u);
u[reverse].insert(v);
}
if (uovervX <= 0) {
break;
}
}
};
f("next", "prev");
f("prev", "next");
}
function findYNeighbours(v, scanline) {
var f = function (forward, reverse) {
var u = scanline.findIter(v)[forward]();
if (u !== null && u.r.overlapX(v.r) > 0) {
v[forward].insert(u);
u[reverse].insert(v);
}
};
f("next", "prev");
f("prev", "next");
}
function generateXConstraints(rs, vars) {
return generateConstraints(rs, vars, xRect, 1e-6);
}
vpsc.generateXConstraints = generateXConstraints;
function generateYConstraints(rs, vars) {
return generateConstraints(rs, vars, yRect, 1e-6);
}
vpsc.generateYConstraints = generateYConstraints;
function generateXGroupConstraints(root) {
return generateGroupConstraints(root, xRect, 1e-6);
}
vpsc.generateXGroupConstraints = generateXGroupConstraints;
function generateYGroupConstraints(root) {
return generateGroupConstraints(root, yRect, 1e-6);
}
vpsc.generateYGroupConstraints = generateYGroupConstraints;
function removeOverlaps(rs) {
var vs = rs.map(function (r) { return new vpsc.Variable(r.cx()); });
var cs = vpsc.generateXConstraints(rs, vs);
var solver = new vpsc.Solver(vs, cs);
solver.solve();
vs.forEach(function (v, i) { return rs[i].setXCentre(v.position()); });
vs = rs.map(function (r) {
return new vpsc.Variable(r.cy());
});
cs = vpsc.generateYConstraints(rs, vs);
solver = new vpsc.Solver(vs, cs);
solver.solve();
vs.forEach(function (v, i) { return rs[i].setYCentre(v.position()); });
}
vpsc.removeOverlaps = removeOverlaps;
var IndexedVariable = (function (_super) {
__extends(IndexedVariable, _super);
function IndexedVariable(index, w) {
_super.call(this, 0, w);
this.index = index;
}
return IndexedVariable;
})(vpsc.Variable);
vpsc.IndexedVariable = IndexedVariable;
var Projection = (function () {
function Projection(nodes, groups, rootGroup, constraints, avoidOverlaps) {
var _this = this;
if (rootGroup === void 0) { rootGroup = null; }
if (constraints === void 0) { constraints = null; }
if (avoidOverlaps === void 0) { avoidOverlaps = false; }
this.nodes = nodes;
this.groups = groups;
this.rootGroup = rootGroup;
this.avoidOverlaps = avoidOverlaps;
this.variables = nodes.map(function (v, i) {
return v.variable = new IndexedVariable(i, 1);
});
if (constraints)
this.createConstraints(constraints);
if (avoidOverlaps && rootGroup && typeof rootGroup.groups !== 'undefined') {
nodes.forEach(function (v) {
if (!v.width || !v.height) {
//If undefined, default to nothing
v.bounds = new vpsc.Rectangle(v.x, v.x, v.y, v.y);
return;
}
var w2 = v.width / 2, h2 = v.height / 2;
v.bounds = new vpsc.Rectangle(v.x - w2, v.x + w2, v.y - h2, v.y + h2);
});
computeGroupBounds(rootGroup);
var i = nodes.length;
groups.forEach(function (g) {
_this.variables[i] = g.minVar = new IndexedVariable(i++, typeof g.stiffness !== "undefined" ? g.stiffness : 0.01);
_this.variables[i] = g.maxVar = new IndexedVariable(i++, typeof g.stiffness !== "undefined" ? g.stiffness : 0.01);
});
}
}
Projection.prototype.createSeparation = function (c) {
return new vpsc.Constraint(this.nodes[c.left].variable, this.nodes[c.right].variable, c.gap, typeof c.equality !== "undefined" ? c.equality : false);
};
Projection.prototype.makeFeasible = function (c) {
var _this = this;
if (!this.avoidOverlaps)
return;
var axis = 'x', dim = 'width';
if (c.axis === 'x')
axis = 'y', dim = 'height';
var vs = c.offsets.map(function (o) { return _this.nodes[o.node]; }).sort(function (a, b) { return a[axis] - b[axis]; });
var p = null;
vs.forEach(function (v) {
if (p)
v[axis] = p[axis] + p[dim] + 1;
p = v;
});
};
Projection.prototype.createAlignment = function (c) {
var _this = this;
var u = this.nodes[c.offsets[0].node].variable;
this.makeFeasible(c);
var cs = c.axis === 'x' ? this.xConstraints : this.yConstraints;
c.offsets.slice(1).forEach(function (o) {
var v = _this.nodes[o.node].variable;
cs.push(new vpsc.Constraint(u, v, o.offset, true));
});
};
Projection.prototype.createConstraints = function (constraints) {
var _this = this;
var isSep = function (c) { return typeof c.type === 'undefined' || c.type === 'separation'; };
this.xConstraints = constraints
.filter(function (c) { return c.axis === "x" && isSep(c); })
.map(function (c) { return _this.createSeparation(c); });
this.yConstraints = constraints
.filter(function (c) { return c.axis === "y" && isSep(c); })
.map(function (c) { return _this.createSeparation(c); });
constraints
.filter(function (c) { return c.type === 'alignment'; })
.forEach(function (c) { return _this.createAlignment(c); });
};
Projection.prototype.setupVariablesAndBounds = function (x0, y0, desired, getDesired) {
this.nodes.forEach(function (v, i) {
if (v.fixed) {
v.variable.weight = 1000;
desired[i] = getDesired(v);
}
else {
v.variable.weight = 1;
}
var w = (v.width || 0) / 2, h = (v.height || 0) / 2;
var ix = x0[i], iy = y0[i];
v.bounds = new Rectangle(ix - w, ix + w, iy - h, iy + h);
});
};
Projection.prototype.xProject = function (x0, y0, x) {
if (!this.rootGroup && !(this.avoidOverlaps || this.xConstraints))
return;
this.project(x0, y0, x0, x, function (v) { return v.px; }, this.xConstraints, generateXGroupConstraints, function (v) { return v.bounds.setXCentre(x[v.variable.index] = v.variable.position()); }, function (g) {
var xmin = x[g.minVar.index] = g.minVar.position();
var xmax = x[g.maxVar.index] = g.maxVar.position();
var p2 = g.padding / 2;
g.bounds.x = xmin - p2;
g.bounds.X = xmax + p2;
});
};
Projection.prototype.yProject = function (x0, y0, y) {
if (!this.rootGroup && !this.yConstraints)
return;
this.project(x0, y0, y0, y, function (v) { return v.py; }, this.yConstraints, generateYGroupConstraints, function (v) { return v.bounds.setYCentre(y[v.variable.index] = v.variable.position()); }, function (g) {
var ymin = y[g.minVar.index] = g.minVar.position();
var ymax = y[g.maxVar.index] = g.maxVar.position();
var p2 = g.padding / 2;
g.bounds.y = ymin - p2;
;
g.bounds.Y = ymax + p2;
});
};
Projection.prototype.projectFunctions = function () {
var _this = this;
return [
function (x0, y0, x) { return _this.xProject(x0, y0, x); },
function (x0, y0, y) { return _this.yProject(x0, y0, y); }
];
};
Projection.prototype.project = function (x0, y0, start, desired, getDesired, cs, generateConstraints, updateNodeBounds, updateGroupBounds) {
this.setupVariablesAndBounds(x0, y0, desired, getDesired);
if (this.rootGroup && this.avoidOverlaps) {
computeGroupBounds(this.rootGroup);
cs = cs.concat(generateConstraints(this.rootGroup));
}
this.solve(this.variables, cs, start, desired);
this.nodes.forEach(updateNodeBounds);
if (this.rootGroup && this.avoidOverlaps) {
this.groups.forEach(updateGroupBounds);
}
};
Projection.prototype.solve = function (vs, cs, starting, desired) {
var solver = new vpsc.Solver(vs, cs);
solver.setStartingPositions(starting);
solver.setDesiredPositions(desired);
solver.solve();
};
return Projection;
})();
vpsc.Projection = Projection;
})(vpsc = cola.vpsc || (cola.vpsc = {}));
})(cola || (cola = {}));
///<reference path="vpsc.ts"/>
///<reference path="rectangle.ts"/>
var cola;
(function (cola) {
var geom;
(function (geom) {
var Point = (function () {
function Point() {
}
return Point;
})();
geom.Point = Point;
var LineSegment = (function () {
function LineSegment(x1, y1, x2, y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
return LineSegment;
})();
geom.LineSegment = LineSegment;
var PolyPoint = (function (_super) {
__extends(PolyPoint, _super);
function PolyPoint() {
_super.apply(this, arguments);
}
return PolyPoint;
})(Point);
geom.PolyPoint = PolyPoint;
/** tests if a point is Left|On|Right of an infinite line.
* @param points P0, P1, and P2
* @return >0 for P2 left of the line through P0 and P1
* =0 for P2 on the line
* <0 for P2 right of the line
*/
function isLeft(P0, P1, P2) {
return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
}
geom.isLeft = isLeft;
function above(p, vi, vj) {
return isLeft(p, vi, vj) > 0;
}
function below(p, vi, vj) {
return isLeft(p, vi, vj) < 0;
}
/**
* returns the convex hull of a set of points using Andrew's monotone chain algorithm
* see: http://geomalgorithms.com/a10-_hull-1.html#Monotone%20Chain
* @param S array of points
* @return the convex hull as an array of points
*/
function ConvexHull(S) {
var P = S.slice(0).sort(function (a, b) { return a.x !== b.x ? b.x - a.x : b.y - a.y; });
var n = S.length, i;
var minmin = 0;
var xmin = P[0].x;
for (i = 1; i < n; ++i) {
if (P[i].x !== xmin)
break;
}
var minmax = i - 1;
var H = [];
H.push(P[minmin]); // push minmin point onto stack
if (minmax === n - 1) {
if (P[minmax].y !== P[minmin].y)
H.push(P[minmax]);
}
else {
// Get the indices of points with max x-coord and min|max y-coord
var maxmin, maxmax = n - 1;
var xmax = P[n - 1].x;
for (i = n - 2; i >= 0; i--)
if (P[i].x !== xmax)
break;
maxmin = i + 1;
// Compute the lower hull on the stack H
i = minmax;
while (++i <= maxmin) {
// the lower line joins P[minmin] with P[maxmin]
if (isLeft(P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
continue; // ignore P[i] above or on the lower line
while (H.length > 1) {
// test if P[i] is left of the line at the stack top
if (isLeft(H[H.length - 2], H[H.length - 1], P[i]) > 0)
break; // P[i] is a new hull vertex
else
H.length -= 1; // pop top point off stack
}
if (i != minmin)
H.push(P[i]);
}
// Next, compute the upper hull on the stack H above the bottom hull
if (maxmax != maxmin)
H.push(P[maxmax]); // push maxmax point onto stack
var bot = H.length; // the bottom point of the upper hull stack
i = maxmin;
while (--i >= minmax) {
// the upper line joins P[maxmax] with P[minmax]
if (isLeft(P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
continue; // ignore P[i] below or on the upper line
while (H.length > bot) {
// test if P[i] is left of the line at the stack top
if (isLeft(H[H.length - 2], H[H.length - 1], P[i]) > 0)
break; // P[i] is a new hull vertex
else
H.length -= 1; // pop top point off stack
}
if (i != minmin)
H.push(P[i]); // push P[i] onto stack
}
}
return H;
}
geom.ConvexHull = ConvexHull;
// apply f to the points in P in clockwise order around the point p
function clockwiseRadialSweep(p, P, f) {
P.slice(0).sort(function (a, b) { return Math.atan2(a.y - p.y, a.x - p.x) - Math.atan2(b.y - p.y, b.x - p.x); }).forEach(f);
}
geom.clockwiseRadialSweep = clockwiseRadialSweep;
function nextPolyPoint(p, ps) {
if (p.polyIndex === ps.length - 1)
return ps[0];
return ps[p.polyIndex + 1];
}
function prevPolyPoint(p, ps) {
if (p.polyIndex === 0)
return ps[ps.length - 1];
return ps[p.polyIndex - 1];
}
// tangent_PointPolyC(): fast binary search for tangents to a convex polygon
// Input: P = a 2D point (exterior to the polygon)
// n = number of polygon vertices
// V = array of vertices for a 2D convex polygon with V[n] = V[0]
// Output: rtan = index of rightmost tangent point V[rtan]
// ltan = index of leftmost tangent point V[ltan]
function tangent_PointPolyC(P, V) {
return { rtan: Rtangent_PointPolyC(P, V), ltan: Ltangent_PointPolyC(P, V) };
}
// Rtangent_PointPolyC(): binary search for convex polygon right tangent
// Input: P = a 2D point (exterior to the polygon)
// n = number of polygon vertices
// V = array of vertices for a 2D convex polygon with V[n] = V[0]
// Return: index "i" of rightmost tangent point V[i]
function Rtangent_PointPolyC(P, V) {
var n = V.length - 1;
// use binary search for large convex polygons
var a, b, c; // indices for edge chain endpoints
var upA, dnC; // test for up direction of edges a and c
// rightmost tangent = maximum for the isLeft() ordering
// test if V[0] is a local maximum
if (below(P, V[1], V[0]) && !above(P, V[n - 1], V[0]))
return 0; // V[0] is the maximum tangent point
for (a = 0, b = n;;) {
if (b - a === 1)
if (above(P, V[a], V[b]))
return a;
else
return b;
c = Math.floor((a + b) / 2); // midpoint of [a,b], and 0<c<n
dnC = below(P, V[c + 1], V[c]);
if (dnC && !above(P, V[c - 1], V[c]))
return c; // V[c] is the maximum tangent point
// no max yet, so continue with the binary search
// pick one of the two subchains [a,c] or [c,b]
upA = above(P, V[a + 1], V[a]);
if (upA) {
if (dnC)
b = c; // select [a,c]
else {
if (above(P, V[a], V[c]))
b = c; // select [a,c]
else
a = c; // select [c,b]
}
}
else {
if (!dnC)
a = c; // select [c,b]
else {
if (below(P, V[a], V[c]))
b = c; // select [a,c]
else
a = c; // select [c,b]
}
}
}
}
// Ltangent_PointPolyC(): binary search for convex polygon left tangent
// Input: P = a 2D point (exterior to the polygon)
// n = number of polygon vertices
// V = array of vertices for a 2D convex polygon with V[n]=V[0]
// Return: index "i" of leftmost tangent point V[i]
function Ltangent_PointPolyC(P, V) {
var n = V.length - 1;
// use binary search for large convex polygons
var a, b, c; // indices for edge chain endpoints
var dnA, dnC; // test for down direction of edges a and c
// leftmost tangent = minimum for the isLeft() ordering
// test if V[0] is a local minimum
if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
return 0; // V[0] is the minimum tangent point
for (a = 0, b = n;;) {
if (b - a === 1)
if (below(P, V[a], V[b]))
return a;
else
return b;
c = Math.floor((a + b) / 2); // midpoint of [a,b], and 0<c<n
dnC = below(P, V[c + 1], V[c]);
if (above(P, V[c - 1], V[c]) && !dnC)
return c; // V[c] is the minimum tangent point
// no min yet, so continue with the binary search
// pick one of the two subchains [a,c] or [c,b]
dnA = below(P, V[a + 1], V[a]);
if (dnA) {
if (!dnC)
b = c; // select [a,c]
else {
if (below(P, V[a], V[c]))
b = c; // select [a,c]
else
a = c; // select [c,b]
}
}
else {
if (dnC)
a = c; // select [c,b]
else {
if (above(P, V[a], V[c]))
b = c; // select [a,c]
else
a = c; // select [c,b]
}
}
}
}
// RLtangent_PolyPolyC(): get the RL tangent between two convex polygons
// Input: m = number of vertices in polygon 1
// V = array of vertices for convex polygon 1 with V[m]=V[0]
// n = number of vertices in polygon 2
// W = array of vertices for convex polygon 2 with W[n]=W[0]
// Output: *t1 = index of tangent point V[t1] for polygon 1
// *t2 = index of tangent point W[t2] for polygon 2
function tangent_PolyPolyC(V, W, t1, t2, cmp1, cmp2) {
var ix1, ix2; // search indices for polygons 1 and 2
// first get the initial vertex on each polygon
ix1 = t1(W[0], V); // right tangent from W[0] to V
ix2 = t2(V[ix1], W); // left tangent from V[ix1] to W
// ping-pong linear search until it stabilizes
var done = false; // flag when done
while (!done) {
done = true; // assume done until...
while (true) {
if (ix1 === V.length - 1)
ix1 = 0;
if (cmp1(W[ix2], V[ix1], V[ix1 + 1]))
break;
++ix1; // get Rtangent from W[ix2] to V
}
while (true) {
if (ix2 === 0)
ix2 = W.length - 1;
if (cmp2(V[ix1], W[ix2], W[ix2 - 1]))
break;
--ix2; // get Ltangent from V[ix1] to W
done = false; // not done if had to adjust this
}
}
return { t1: ix1, t2: ix2 };
}
geom.tangent_PolyPolyC = tangent_PolyPolyC;
function LRtangent_PolyPolyC(V, W) {
var rl = RLtangent_PolyPolyC(W, V);
return { t1: rl.t2, t2: rl.t1 };
}
geom.LRtangent_PolyPolyC = LRtangent_PolyPolyC;
function RLtangent_PolyPolyC(V, W) {
return tangent_PolyPolyC(V, W, Rtangent_PointPolyC, Ltangent_PointPolyC, above, below);
}
geom.RLtangent_PolyPolyC = RLtangent_PolyPolyC;
function LLtangent_PolyPolyC(V, W) {
return tangent_PolyPolyC(V, W, Ltangent_PointPolyC, Ltangent_PointPolyC, below, below);
}
geom.LLtangent_PolyPolyC = LLtangent_PolyPolyC;
function RRtangent_PolyPolyC(V, W) {
return tangent_PolyPolyC(V, W, Rtangent_PointPolyC, Rtangent_PointPolyC, above, above);
}
geom.RRtangent_PolyPolyC = RRtangent_PolyPolyC;
var BiTangent = (function () {
function BiTangent(t1, t2) {
this.t1 = t1;
this.t2 = t2;
}
return BiTangent;
})();
geom.BiTangent = BiTangent;
var BiTangents = (function () {
function BiTangents() {
}
return BiTangents;
})();
geom.BiTangents = BiTangents;
var TVGPoint = (function (_super) {
__extends(TVGPoint, _super);
function TVGPoint() {
_super.apply(this, arguments);
}
return TVGPoint;
})(Point);
geom.TVGPoint = TVGPoint;
var VisibilityVertex = (function () {
function VisibilityVertex(id, polyid, polyvertid, p) {
this.id = id;
this.polyid = polyid;
this.polyvertid = polyvertid;
this.p = p;
p.vv = this;
}
return VisibilityVertex;
})();
geom.VisibilityVertex = VisibilityVertex;
var VisibilityEdge = (function () {
function VisibilityEdge(source, target) {
this.source = source;
this.target = target;
}
VisibilityEdge.prototype.length = function () {
var dx = this.source.p.x - this.target.p.x;
var dy = this.source.p.y - this.target.p.y;
return Math.sqrt(dx * dx + dy * dy);
};
return VisibilityEdge;
})();
geom.VisibilityEdge = VisibilityEdge;
var TangentVisibilityGraph = (function () {
function TangentVisibilityGraph(P, g0) {
this.P = P;
this.V = [];
this.E = [];
if (!g0) {
var n = P.length;
for (var i = 0; i < n; i++) {
var p = P[i];
for (var j = 0; j < p.length; ++j) {
var pj = p[j], vv = new VisibilityVertex(this.V.length, i, j, pj);
this.V.push(vv);
if (j > 0)
this.E.push(new VisibilityEdge(p[j - 1].vv, vv));
}
}
for (var i = 0; i < n - 1; i++) {
var Pi = P[i];
for (var j = i + 1; j < n; j++) {
var Pj = P[j], t = geom.tangents(Pi, Pj);
for (var q in t) {
var c = t[q], source = Pi[c.t1], target = Pj[c.t2];
this.addEdgeIfVisible(source, target, i, j);
}
}
}
}
else {
this.V = g0.V.slice(0);
this.E = g0.E.slice(0);
}
}
TangentVisibilityGraph.prototype.addEdgeIfVisible = function (u, v, i1, i2) {
if (!this.intersectsPolys(new LineSegment(u.x, u.y, v.x, v.y), i1, i2)) {
this.E.push(new VisibilityEdge(u.vv, v.vv));
}
};
TangentVisibilityGraph.prototype.addPoint = function (p, i1) {
var n = this.P.length;
this.V.push(new VisibilityVertex(this.V.length, n, 0, p));
for (var i = 0; i < n; ++i) {
if (i === i1)
continue;
var poly = this.P[i], t = tangent_PointPolyC(p, poly);
this.addEdgeIfVisible(p, poly[t.ltan], i1, i);
this.addEdgeIfVisible(p, poly[t.rtan], i1, i);
}
return p.vv;
};
TangentVisibilityGraph.prototype.intersectsPolys = function (l, i1, i2) {
for (var i = 0, n = this.P.length; i < n; ++i) {
if (i != i1 && i != i2 && intersects(l, this.P[i]).length > 0) {
return true;
}
}
return false;
};
return TangentVisibilityGraph;
})();
geom.TangentVisibilityGraph = TangentVisibilityGraph;
function intersects(l, P) {
var ints = [];
for (var i = 1, n = P.length; i < n; ++i) {
var int = cola.vpsc.Rectangle.lineIntersection(l.x1, l.y1, l.x2, l.y2, P[i - 1].x, P[i - 1].y, P[i].x, P[i].y);
if (int)
ints.push(int);
}
return ints;
}
function tangents(V, W) {
var m = V.length - 1, n = W.length - 1;
var bt = new BiTangents();
for (var i = 0; i < m; ++i) {
for (var j = 0; j < n; ++j) {
var v1 = V[i == 0 ? m - 1 : i - 1];
var v2 = V[i];
var v3 = V[i + 1];
var w1 = W[j == 0 ? n - 1 : j - 1];
var w2 = W[j];
var w3 = W[j + 1];
var v1v2w2 = isLeft(v1, v2, w2);
var v2w1w2 = isLeft(v2, w1, w2);
var v2w2w3 = isLeft(v2, w2, w3);
var w1w2v2 = isLeft(w1, w2, v2);
var w2v1v2 = isLeft(w2, v1, v2);
var w2v2v3 = isLeft(w2, v2, v3);
if (v1v2w2 >= 0 && v2w1w2 >= 0 && v2w2w3 < 0
&& w1w2v2 >= 0 && w2v1v2 >= 0 && w2v2v3 < 0) {
bt.ll = new BiTangent(i, j);
}
else if (v1v2w2 <= 0 && v2w1w2 <= 0 && v2w2w3 > 0
&& w1w2v2 <= 0 && w2v1v2 <= 0 && w2v2v3 > 0) {
bt.rr = new BiTangent(i, j);
}
else if (v1v2w2 <= 0 && v2w1w2 > 0 && v2w2w3 <= 0
&& w1w2v2 >= 0 && w2v1v2 < 0 && w2v2v3 >= 0) {
bt.rl = new BiTangent(i, j);
}
else if (v1v2w2 >= 0 && v2w1w2 < 0 && v2w2w3 >= 0
&& w1w2v2 <= 0 && w2v1v2 > 0 && w2v2v3 <= 0) {
bt.lr = new BiTangent(i, j);
}
}
}
return bt;
}
geom.tangents = tangents;
function isPointInsidePoly(p, poly) {
for (var i = 1, n = poly.length; i < n; ++i)
if (below(poly[i - 1], poly[i], p))
return false;
return true;
}
function isAnyPInQ(p, q) {
return !p.every(function (v) { return !isPointInsidePoly(v, q); });
}
function polysOverlap(p, q) {
if (isAnyPInQ(p, q))
return true;
if (isAnyPInQ(q, p))
return true;
for (var i = 1, n = p.length; i < n; ++i) {
var v = p[i], u = p[i - 1];
if (intersects(new LineSegment(u.x, u.y, v.x, v.y), q).length > 0)
return true;
}
return false;
}
geom.polysOverlap = polysOverlap;
})(geom = cola.geom || (cola.geom = {}));
})(cola || (cola = {}));
/**
* @module cola
*/
var cola;
(function (cola) {
/**
* Descent respects a collection of locks over nodes that should not move
* @class Locks
*/
var Locks = (function () {
function Locks() {
this.locks = {};
}
/**
* add a lock on the node at index id
* @method add
* @param id index of node to be locked
* @param x required position for node
*/
Locks.prototype.add = function (id, x) {
if (isNaN(x[0]) || isNaN(x[1]))
debugger;
this.locks[id] = x;
};
/**
* @method clear clear all locks
*/
Locks.prototype.clear = function () {
this.locks = {};
};
/**
* @isEmpty
* @returns false if no locks exist
*/
Locks.prototype.isEmpty = function () {
for (var l in this.locks)
return false;
return true;
};
/**
* perform an operation on each lock
* @apply
*/
Locks.prototype.apply = function (f) {
for (var l in this.locks) {
f(l, this.locks[l]);
}
};
return Locks;
})();
cola.Locks = Locks;
/**
* Uses a gradient descent approach to reduce a stress or p-stress goal function over a graph with specified ideal edge lengths or a square matrix of dissimilarities.
* The standard stress function over a graph nodes with position vectors x,y,z is (mathematica input):
* stress[x_,y_,z_,D_,w_]:=Sum[w[[i,j]] (length[x[[i]],y[[i]],z[[i]],x[[j]],y[[j]],z[[j]]]-d[[i,j]])^2,{i,Length[x]-1},{j,i+1,Length[x]}]
* where: D is a square matrix of ideal separations between nodes, w is matrix of weights for those separations
* length[x1_, y1_, z1_, x2_, y2_, z2_] = Sqrt[(x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2]
* below, we use wij = 1/(Dij^2)
*
* @class Descent
*/
var Descent = (function () {
/**
* @method constructor
* @param x {number[][]} initial coordinates for nodes
* @param D {number[][]} matrix of desired distances between pairs of nodes
* @param G {number[][]} [default=null] if specified, G is a matrix of weights for goal terms between pairs of nodes.
* If G[i][j] > 1 and the separation between nodes i and j is greater than their ideal distance, then there is no contribution for this pair to the goal
* If G[i][j] <= 1 then it is used as a weighting on the contribution of the variance between ideal and actual separation between i and j to the goal function
*/
function Descent(x, D, G) {
if (G === void 0) { G = null; }
this.D = D;
this.G = G;
this.threshold = 0.0001;
// Parameters for grid snap stress.
// TODO: Make a pluggable "StressTerm" class instead of this
// mess.
this.numGridSnapNodes = 0;
this.snapGridSize = 100;
this.snapStrength = 1000;
this.scaleSnapByMaxH = false;
this.random = new PseudoRandom();
this.project = null;
this.x = x;
this.k = x.length; // dimensionality
var n = this.n = x[0].length; // number of nodes
this.H = new Array(this.k);
this.g = new Array(this.k);
this.Hd = new Array(this.k);
this.a = new Array(this.k);
this.b = new Array(this.k);
this.c = new Array(this.k);
this.d = new Array(this.k);
this.e = new Array(this.k);
this.ia = new Array(this.k);
this.ib = new Array(this.k);
this.xtmp = new Array(this.k);
this.locks = new Locks();
this.minD = Number.MAX_VALUE;
var i = n, j;
while (i--) {
j = n;
while (--j > i) {
var d = D[i][j];
if (d > 0 && d < this.minD) {
this.minD = d;
}
}
}
if (this.minD === Number.MAX_VALUE)
this.minD = 1;
i = this.k;
while (i--) {
this.g[i] = new Array(n);
this.H[i] = new Array(n);
j = n;
while (j--) {
this.H[i][j] = new Array(n);
}
this.Hd[i] = new Array(n);
this.a[i] = new Array(n);
this.b[i] = new Array(n);
this.c[i] = new Array(n);
this.d[i] = new Array(n);
this.e[i] = new Array(n);
this.ia[i] = new Array(n);
this.ib[i] = new Array(n);
this.xtmp[i] = new Array(n);
}
}
Descent.createSquareMatrix = function (n, f) {
var M = new Array(n);
for (var i = 0; i < n; ++i) {
M[i] = new Array(n);
for (var j = 0; j < n; ++j) {
M[i][j] = f(i, j);
}
}
return M;
};
Descent.prototype.offsetDir = function () {
var _this = this;
var u = new Array(this.k);
var l = 0;
for (var i = 0; i < this.k; ++i) {
var x = u[i] = this.random.getNextBetween(0.01, 1) - 0.5;
l += x * x;
}
l = Math.sqrt(l);
return u.map(function (x) { return x *= _this.minD / l; });
};
// compute first and second derivative information storing results in this.g and this.H
Descent.prototype.computeDerivatives = function (x) {
var _this = this;
var n = this.n;
if (n < 1)
return;
var i;
/* DEBUG
for (var u: number = 0; u < n; ++u)
for (i = 0; i < this.k; ++i)
if (isNaN(x[i][u])) debugger;
DEBUG */
var d = new Array(this.k);
var d2 = new Array(this.k);
var Huu = new Array(this.k);
var maxH = 0;
for (var u = 0; u < n; ++u) {
for (i = 0; i < this.k; ++i)
Huu[i] = this.g[i][u] = 0;
for (var v = 0; v < n; ++v) {
if (u === v)
continue;
// The following loop randomly displaces nodes that are at identical positions
var maxDisplaces = n; // avoid infinite loop in the case of numerical issues, such as huge values
while (maxDisplaces--) {
var sd2 = 0;
for (i = 0; i < this.k; ++i) {
var dx = d[i] = x[i][u] - x[i][v];
sd2 += d2[i] = dx * dx;
}
if (sd2 > 1e-9)
break;
var rd = this.offsetDir();
for (i = 0; i < this.k; ++i)
x[i][v] += rd[i];
}
var l = Math.sqrt(sd2);
var D = this.D[u][v];
var weight = this.G != null ? this.G[u][v] : 1;
if (weight > 1 && l > D || !isFinite(D)) {
for (i = 0; i < this.k; ++i)
this.H[i][u][v] = 0;
continue;
}
if (weight > 1) {
weight = 1;
}
var D2 = D * D;
var gs = 2 * weight * (l - D) / (D2 * l);
var l3 = l * l * l;
var hs = 2 * -weight / (D2 * l3);
if (!isFinite(gs))
console.log(gs);
for (i = 0; i < this.k; ++i) {
this.g[i][u] += d[i] * gs;
Huu[i] -= this.H[i][u][v] = hs * (l3 + D * (d2[i] - sd2) + l * sd2);
}
}
for (i = 0; i < this.k; ++i)
maxH = Math.max(maxH, this.H[i][u][u] = Huu[i]);
}
// Grid snap forces
var r = this.snapGridSize / 2;
var g = this.snapGridSize;
var w = this.snapStrength;
var k = w / (r * r);
var numNodes = this.numGridSnapNodes;
//var numNodes = n;
for (var u = 0; u < numNodes; ++u) {
for (i = 0; i < this.k; ++i) {
var xiu = this.x[i][u];
var m = xiu / g;
var f = m % 1;
var q = m - f;
var a = Math.abs(f);
var dx = (a <= 0.5) ? xiu - q * g :
(xiu > 0) ? xiu - (q + 1) * g : xiu - (q - 1) * g;
if (-r < dx && dx <= r) {
if (this.scaleSnapByMaxH) {
this.g[i][u] += maxH * k * dx;
this.H[i][u][u] += maxH * k;
}
else {
this.g[i][u] += k * dx;
this.H[i][u][u] += k;
}
}
}
}
if (!this.locks.isEmpty()) {
this.locks.apply(function (u, p) {
for (i = 0; i < _this.k; ++i) {
_this.H[i][u][u] += maxH;
_this.g[i][u] -= maxH * (p[i] - x[i][u]);
}
});
}
/* DEBUG
for (var u: number = 0; u < n; ++u)
for (i = 0; i < this.k; ++i) {
if (isNaN(this.g[i][u])) debugger;
for (var v: number = 0; v < n; ++v)
if (isNaN(this.H[i][u][v])) debugger;
}
DEBUG */
};
Descent.dotProd = function (a, b) {
var x = 0, i = a.length;
while (i--)
x += a[i] * b[i];
return x;
};
// result r = matrix m * vector v
Descent.rightMultiply = function (m, v, r) {
var i = m.length;
while (i--)
r[i] = Descent.dotProd(m[i], v);
};
// computes the optimal step size to take in direction d using the
// derivative information in this.g and this.H
// returns the scalar multiplier to apply to d to get the optimal step
Descent.prototype.computeStepSize = function (d) {
var numerator = 0, denominator = 0;
for (var i = 0; i < this.k; ++i) {
numerator += Descent.dotProd(this.g[i], d[i]);
Descent.rightMultiply(this.H[i], d[i], this.Hd[i]);
denominator += Descent.dotProd(d[i], this.Hd[i]);
}
if (denominator === 0 || !isFinite(denominator))
return 0;
return 1 * numerator / denominator;
};
Descent.prototype.reduceStress = function () {
this.computeDerivatives(this.x);
var alpha = this.computeStepSize(this.g);
for (var i = 0; i < this.k; ++i) {
this.takeDescentStep(this.x[i], this.g[i], alpha);
}
return this.computeStress();
};
Descent.copy = function (a, b) {
var m = a.length, n = b[0].length;
for (var i = 0; i < m; ++i) {
for (var j = 0; j < n; ++j) {
b[i][j] = a[i][j];
}
}
};
// takes a step of stepSize * d from x0, and then project against any constraints.
// result is returned in r.
// x0: starting positions
// r: result positions will be returned here
// d: unconstrained descent vector
// stepSize: amount to step along d
Descent.prototype.stepAndProject = function (x0, r, d, stepSize) {
var _this = this;
Descent.copy(x0, r);
this.takeDescentStep(r[0], d[0], stepSize);
if (this.project)
this.project[0](x0[0], x0[1], r[0]);
this.takeDescentStep(r[1], d[1], stepSize);
if (this.project)
this.project[1](r[0], x0[1], r[1]);
// todo: allow projection against constraints in higher dimensions
for (var i = 2; i < this.k; i++)
this.takeDescentStep(r[i], d[i], stepSize);
if (!this.locks.isEmpty()) {
this.locks.apply(function (u, p) {
for (var i = 0; i < _this.k; i++) {
r[i][u] = p[i];
}
});
}
};
Descent.mApply = function (m, n, f) {
var i = m;
while (i-- > 0) {
var j = n;
while (j-- > 0)
f(i, j);
}
};
Descent.prototype.matrixApply = function (f) {
Descent.mApply(this.k, this.n, f);
};
Descent.prototype.computeNextPosition = function (x0, r) {
var _this = this;
this.computeDerivatives(x0);
var alpha = this.computeStepSize(this.g);
this.stepAndProject(x0, r, this.g, alpha);
for (var u = 0; u < this.n; ++u)
for (var i = 0; i < this.k; ++i)
if (isNaN(r[i][u]))
debugger;
if (this.project) {
this.matrixApply(function (i, j) { return _this.e[i][j] = x0[i][j] - r[i][j]; });
var beta = this.computeStepSize(this.e);
beta = Math.max(0.2, Math.min(beta, 1));
this.stepAndProject(x0, r, this.e, beta);
}
};
Descent.prototype.run = function (iterations) {
var stress = Number.MAX_VALUE, converged = false;
while (!converged && iterations-- > 0) {
var s = this.rungeKutta();
converged = Math.abs(stress / s - 1) < this.threshold;
stress = s;
}
return stress;
};
Descent.prototype.rungeKutta = function () {
var _this = this;
this.computeNextPosition(this.x, this.a);
Descent.mid(this.x, this.a, this.ia);
this.computeNextPosition(this.ia, this.b);
Descent.mid(this.x, this.b, this.ib);
this.computeNextPosition(this.ib, this.c);
this.computeNextPosition(this.c, this.d);
var disp = 0;
this.matrixApply(function (i, j) {
var x = (_this.a[i][j] + 2.0 * _this.b[i][j] + 2.0 * _this.c[i][j] + _this.d[i][j]) / 6.0, d = _this.x[i][j] - x;
disp += d * d;
_this.x[i][j] = x;
});
return disp;
};
Descent.mid = function (a, b, m) {
Descent.mApply(a.length, a[0].length, function (i, j) {
return m[i][j] = a[i][j] + (b[i][j] - a[i][j]) / 2.0;
});
};
Descent.prototype.takeDescentStep = function (x, d, stepSize) {
for (var i = 0; i < this.n; ++i) {
x[i] = x[i] - stepSize * d[i];
}
};
Descent.prototype.computeStress = function () {
var stress = 0;
for (var u = 0, nMinus1 = this.n - 1; u < nMinus1; ++u) {
for (var v = u + 1, n = this.n; v < n; ++v) {
var l = 0;
for (var i = 0; i < this.k; ++i) {
var dx = this.x[i][u] - this.x[i][v];
l += dx * dx;
}
l = Math.sqrt(l);
var d = this.D[u][v];
if (!isFinite(d))
continue;
var rl = d - l;
var d2 = d * d;
stress += rl * rl / d2;
}
}
return stress;
};
Descent.zeroDistance = 1e-10;
return Descent;
})();
cola.Descent = Descent;
// Linear congruential pseudo random number generator
var PseudoRandom = (function () {
function PseudoRandom(seed) {
if (seed === void 0) { seed = 1; }
this.seed = seed;
this.a = 214013;
this.c = 2531011;
this.m = 2147483648;
this.range = 32767;
}
// random real between 0 and 1
PseudoRandom.prototype.getNext = function () {
this.seed = (this.seed * this.a + this.c) % this.m;
return (this.seed >> 16) / this.range;
};
// random real between min and max
PseudoRandom.prototype.getNextBetween = function (min, max) {
return min + this.getNext() * (max - min);
};
return PseudoRandom;
})();
cola.PseudoRandom = PseudoRandom;
})(cola || (cola = {}));
var cola;
(function (cola) {
var powergraph;
(function (powergraph) {
var PowerEdge = (function () {
function PowerEdge(source, target, type) {
this.source = source;
this.target = target;
this.type = type;
}
return PowerEdge;
})();
powergraph.PowerEdge = PowerEdge;
var Configuration = (function () {
function Configuration(n, edges, linkAccessor, rootGroup) {
var _this = this;
this.linkAccessor = linkAccessor;
this.modules = new Array(n);
this.roots = [];
if (rootGroup) {
this.initModulesFromGroup(rootGroup);
}
else {
this.roots.push(new ModuleSet());
for (var i = 0; i < n; ++i)
this.roots[0].add(this.modules[i] = new Module(i));
}
this.R = edges.length;
edges.forEach(function (e) {
var s = _this.modules[linkAccessor.getSourceIndex(e)], t = _this.modules[linkAccessor.getTargetIndex(e)], type = linkAccessor.getType(e);
s.outgoing.add(type, t);
t.incoming.add(type, s);
});
}
Configuration.prototype.initModulesFromGroup = function (group) {
var moduleSet = new ModuleSet();
this.roots.push(moduleSet);
for (var i = 0; i < group.leaves.length; ++i) {
var node = group.leaves[i];
var module = new Module(node.id);
this.modules[node.id] = module;
moduleSet.add(module);
}
if (group.groups) {
for (var j = 0; j < group.groups.length; ++j) {
var child = group.groups[j];
// Propagate group properties (like padding, stiffness, ...) as module definition so that the generated power graph group will inherit it
var definition = {};
for (var prop in child)
if (prop !== "leaves" && prop !== "groups" && child.hasOwnProperty(prop))
definition[prop] = child[prop];
// Use negative module id to avoid clashes between predefined and generated modules
moduleSet.add(new Module(-1 - j, new LinkSets(), new LinkSets(), this.initModulesFromGroup(child), definition));
}
}
return moduleSet;
};
// merge modules a and b keeping track of their power edges and removing the from roots
Configuration.prototype.merge = function (a, b, k) {
if (k === void 0) { k = 0; }
var inInt = a.incoming.intersection(b.incoming), outInt = a.outgoing.intersection(b.outgoing);
var children = new ModuleSet();
children.add(a);
children.add(b);
var m = new Module(this.modules.length, outInt, inInt, children);
this.modules.push(m);
var update = function (s, i, o) {
s.forAll(function (ms, linktype) {
ms.forAll(function (n) {
var nls = n[i];
nls.add(linktype, m);
nls.remove(linktype, a);
nls.remove(linktype, b);
a[o].remove(linktype, n);
b[o].remove(linktype, n);
});
});
};
update(outInt, "incoming", "outgoing");
update(inInt, "outgoing", "incoming");
this.R -= inInt.count() + outInt.count();
this.roots[k].remove(a);
this.roots[k].remove(b);
this.roots[k].add(m);
return m;
};
Configuration.prototype.rootMerges = function (k) {
if (k === void 0) { k = 0; }
var rs = this.roots[k].modules();
var n = rs.length;
var merges = new Array(n * (n - 1));
var ctr = 0;
for (var i = 0, i_ = n - 1; i < i_; ++i) {
for (var j = i + 1; j < n; ++j) {
var a = rs[i], b = rs[j];
merges[ctr] = { id: ctr, nEdges: this.nEdges(a, b), a: a, b: b };
ctr++;
}
}
return merges;
};
Configuration.prototype.greedyMerge = function () {
for (var i = 0; i < this.roots.length; ++i) {
// Handle single nested module case
if (this.roots[i].modules().length < 2)
continue;
// find the merge that allows for the most edges to be removed. secondary ordering based on arbitrary id (for predictability)
var ms = this.rootMerges(i).sort(function (a, b) { return a.nEdges == b.nEdges ? a.id - b.id : a.nEdges - b.nEdges; });
var m = ms[0];
if (m.nEdges >= this.R)
continue;
this.merge(m.a, m.b, i);
return true;
}
};
Configuration.prototype.nEdges = function (a, b) {
var inInt = a.incoming.intersection(b.incoming), outInt = a.outgoing.intersection(b.outgoing);
return this.R - inInt.count() - outInt.count();
};
Configuration.prototype.getGroupHierarchy = function (retargetedEdges) {
var _this = this;
var groups = [];
var root = {};
toGroups(this.roots[0], root, groups);
var es = this.allEdges();
es.forEach(function (e) {
var a = _this.modules[e.source];
var b = _this.modules[e.target];
retargetedEdges.push(new PowerEdge(typeof a.gid === "undefined" ? e.source : groups[a.gid], typeof b.gid === "undefined" ? e.target : groups[b.gid], e.type));
});
return groups;
};
Configuration.prototype.allEdges = function () {
var es = [];
Configuration.getEdges(this.roots[0], es);
return es;
};
Configuration.getEdges = function (modules, es) {
modules.forAll(function (m) {
m.getEdges(es);
Configuration.getEdges(m.children, es);
});
};
return Configuration;
})();
powergraph.Configuration = Configuration;
function toGroups(modules, group, groups) {
modules.forAll(function (m) {
if (m.isLeaf()) {
if (!group.leaves)
group.leaves = [];
group.leaves.push(m.id);
}
else {
var g = group;
m.gid = groups.length;
if (!m.isIsland() || m.isPredefined()) {
g = { id: m.gid };
if (m.isPredefined())
// Apply original group properties
for (var prop in m.definition)
g[prop] = m.definition[prop];
if (!group.groups)
group.groups = [];
group.groups.push(m.gid);
groups.push(g);
}
toGroups(m.children, g, groups);
}
});
}
var Module = (function () {
function Module(id, outgoing, incoming, children, definition) {
if (outgoing === void 0) { outgoing = new LinkSets(); }
if (incoming === void 0) { incoming = new LinkSets(); }
if (children === void 0) { children = new ModuleSet(); }
this.id = id;
this.outgoing = outgoing;
this.incoming = incoming;
this.children = children;
this.definition = definition;
}
Module.prototype.getEdges = function (es) {
var _this = this;
this.outgoing.forAll(function (ms, edgetype) {
ms.forAll(function (target) {
es.push(new PowerEdge(_this.id, target.id, edgetype));
});
});
};
Module.prototype.isLeaf = function () {
return this.children.count() === 0;
};
Module.prototype.isIsland = function () {
return this.outgoing.count() === 0 && this.incoming.count() === 0;
};
Module.prototype.isPredefined = function () {
return typeof this.definition !== "undefined";
};
return Module;
})();
powergraph.Module = Module;
function intersection(m, n) {
var i = {};
for (var v in m)
if (v in n)
i[v] = m[v];
return i;
}
var ModuleSet = (function () {
function ModuleSet() {
this.table = {};
}
ModuleSet.prototype.count = function () {
return Object.keys(this.table).length;
};
ModuleSet.prototype.intersection = function (other) {
var result = new ModuleSet();
result.table = intersection(this.table, other.table);
return result;
};
ModuleSet.prototype.intersectionCount = function (other) {
return this.intersection(other).count();
};
ModuleSet.prototype.contains = function (id) {
return id in this.table;
};
ModuleSet.prototype.add = function (m) {
this.table[m.id] = m;
};
ModuleSet.prototype.remove = function (m) {
delete this.table[m.id];
};
ModuleSet.prototype.forAll = function (f) {
for (var mid in this.table) {
f(this.table[mid]);
}
};
ModuleSet.prototype.modules = function () {
var vs = [];
this.forAll(function (m) {
if (!m.isPredefined())
vs.push(m);
});
return vs;
};
return ModuleSet;
})();
powergraph.ModuleSet = ModuleSet;
var LinkSets = (function () {
function LinkSets() {
this.sets = {};
this.n = 0;
}
LinkSets.prototype.count = function () {
return this.n;
};
LinkSets.prototype.contains = function (id) {
var result = false;
this.forAllModules(function (m) {
if (!result && m.id == id) {
result = true;
}
});
return result;
};
LinkSets.prototype.add = function (linktype, m) {
var s = linktype in this.sets ? this.sets[linktype] : this.sets[linktype] = new ModuleSet();
s.add(m);
++this.n;
};
LinkSets.prototype.remove = function (linktype, m) {
var ms = this.sets[linktype];
ms.remove(m);
if (ms.count() === 0) {
delete this.sets[linktype];
}
--this.n;
};
LinkSets.prototype.forAll = function (f) {
for (var linktype in this.sets) {
f(this.sets[linktype], linktype);
}
};
LinkSets.prototype.forAllModules = function (f) {
this.forAll(function (ms, lt) { return ms.forAll(f); });
};
LinkSets.prototype.intersection = function (other) {
var result = new LinkSets();
this.forAll(function (ms, lt) {
if (lt in other.sets) {
var i = ms.intersection(other.sets[lt]), n = i.count();
if (n > 0) {
result.sets[lt] = i;
result.n += n;
}
}
});
return result;
};
return LinkSets;
})();
powergraph.LinkSets = LinkSets;
function intersectionCount(m, n) {
return Object.keys(intersection(m, n)).length;
}
function getGroups(nodes, links, la, rootGroup) {
var n = nodes.length, c = new powergraph.Configuration(n, links, la, rootGroup);
while (c.greedyMerge())
;
var powerEdges = [];
var g = c.getGroupHierarchy(powerEdges);
powerEdges.forEach(function (e) {
var f = function (end) {
var g = e[end];
if (typeof g == "number")
e[end] = nodes[g];
};
f("source");
f("target");
});
return { groups: g, powerEdges: powerEdges };
}
powergraph.getGroups = getGroups;
})(powergraph = cola.powergraph || (cola.powergraph = {}));
})(cola || (cola = {}));
/**
* @module cola
*/
var cola;
(function (cola) {
// compute the size of the union of two sets a and b
function unionCount(a, b) {
var u = {};
for (var i in a)
u[i] = {};
for (var i in b)
u[i] = {};
return Object.keys(u).length;
}
// compute the size of the intersection of two sets a and b
function intersectionCount(a, b) {
var n = 0;
for (var i in a)
if (typeof b[i] !== 'undefined')
++n;
return n;
}
function getNeighbours(links, la) {
var neighbours = {};
var addNeighbours = function (u, v) {
if (typeof neighbours[u] === 'undefined')
neighbours[u] = {};
neighbours[u][v] = {};
};
links.forEach(function (e) {
var u = la.getSourceIndex(e), v = la.getTargetIndex(e);
addNeighbours(u, v);
addNeighbours(v, u);
});
return neighbours;
}
// modify the lengths of the specified links by the result of function f weighted by w
function computeLinkLengths(links, w, f, la) {
var neighbours = getNeighbours(links, la);
links.forEach(function (l) {
var a = neighbours[la.getSourceIndex(l)];
var b = neighbours[la.getTargetIndex(l)];
la.setLength(l, 1 + w * f(a, b));
});
}
/** modify the specified link lengths based on the symmetric difference of their neighbours
* @class symmetricDiffLinkLengths
*/
function symmetricDiffLinkLengths(links, la, w) {
if (w === void 0) { w = 1; }
computeLinkLengths(links, w, function (a, b) { return Math.sqrt(unionCount(a, b) - intersectionCount(a, b)); }, la);
}
cola.symmetricDiffLinkLengths = symmetricDiffLinkLengths;
/** modify the specified links lengths based on the jaccard difference between their neighbours
* @class jaccardLinkLengths
*/
function jaccardLinkLengths(links, la, w) {
if (w === void 0) { w = 1; }
computeLinkLengths(links, w, function (a, b) {
return Math.min(Object.keys(a).length, Object.keys(b).length) < 1.1 ? 0 : intersectionCount(a, b) / unionCount(a, b);
}, la);
}
cola.jaccardLinkLengths = jaccardLinkLengths;
/** generate separation constraints for all edges unless both their source and sink are in the same strongly connected component
* @class generateDirectedEdgeConstraints
*/
function generateDirectedEdgeConstraints(n, links, axis, la) {
var components = stronglyConnectedComponents(n, links, la);
var nodes = {};
components.filter(function (c) { return c.length > 1; }).forEach(function (c) {
return c.forEach(function (v) { return nodes[v] = c; });
});
var constraints = [];
links.forEach(function (l) {
var ui = la.getSourceIndex(l), vi = la.getTargetIndex(l), u = nodes[ui], v = nodes[vi];
if (!u || !v || u.component !== v.component) {
constraints.push({
axis: axis,
left: ui,
right: vi,
gap: la.getMinSeparation(l)
});
}
});
return constraints;
}
cola.generateDirectedEdgeConstraints = generateDirectedEdgeConstraints;
/*
Following function based on: https://github.com/mikolalysenko/strongly-connected-components
The MIT License (MIT)
Copyright (c) 2013 Mikola Lysenko
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.
*/
function stronglyConnectedComponents(numVertices, edges, la) {
var adjList = new Array(numVertices);
var index = new Array(numVertices);
var lowValue = new Array(numVertices);
var active = new Array(numVertices);
//Initialize tables
for (var i = 0; i < numVertices; ++i) {
adjList[i] = [];
index[i] = -1;
lowValue[i] = 0;
active[i] = false;
}
//Build adjacency list representation
for (var i = 0; i < edges.length; ++i) {
adjList[la.getSourceIndex(edges[i])].push(la.getTargetIndex(edges[i]));
}
var count = 0;
var S = [];
var components = [];
function strongConnect(v) {
index[v] = count;
lowValue[v] = count;
active[v] = true;
count += 1;
S.push(v);
var e = adjList[v];
for (var i = 0; i < e.length; ++i) {
var u = e[i];
if (index[u] < 0) {
strongConnect(u);
lowValue[v] = Math.min(lowValue[v], lowValue[u]) | 0;
}
else if (active[u]) {
lowValue[v] = Math.min(lowValue[v], lowValue[u]);
}
}
if (lowValue[v] === index[v]) {
var component = [];
for (var i = S.length - 1; i >= 0; --i) {
var w = S[i];
active[w] = false;
component.push(w);
if (w === v) {
S.length = i;
break;
}
}
components.push(component);
}
}
//Run strong connect starting from each vertex
for (var i = 0; i < numVertices; ++i) {
if (index[i] < 0) {
strongConnect(i);
}
}
return components;
}
})(cola || (cola = {}));
var PairingHeap = (function () {
// from: https://gist.github.com/nervoussystem
//{elem:object, subheaps:[array of heaps]}
function PairingHeap(elem) {
this.elem = elem;
this.subheaps = [];
}
PairingHeap.prototype.toString = function (selector) {
var str = "", needComma = false;
for (var i = 0; i < this.subheaps.length; ++i) {
var subheap = this.subheaps[i];
if (!subheap.elem) {
needComma = false;
continue;
}
if (needComma) {
str = str + ",";
}
str = str + subheap.toString(selector);
needComma = true;
}
if (str !== "") {
str = "(" + str + ")";
}
return (this.elem ? selector(this.elem) : "") + str;
};
PairingHeap.prototype.forEach = function (f) {
if (!this.empty()) {
f(this.elem, this);
this.subheaps.forEach(function (s) { return s.forEach(f); });
}
};
PairingHeap.prototype.count = function () {
return this.empty() ? 0 : 1 + this.subheaps.reduce(function (n, h) {
return n + h.count();
}, 0);
};
PairingHeap.prototype.min = function () {
return this.elem;
};
PairingHeap.prototype.empty = function () {
return this.elem == null;
};
PairingHeap.prototype.contains = function (h) {
if (this === h)
return true;
for (var i = 0; i < this.subheaps.length; i++) {
if (this.subheaps[i].contains(h))
return true;
}
return false;
};
PairingHeap.prototype.isHeap = function (lessThan) {
var _this = this;
return this.subheaps.every(function (h) { return lessThan(_this.elem, h.elem) && h.isHeap(lessThan); });
};
PairingHeap.prototype.insert = function (obj, lessThan) {
return this.merge(new PairingHeap(obj), lessThan);
};
PairingHeap.prototype.merge = function (heap2, lessThan) {
if (this.empty())
return heap2;
else if (heap2.empty())
return this;
else if (lessThan(this.elem, heap2.elem)) {
this.subheaps.push(heap2);
return this;
}
else {
heap2.subheaps.push(this);
return heap2;
}
};
PairingHeap.prototype.removeMin = function (lessThan) {
if (this.empty())
return null;
else
return this.mergePairs(lessThan);
};
PairingHeap.prototype.mergePairs = function (lessThan) {
if (this.subheaps.length == 0)
return new PairingHeap(null);
else if (this.subheaps.length == 1) {
return this.subheaps[0];
}
else {
var firstPair = this.subheaps.pop().merge(this.subheaps.pop(), lessThan);
var remaining = this.mergePairs(lessThan);
return firstPair.merge(remaining, lessThan);
}
};
PairingHeap.prototype.decreaseKey = function (subheap, newValue, setHeapNode, lessThan) {
var newHeap = subheap.removeMin(lessThan);
//reassign subheap values to preserve tree
subheap.elem = newHeap.elem;
subheap.subheaps = newHeap.subheaps;
if (setHeapNode !== null && newHeap.elem !== null) {
setHeapNode(subheap.elem, subheap);
}
var pairingNode = new PairingHeap(newValue);
if (setHeapNode !== null) {
setHeapNode(newValue, pairingNode);
}
return this.merge(pairingNode, lessThan);
};
return PairingHeap;
})();
/**
* @class PriorityQueue a min priority queue backed by a pairing heap
*/
var PriorityQueue = (function () {
function PriorityQueue(lessThan) {
this.lessThan = lessThan;
}
/**
* @method top
* @return the top element (the min element as defined by lessThan)
*/
PriorityQueue.prototype.top = function () {
if (this.empty()) {
return null;
}
return this.root.elem;
};
/**
* @method push
* put things on the heap
*/
PriorityQueue.prototype.push = function () {
var args = [];
for (var _i = 0; _i < arguments.length; _i++) {
args[_i - 0] = arguments[_i];
}
var pairingNode;
for (var i = 0, arg; arg = args[i]; ++i) {
pairingNode = new PairingHeap(arg);
this.root = this.empty() ?
pairingNode : this.root.merge(pairingNode, this.lessThan);
}
return pairingNode;
};
/**
* @method empty
* @return true if no more elements in queue
*/
PriorityQueue.prototype.empty = function () {
return !this.root || !this.root.elem;
};
/**
* @method isHeap check heap condition (for testing)
* @return true if queue is in valid state
*/
PriorityQueue.prototype.isHeap = function () {
return this.root.isHeap(this.lessThan);
};
/**
* @method forEach apply f to each element of the queue
* @param f function to apply
*/
PriorityQueue.prototype.forEach = function (f) {
this.root.forEach(f);
};
/**
* @method pop remove and return the min element from the queue
*/
PriorityQueue.prototype.pop = function () {
if (this.empty()) {
return null;
}
var obj = this.root.min();
this.root = this.root.removeMin(this.lessThan);
return obj;
};
/**
* @method reduceKey reduce the key value of the specified heap node
*/
PriorityQueue.prototype.reduceKey = function (heapNode, newKey, setHeapNode) {
if (setHeapNode === void 0) { setHeapNode = null; }
this.root = this.root.decreaseKey(heapNode, newKey, setHeapNode, this.lessThan);
};
PriorityQueue.prototype.toString = function (selector) {
return this.root.toString(selector);
};
/**
* @method count
* @return number of elements in queue
*/
PriorityQueue.prototype.count = function () {
return this.root.count();
};
return PriorityQueue;
})();
///<reference path="pqueue.ts"/>
/**
* @module shortestpaths
*/
var cola;
(function (cola) {
var shortestpaths;
(function (shortestpaths) {
var Neighbour = (function () {
function Neighbour(id, distance) {
this.id = id;
this.distance = distance;
}
return Neighbour;
})();
var Node = (function () {
function Node(id) {
this.id = id;
this.neighbours = [];
}
return Node;
})();
var QueueEntry = (function () {
function QueueEntry(node, prev, d) {
this.node = node;
this.prev = prev;
this.d = d;
}
return QueueEntry;
})();
/**
* calculates all-pairs shortest paths or shortest paths from a single node
* @class Calculator
* @constructor
* @param n {number} number of nodes
* @param es {Edge[]} array of edges
*/
var Calculator = (function () {
function Calculator(n, es, getSourceIndex, getTargetIndex, getLength) {
this.n = n;
this.es = es;
this.neighbours = new Array(this.n);
var i = this.n;
while (i--)
this.neighbours[i] = new Node(i);
i = this.es.length;
while (i--) {
var e = this.es[i];
var u = getSourceIndex(e), v = getTargetIndex(e);
var d = getLength(e);
this.neighbours[u].neighbours.push(new Neighbour(v, d));
this.neighbours[v].neighbours.push(new Neighbour(u, d));
}
}
/**
* compute shortest paths for graph over n nodes with edges an array of source/target pairs
* edges may optionally have a length attribute. 1 is the default.
* Uses Johnson's algorithm.
*
* @method DistanceMatrix
* @return the distance matrix
*/
Calculator.prototype.DistanceMatrix = function () {
var D = new Array(this.n);
for (var i = 0; i < this.n; ++i) {
D[i] = this.dijkstraNeighbours(i);
}
return D;
};
/**
* get shortest paths from a specified start node
* @method DistancesFromNode
* @param start node index
* @return array of path lengths
*/
Calculator.prototype.DistancesFromNode = function (start) {
return this.dijkstraNeighbours(start);
};
Calculator.prototype.PathFromNodeToNode = function (start, end) {
return this.dijkstraNeighbours(start, end);
};
// find shortest path from start to end, with the opportunity at
// each edge traversal to compute a custom cost based on the
// previous edge. For example, to penalise bends.
Calculator.prototype.PathFromNodeToNodeWithPrevCost = function (start, end, prevCost) {
var q = new PriorityQueue(function (a, b) { return a.d <= b.d; }), u = this.neighbours[start], qu = new QueueEntry(u, null, 0), visitedFrom = {};
q.push(qu);
while (!q.empty()) {
qu = q.pop();
u = qu.node;
if (u.id === end) {
break;
}
var i = u.neighbours.length;
while (i--) {
var neighbour = u.neighbours[i], v = this.neighbours[neighbour.id];
// don't double back
if (qu.prev && v.id === qu.prev.node.id)
continue;
// don't retraverse an edge if it has already been explored
// from a lower cost route
var viduid = v.id + ',' + u.id;
if (viduid in visitedFrom && visitedFrom[viduid] <= qu.d)
continue;
var cc = qu.prev ? prevCost(qu.prev.node.id, u.id, v.id) : 0, t = qu.d + neighbour.distance + cc;
// store cost of this traversal
visitedFrom[viduid] = t;
q.push(new QueueEntry(v, qu, t));
}
}
var path = [];
while (qu.prev) {
qu = qu.prev;
path.push(qu.node.id);
}
return path;
};
Calculator.prototype.dijkstraNeighbours = function (start, dest) {
if (dest === void 0) { dest = -1; }
var q = new PriorityQueue(function (a, b) { return a.d <= b.d; }), i = this.neighbours.length, d = new Array(i);
while (i--) {
var node = this.neighbours[i];
node.d = i === start ? 0 : Number.POSITIVE_INFINITY;
node.q = q.push(node);
}
while (!q.empty()) {
// console.log(q.toString(function (u) { return u.id + "=" + (u.d === Number.POSITIVE_INFINITY ? "\u221E" : u.d.toFixed(2) )}));
var u = q.pop();
d[u.id] = u.d;
if (u.id === dest) {
var path = [];
var v = u;
while (typeof v.prev !== 'undefined') {
path.push(v.prev.id);
v = v.prev;
}
return path;
}
i = u.neighbours.length;
while (i--) {
var neighbour = u.neighbours[i];
var v = this.neighbours[neighbour.id];
var t = u.d + neighbour.distance;
if (u.d !== Number.MAX_VALUE && v.d > t) {
v.d = t;
v.prev = u;
q.reduceKey(v.q, v, function (e, q) { return e.q = q; });
}
}
}
return d;
};
return Calculator;
})();
shortestpaths.Calculator = Calculator;
})(shortestpaths = cola.shortestpaths || (cola.shortestpaths = {}));
})(cola || (cola = {}));
///<reference path="handledisconnected.ts"/>
///<reference path="geom.ts"/>
///<reference path="descent.ts"/>
///<reference path="powergraph.ts"/>
///<reference path="linklengths.ts"/>
///<reference path="shortestpaths.ts"/>
/**
* @module cola
*/
var cola;
(function (cola) {
/**
* The layout process fires three events:
* - start: layout iterations started
* - tick: fired once per iteration, listen to this to animate
* - end: layout converged, you might like to zoom-to-fit or something at notification of this event
*/
(function (EventType) {
EventType[EventType["start"] = 0] = "start";
EventType[EventType["tick"] = 1] = "tick";
EventType[EventType["end"] = 2] = "end";
})(cola.EventType || (cola.EventType = {}));
var EventType = cola.EventType;
;
/**
* Main interface to cola layout.
* @class Layout
*/
var Layout = (function () {
function Layout() {
var _this = this;
this._canvasSize = [1, 1];
this._linkDistance = 20;
this._defaultNodeSize = 10;
this._linkLengthCalculator = null;
this._linkType = null;
this._avoidOverlaps = false;
this._handleDisconnected = true;
this._running = false;
this._nodes = [];
this._groups = [];
this._variables = [];
this._rootGroup = null;
this._links = [];
this._constraints = [];
this._distanceMatrix = null;
this._descent = null;
this._directedLinkConstraints = null;
this._threshold = 0.01;
this._visibilityGraph = null;
this._groupCompactness = 1e-6;
// sub-class and override this property to replace with a more sophisticated eventing mechanism
this.event = null;
this.linkAccessor = {
getSourceIndex: Layout.getSourceIndex, getTargetIndex: Layout.getTargetIndex, setLength: Layout.setLinkLength,
getType: function (l) { return typeof _this._linkType === "function" ? _this._linkType(l) : 0; }
};
}
// subscribe a listener to an event
// sub-class and override this method to replace with a more sophisticated eventing mechanism
Layout.prototype.on = function (e, listener) {
// override me!
if (!this.event)
this.event = {};
if (typeof e === 'string') {
this.event[EventType[e]] = listener;
}
else {
this.event[e] = listener;
}
return this;
};
// a function that is notified of events like "tick"
// sub-class and override this method to replace with a more sophisticated eventing mechanism
Layout.prototype.trigger = function (e) {
if (this.event && typeof this.event[e.type] !== 'undefined') {
this.event[e.type](e);
}
};
// a function that kicks off the iteration tick loop
// it calls tick() repeatedly until tick returns true (is converged)
// subclass and override it with something fancier (e.g. dispatch tick on a timer)
Layout.prototype.kick = function () {
while (!this.tick())
;
};
/**
* iterate the layout. Returns true when layout converged.
*/
Layout.prototype.tick = function () {
if (this._alpha < this._threshold) {
this._running = false;
this.trigger({ type: EventType.end, alpha: this._alpha = 0, stress: this._lastStress });
return true;
}
var n = this._nodes.length, m = this._links.length;
var o, i;
this._descent.locks.clear();
for (i = 0; i < n; ++i) {
o = this._nodes[i];
if (o.fixed) {
if (typeof o.px === 'undefined' || typeof o.py === 'undefined') {
o.px = o.x;
o.py = o.y;
}
var p = [o.px, o.py];
this._descent.locks.add(i, p);
}
}
var s1 = this._descent.rungeKutta();
//var s1 = descent.reduceStress();
if (s1 === 0) {
this._alpha = 0;
}
else if (typeof this._lastStress !== 'undefined') {
this._alpha = s1; //Math.abs(Math.abs(this._lastStress / s1) - 1);
}
this._lastStress = s1;
var x = this._descent.x[0], y = this._descent.x[1];
for (i = 0; i < n; ++i) {
o = this._nodes[i];
o.x = x[i];
o.y = y[i];
}
this.trigger({ type: EventType.tick, alpha: this._alpha, stress: this._lastStress });
return false;
};
Layout.prototype.nodes = function (v) {
if (!v) {
if (this._nodes.length === 0 && this._links.length > 0) {
// if we have links but no nodes, create the nodes array now with empty objects for the links to point at.
var n = 0;
this._links.forEach(function (l) {
n = Math.max(n, l.source, l.target);
});
this._nodes = new Array(++n);
for (var i = 0; i < n; ++i) {
this._nodes[i] = {};
}
}
return this._nodes;
}
this._nodes = v;
return this;
};
Layout.prototype.groups = function (x) {
var _this = this;
if (!x)
return this._groups;
this._groups = x;
this._rootGroup = {};
this._groups.forEach(function (g) {
if (typeof g.padding === "undefined")
g.padding = 1;
if (typeof g.leaves !== "undefined")
g.leaves.forEach(function (v, i) { (g.leaves[i] = _this._nodes[v]).parent = g; });
if (typeof g.groups !== "undefined")
g.groups.forEach(function (gi, i) { (g.groups[i] = _this._groups[gi]).parent = g; });
});
this._rootGroup.leaves = this._nodes.filter(function (v) { return typeof v.parent === 'undefined'; });
this._rootGroup.groups = this._groups.filter(function (g) { return typeof g.parent === 'undefined'; });
return this;
};
Layout.prototype.powerGraphGroups = function (f) {
var g = cola.powergraph.getGroups(this._nodes, this._links, this.linkAccessor, this._rootGroup);
this.groups(g.groups);
f(g);
return this;
};
Layout.prototype.avoidOverlaps = function (v) {
if (!arguments.length)
return this._avoidOverlaps;
this._avoidOverlaps = v;
return this;
};
Layout.prototype.handleDisconnected = function (v) {
if (!arguments.length)
return this._handleDisconnected;
this._handleDisconnected = v;
return this;
};
/**
* causes constraints to be generated such that directed graphs are laid out either from left-to-right or top-to-bottom.
* a separation constraint is generated in the selected axis for each edge that is not involved in a cycle (part of a strongly connected component)
* @param axis {string} 'x' for left-to-right, 'y' for top-to-bottom
* @param minSeparation {number|link=>number} either a number specifying a minimum spacing required across all links or a function to return the minimum spacing for each link
*/
Layout.prototype.flowLayout = function (axis, minSeparation) {
if (!arguments.length)
axis = 'y';
this._directedLinkConstraints = {
axis: axis,
getMinSeparation: typeof minSeparation === 'number' ? function () { return minSeparation; } : minSeparation
};
return this;
};
Layout.prototype.links = function (x) {
if (!arguments.length)
return this._links;
this._links = x;
return this;
};
Layout.prototype.constraints = function (c) {
if (!arguments.length)
return this._constraints;
this._constraints = c;
return this;
};
Layout.prototype.distanceMatrix = function (d) {
if (!arguments.length)
return this._distanceMatrix;
this._distanceMatrix = d;
return this;
};
Layout.prototype.size = function (x) {
if (!x)
return this._canvasSize;
this._canvasSize = x;
return this;
};
Layout.prototype.defaultNodeSize = function (x) {
if (!x)
return this._defaultNodeSize;
this._defaultNodeSize = x;
return this;
};
Layout.prototype.groupCompactness = function (x) {
if (!x)
return this._groupCompactness;
this._groupCompactness = x;
return this;
};
Layout.prototype.linkDistance = function (x) {
if (!x) {
return this._linkDistance;
}
this._linkDistance = typeof x === "function" ? x : +x;
this._linkLengthCalculator = null;
return this;
};
Layout.prototype.linkType = function (f) {
this._linkType = f;
return this;
};
Layout.prototype.convergenceThreshold = function (x) {
if (!x)
return this._threshold;
this._threshold = typeof x === "function" ? x : +x;
return this;
};
Layout.prototype.alpha = function (x) {
if (!arguments.length)
return this._alpha;
else {
x = +x;
if (this._alpha) {
if (x > 0)
this._alpha = x; // we might keep it hot
else
this._alpha = 0; // or, next tick will dispatch "end"
}
else if (x > 0) {
if (!this._running) {
this._running = true;
this.trigger({ type: EventType.start, alpha: this._alpha = x });
this.kick();
}
}
return this;
}
};
Layout.prototype.getLinkLength = function (link) {
return typeof this._linkDistance === "function" ? +(this._linkDistance(link)) : this._linkDistance;
};
Layout.setLinkLength = function (link, length) {
link.length = length;
};
Layout.prototype.getLinkType = function (link) {
return typeof this._linkType === "function" ? this._linkType(link) : 0;
};
/**
* compute an ideal length for each link based on the graph structure around that link.
* you can use this (for example) to create extra space around hub-nodes in dense graphs.
* In particular this calculation is based on the "symmetric difference" in the neighbour sets of the source and target:
* i.e. if neighbours of source is a and neighbours of target are b then calculation is: sqrt(|a union b| - |a intersection b|)
* Actual computation based on inspection of link structure occurs in start(), so links themselves
* don't have to have been assigned before invoking this function.
* @param {number} [idealLength] the base length for an edge when its source and start have no other common neighbours (e.g. 40)
* @param {number} [w] a multiplier for the effect of the length adjustment (e.g. 0.7)
*/
Layout.prototype.symmetricDiffLinkLengths = function (idealLength, w) {
var _this = this;
if (w === void 0) { w = 1; }
this.linkDistance(function (l) { return idealLength * l.length; });
this._linkLengthCalculator = function () { return cola.symmetricDiffLinkLengths(_this._links, _this.linkAccessor, w); };
return this;
};
/**
* compute an ideal length for each link based on the graph structure around that link.
* you can use this (for example) to create extra space around hub-nodes in dense graphs.
* In particular this calculation is based on the "symmetric difference" in the neighbour sets of the source and target:
* i.e. if neighbours of source is a and neighbours of target are b then calculation is: |a intersection b|/|a union b|
* Actual computation based on inspection of link structure occurs in start(), so links themselves
* don't have to have been assigned before invoking this function.
* @param {number} [idealLength] the base length for an edge when its source and start have no other common neighbours (e.g. 40)
* @param {number} [w] a multiplier for the effect of the length adjustment (e.g. 0.7)
*/
Layout.prototype.jaccardLinkLengths = function (idealLength, w) {
var _this = this;
if (w === void 0) { w = 1; }
this.linkDistance(function (l) { return idealLength * l.length; });
this._linkLengthCalculator = function () { return cola.jaccardLinkLengths(_this._links, _this.linkAccessor, w); };
return this;
};
/**
* start the layout process
* @method start
* @param {number} [initialUnconstrainedIterations=0] unconstrained initial layout iterations
* @param {number} [initialUserConstraintIterations=0] initial layout iterations with user-specified constraints
* @param {number} [initialAllConstraintsIterations=0] initial layout iterations with all constraints including non-overlap
* @param {number} [gridSnapIterations=0] iterations of "grid snap", which pulls nodes towards grid cell centers - grid of size node[0].width - only really makes sense if all nodes have the same width and height
*/
Layout.prototype.start = function (initialUnconstrainedIterations, initialUserConstraintIterations, initialAllConstraintsIterations, gridSnapIterations) {
var _this = this;
if (initialUnconstrainedIterations === void 0) { initialUnconstrainedIterations = 0; }
if (initialUserConstraintIterations === void 0) { initialUserConstraintIterations = 0; }
if (initialAllConstraintsIterations === void 0) { initialAllConstraintsIterations = 0; }
if (gridSnapIterations === void 0) { gridSnapIterations = 0; }
var i, j, n = this.nodes().length, N = n + 2 * this._groups.length, m = this._links.length, w = this._canvasSize[0], h = this._canvasSize[1];
if (this._linkLengthCalculator)
this._linkLengthCalculator();
var x = new Array(N), y = new Array(N);
this._variables = new Array(N);
var makeVariable = function (i, w) { return _this._variables[i] = new cola.vpsc.IndexedVariable(i, w); };
var G = null;
var ao = this._avoidOverlaps;
this._nodes.forEach(function (v, i) {
v.index = i;
if (typeof v.x === 'undefined') {
v.x = w / 2, v.y = h / 2;
}
x[i] = v.x, y[i] = v.y;
});
//should we do this to clearly label groups?
//this._groups.forEach((g, i) => g.groupIndex = i);
var distances;
if (this._distanceMatrix) {
// use the user specified distanceMatrix
distances = this._distanceMatrix;
}
else {
// construct an n X n distance matrix based on shortest paths through graph (with respect to edge.length).
distances = (new cola.shortestpaths.Calculator(N, this._links, Layout.getSourceIndex, Layout.getTargetIndex, function (l) { return _this.getLinkLength(l); })).DistanceMatrix();
// G is a square matrix with G[i][j] = 1 iff there exists an edge between node i and node j
// otherwise 2. (
G = cola.Descent.createSquareMatrix(N, function () { return 2; });
this._links.forEach(function (e) {
var u = Layout.getSourceIndex(e), v = Layout.getTargetIndex(e);
G[u][v] = G[v][u] = 1;
});
}
var D = cola.Descent.createSquareMatrix(N, function (i, j) {
return distances[i][j];
});
if (this._rootGroup && typeof this._rootGroup.groups !== 'undefined') {
var i = n;
var addAttraction = function (i, j, strength, idealDistance) {
G[i][j] = G[j][i] = strength;
D[i][j] = D[j][i] = idealDistance;
};
this._groups.forEach(function (g) {
addAttraction(i, i + 1, _this._groupCompactness, 0.1);
// todo: add terms here attracting children of the group to the group dummy nodes
//if (typeof g.leaves !== 'undefined')
// g.leaves.forEach(l => {
// addAttraction(l.index, i, 1e-4, 0.1);
// addAttraction(l.index, i + 1, 1e-4, 0.1);
// });
//if (typeof g.groups !== 'undefined')
// g.groups.forEach(g => {
// var gid = n + g.groupIndex * 2;
// addAttraction(gid, i, 0.1, 0.1);
// addAttraction(gid + 1, i, 0.1, 0.1);
// addAttraction(gid, i + 1, 0.1, 0.1);
// addAttraction(gid + 1, i + 1, 0.1, 0.1);
// });
x[i] = 0, y[i++] = 0;
x[i] = 0, y[i++] = 0;
});
}
else
this._rootGroup = { leaves: this._nodes, groups: [] };
var curConstraints = this._constraints || [];
if (this._directedLinkConstraints) {
this.linkAccessor.getMinSeparation = this._directedLinkConstraints.getMinSeparation;
curConstraints = curConstraints.concat(cola.generateDirectedEdgeConstraints(n, this._links, this._directedLinkConstraints.axis, (this.linkAccessor)));
}
this.avoidOverlaps(false);
this._descent = new cola.Descent([x, y], D);
this._descent.locks.clear();
for (var i = 0; i < n; ++i) {
var o = this._nodes[i];
if (o.fixed) {
o.px = o.x;
o.py = o.y;
var p = [o.x, o.y];
this._descent.locks.add(i, p);
}
}
this._descent.threshold = this._threshold;
// apply initialIterations without user constraints or nonoverlap constraints
this._descent.run(initialUnconstrainedIterations);
// apply initialIterations with user constraints but no nonoverlap constraints
if (curConstraints.length > 0)
this._descent.project = new cola.vpsc.Projection(this._nodes, this._groups, this._rootGroup, curConstraints).projectFunctions();
this._descent.run(initialUserConstraintIterations);
// subsequent iterations will apply all constraints
this.avoidOverlaps(ao);
if (ao) {
this._nodes.forEach(function (v, i) { v.x = x[i], v.y = y[i]; });
this._descent.project = new cola.vpsc.Projection(this._nodes, this._groups, this._rootGroup, curConstraints, true).projectFunctions();
this._nodes.forEach(function (v, i) { x[i] = v.x, y[i] = v.y; });
}
// allow not immediately connected nodes to relax apart (p-stress)
this._descent.G = G;
this._descent.run(initialAllConstraintsIterations);
if (gridSnapIterations) {
this._descent.snapStrength = 1000;
this._descent.snapGridSize = this._nodes[0].width;
this._descent.numGridSnapNodes = n;
this._descent.scaleSnapByMaxH = n != N; // if we have groups then need to scale hessian so grid forces still apply
var G0 = cola.Descent.createSquareMatrix(N, function (i, j) {
if (i >= n || j >= n)
return G[i][j];
return 0;
});
this._descent.G = G0;
this._descent.run(gridSnapIterations);
}
this._links.forEach(function (l) {
if (typeof l.source == "number")
l.source = _this._nodes[l.source];
if (typeof l.target == "number")
l.target = _this._nodes[l.target];
});
this._nodes.forEach(function (v, i) {
v.x = x[i], v.y = y[i];
});
// recalculate nodes position for disconnected graphs
if (!this._distanceMatrix && this._handleDisconnected) {
var graphs = cola.separateGraphs(this._nodes, this._links);
cola.applyPacking(graphs, w, h, this._defaultNodeSize);
this._nodes.forEach(function (v, i) {
_this._descent.x[0][i] = v.x, _this._descent.x[1][i] = v.y;
});
}
return this.resume();
};
Layout.prototype.resume = function () {
return this.alpha(0.1);
};
Layout.prototype.stop = function () {
return this.alpha(0);
};
Layout.prototype.prepareEdgeRouting = function (nodeMargin) {
if (nodeMargin === void 0) { nodeMargin = 0; }
this._visibilityGraph = new cola.geom.TangentVisibilityGraph(this._nodes.map(function (v) {
return v.bounds.inflate(-nodeMargin).vertices();
}));
};
Layout.prototype.routeEdge = function (d, draw) {
var lineData = [];
//if (d.source.id === 10 && d.target.id === 11) {
// debugger;
//}
var vg2 = new cola.geom.TangentVisibilityGraph(this._visibilityGraph.P, { V: this._visibilityGraph.V, E: this._visibilityGraph.E }), port1 = { x: d.source.x, y: d.source.y }, port2 = { x: d.target.x, y: d.target.y }, start = vg2.addPoint(port1, d.source.id), end = vg2.addPoint(port2, d.target.id);
vg2.addEdgeIfVisible(port1, port2, d.source.id, d.target.id);
if (typeof draw !== 'undefined') {
draw(vg2);
}
var sourceInd = function (e) { return e.source.id; }, targetInd = function (e) { return e.target.id; }, length = function (e) { return e.length(); }, spCalc = new cola.shortestpaths.Calculator(vg2.V.length, vg2.E, sourceInd, targetInd, length), shortestPath = spCalc.PathFromNodeToNode(start.id, end.id);
if (shortestPath.length === 1 || shortestPath.length === vg2.V.length) {
cola.vpsc.makeEdgeBetween(d, d.source.innerBounds, d.target.innerBounds, 5);
lineData = [{ x: d.sourceIntersection.x, y: d.sourceIntersection.y }, { x: d.arrowStart.x, y: d.arrowStart.y }];
}
else {
var n = shortestPath.length - 2, p = vg2.V[shortestPath[n]].p, q = vg2.V[shortestPath[0]].p, lineData = [d.source.innerBounds.rayIntersection(p.x, p.y)];
for (var i = n; i >= 0; --i)
lineData.push(vg2.V[shortestPath[i]].p);
lineData.push(cola.vpsc.makeEdgeTo(q, d.target.innerBounds, 5));
}
//lineData.forEach((v, i) => {
// if (i > 0) {
// var u = lineData[i - 1];
// this._nodes.forEach(function (node) {
// if (node.id === getSourceIndex(d) || node.id === getTargetIndex(d)) return;
// var ints = node.innerBounds.lineIntersections(u.x, u.y, v.x, v.y);
// if (ints.length > 0) {
// debugger;
// }
// })
// }
//})
return lineData;
};
//The link source and target may be just a node index, or they may be references to nodes themselves.
Layout.getSourceIndex = function (e) {
return typeof e.source === 'number' ? e.source : e.source.index;
};
//The link source and target may be just a node index, or they may be references to nodes themselves.
Layout.getTargetIndex = function (e) {
return typeof e.target === 'number' ? e.target : e.target.index;
};
// Get a string ID for a given link.
Layout.linkId = function (e) {
return Layout.getSourceIndex(e) + "-" + Layout.getTargetIndex(e);
};
// The fixed property has three bits:
// Bit 1 can be set externally (e.g., d.fixed = true) and show persist.
// Bit 2 stores the dragging state, from mousedown to mouseup.
// Bit 3 stores the hover state, from mouseover to mouseout.
// Dragend is a special case: it also clears the hover state.
Layout.dragStart = function (d) {
d.fixed |= 2; // set bit 2
d.px = d.x, d.py = d.y; // set velocity to zero
};
Layout.dragEnd = function (d) {
d.fixed &= ~6; // unset bits 2 and 3
//d.fixed = 0;
};
Layout.mouseOver = function (d) {
d.fixed |= 4; // set bit 3
d.px = d.x, d.py = d.y; // set velocity to zero
};
Layout.mouseOut = function (d) {
d.fixed &= ~4; // unset bit 3
};
return Layout;
})();
cola.Layout = Layout;
})(cola || (cola = {}));
///<reference path="../extern/d3.d.ts"/>
///<reference path="layout.ts"/>
var cola;
(function (cola) {
var D3StyleLayoutAdaptor = (function (_super) {
__extends(D3StyleLayoutAdaptor, _super);
function D3StyleLayoutAdaptor() {
_super.call(this);
this.event = d3.dispatch(cola.EventType[cola.EventType.start], cola.EventType[cola.EventType.tick], cola.EventType[cola.EventType.end]);
// bit of trickyness remapping 'this' so we can reference it in the function body.
var d3layout = this;
this.drag = function () {
var drag = d3.behavior.drag()
.origin(function (d) { return d; })
.on("dragstart.d3adaptor", cola.Layout.dragStart)
.on("drag.d3adaptor", function (d) {
d.px = d3.event.x, d.py = d3.event.y;
d3layout.resume(); // restart annealing
})
.on("dragend.d3adaptor", cola.Layout.dragEnd);
if (!arguments.length)
return drag;
// this is the context of the function, i.e. the d3 selection
this //.on("mouseover.adaptor", colaMouseover)
.call(drag);
};
}
D3StyleLayoutAdaptor.prototype.trigger = function (e) {
var d3event = { type: cola.EventType[e.type], alpha: e.alpha, stress: e.stress };
this.event[d3event.type](d3event); // via d3 dispatcher, e.g. event.start(e);
};
// iterate layout using a d3.timer, which queues calls to tick repeatedly until tick returns true
D3StyleLayoutAdaptor.prototype.kick = function () {
var _this = this;
d3.timer(function () { return _super.prototype.tick.call(_this); });
};
// a function for binding to events on the adapter
D3StyleLayoutAdaptor.prototype.on = function (eventType, listener) {
if (typeof eventType === 'string') {
this.event.on(eventType, listener);
}
else {
this.event.on(cola.EventType[eventType], listener);
}
return this;
};
return D3StyleLayoutAdaptor;
})(cola.Layout);
cola.D3StyleLayoutAdaptor = D3StyleLayoutAdaptor;
/**
* provides an interface for use with d3:
* - uses the d3 event system to dispatch layout events such as:
* o "start" (start layout process)
* o "tick" (after each layout iteration)
* o "end" (layout converged and complete).
* - uses the d3 timer to queue layout iterations.
* - sets up d3.behavior.drag to drag nodes
* o use `node.call(<the returned instance of Layout>.drag)` to make nodes draggable
* returns an instance of the cola.Layout itself with which the user
* can interact directly.
*/
function d3adaptor() {
return new D3StyleLayoutAdaptor();
}
cola.d3adaptor = d3adaptor;
})(cola || (cola = {}));
/// <reference path="rectangle.ts"/>
/// <reference path="shortestpaths.ts"/>
/// <reference path="geom.ts"/>
/// <reference path="vpsc.ts"/>
var cola;
(function (cola) {
var NodeWrapper = (function () {
function NodeWrapper(id, rect, children) {
this.id = id;
this.rect = rect;
this.children = children;
this.leaf = typeof children === 'undefined' || children.length === 0;
}
return NodeWrapper;
})();
cola.NodeWrapper = NodeWrapper;
var Vert = (function () {
function Vert(id, x, y, node, line) {
if (node === void 0) { node = null; }
if (line === void 0) { line = null; }
this.id = id;
this.x = x;
this.y = y;
this.node = node;
this.line = line;
}
return Vert;
})();
cola.Vert = Vert;
var LongestCommonSubsequence = (function () {
function LongestCommonSubsequence(s, t) {
this.s = s;
this.t = t;
var mf = LongestCommonSubsequence.findMatch(s, t);
var tr = t.slice(0).reverse();
var mr = LongestCommonSubsequence.findMatch(s, tr);
if (mf.length >= mr.length) {
this.length = mf.length;
this.si = mf.si;
this.ti = mf.ti;
this.reversed = false;
}
else {
this.length = mr.length;
this.si = mr.si;
this.ti = t.length - mr.ti - mr.length;
this.reversed = true;
}
}
LongestCommonSubsequence.findMatch = function (s, t) {
var m = s.length;
var n = t.length;
var match = { length: 0, si: -1, ti: -1 };
var l = new Array(m);
for (var i = 0; i < m; i++) {
l[i] = new Array(n);
for (var j = 0; j < n; j++)
if (s[i] === t[j]) {
var v = l[i][j] = (i === 0 || j === 0) ? 1 : l[i - 1][j - 1] + 1;
if (v > match.length) {
match.length = v;
match.si = i - v + 1;
match.ti = j - v + 1;
}
;
}
else
l[i][j] = 0;
}
return match;
};
LongestCommonSubsequence.prototype.getSequence = function () {
return this.length >= 0 ? this.s.slice(this.si, this.si + this.length) : [];
};
return LongestCommonSubsequence;
})();
cola.LongestCommonSubsequence = LongestCommonSubsequence;
var GridRouter = (function () {
function GridRouter(originalnodes, accessor, groupPadding) {
var _this = this;
if (groupPadding === void 0) { groupPadding = 12; }
this.originalnodes = originalnodes;
this.groupPadding = groupPadding;
this.leaves = null;
this.nodes = originalnodes.map(function (v, i) { return new NodeWrapper(i, accessor.getBounds(v), accessor.getChildren(v)); });
this.leaves = this.nodes.filter(function (v) { return v.leaf; });
this.groups = this.nodes.filter(function (g) { return !g.leaf; });
this.cols = this.getGridDim('x');
this.rows = this.getGridDim('y');
// create parents for each node or group that is a member of another's children
this.groups.forEach(function (v) {
return v.children.forEach(function (c) { return _this.nodes[c].parent = v; });
});
// root claims the remaining orphans
this.root = { children: [] };
this.nodes.forEach(function (v) {
if (typeof v.parent === 'undefined') {
v.parent = _this.root;
_this.root.children.push(v.id);
}
// each node will have grid vertices associated with it,
// some inside the node and some on the boundary
// leaf nodes will have exactly one internal node at the center
// and four boundary nodes
// groups will have potentially many of each
v.ports = [];
});
// nodes ordered by their position in the group hierarchy
this.backToFront = this.nodes.slice(0);
this.backToFront.sort(function (x, y) { return _this.getDepth(x) - _this.getDepth(y); });
// compute boundary rectangles for each group
// has to be done from front to back, i.e. inside groups to outside groups
// such that each can be made large enough to enclose its interior
var frontToBackGroups = this.backToFront.slice(0).reverse().filter(function (g) { return !g.leaf; });
frontToBackGroups.forEach(function (v) {
var r = cola.vpsc.Rectangle.empty();
v.children.forEach(function (c) { return r = r.union(_this.nodes[c].rect); });
v.rect = r.inflate(_this.groupPadding);
});
var colMids = this.midPoints(this.cols.map(function (r) { return r.x; }));
var rowMids = this.midPoints(this.rows.map(function (r) { return r.y; }));
// setup extents of lines
var rowx = colMids[0], rowX = colMids[colMids.length - 1];
var coly = rowMids[0], colY = rowMids[rowMids.length - 1];
// horizontal lines
var hlines = this.rows.map(function (r) { return { x1: rowx, x2: rowX, y1: r.y, y2: r.y }; })
.concat(rowMids.map(function (m) { return { x1: rowx, x2: rowX, y1: m, y2: m }; }));
// vertical lines
var vlines = this.cols.map(function (c) { return { x1: c.x, x2: c.x, y1: coly, y2: colY }; })
.concat(colMids.map(function (m) { return { x1: m, x2: m, y1: coly, y2: colY }; }));
// the full set of lines
var lines = hlines.concat(vlines);
// we record the vertices associated with each line
lines.forEach(function (l) { return l.verts = []; });
// the routing graph
this.verts = [];
this.edges = [];
// create vertices at the crossings of horizontal and vertical grid-lines
hlines.forEach(function (h) {
return vlines.forEach(function (v) {
var p = new Vert(_this.verts.length, v.x1, h.y1);
h.verts.push(p);
v.verts.push(p);
_this.verts.push(p);
// assign vertices to the nodes immediately under them
var i = _this.backToFront.length;
while (i-- > 0) {
var node = _this.backToFront[i], r = node.rect;
var dx = Math.abs(p.x - r.cx()), dy = Math.abs(p.y - r.cy());
if (dx < r.width() / 2 && dy < r.height() / 2) {
p.node = node;
break;
}
}
});
});
lines.forEach(function (l, li) {
// create vertices at the intersections of nodes and lines
_this.nodes.forEach(function (v, i) {
v.rect.lineIntersections(l.x1, l.y1, l.x2, l.y2).forEach(function (intersect, j) {
//console.log(li+','+i+','+j+':'+intersect.x + ',' + intersect.y);
var p = new Vert(_this.verts.length, intersect.x, intersect.y, v, l);
_this.verts.push(p);
l.verts.push(p);
v.ports.push(p);
});
});
// split lines into edges joining vertices
var isHoriz = Math.abs(l.y1 - l.y2) < 0.1;
var delta = function (a, b) { return isHoriz ? b.x - a.x : b.y - a.y; };
l.verts.sort(delta);
for (var i = 1; i < l.verts.length; i++) {
var u = l.verts[i - 1], v = l.verts[i];
if (u.node && u.node === v.node && u.node.leaf)
continue;
_this.edges.push({ source: u.id, target: v.id, length: Math.abs(delta(u, v)) });
}
});
}
GridRouter.prototype.avg = function (a) { return a.reduce(function (x, y) { return x + y; }) / a.length; };
GridRouter.prototype.getGridDim = function (axis) {
var columns = [];
var ls = this.leaves.slice(0, this.leaves.length);
while (ls.length > 0) {
var r = ls[0].rect;
var col = ls.filter(function (v) { return v.rect['overlap' + axis.toUpperCase()](r); });
columns.push(col);
col.forEach(function (v) { return ls.splice(ls.indexOf(v), 1); });
col[axis] = this.avg(col.map(function (v) { return v.rect['c' + axis](); }));
}
columns.sort(function (x, y) { return x[axis] - y[axis]; });
return columns;
};
// get the depth of the given node in the group hierarchy
GridRouter.prototype.getDepth = function (v) {
var depth = 0;
while (v.parent !== this.root) {
depth++;
v = v.parent;
}
return depth;
};
// medial axes between node centres and also boundary lines for the grid
GridRouter.prototype.midPoints = function (a) {
var gap = a[1] - a[0];
var mids = [a[0] - gap / 2];
for (var i = 1; i < a.length; i++) {
mids.push((a[i] + a[i - 1]) / 2);
}
mids.push(a[a.length - 1] + gap / 2);
return mids;
};
// find path from v to root including both v and root
GridRouter.prototype.findLineage = function (v) {
var lineage = [v];
do {
v = v.parent;
lineage.push(v);
} while (v !== this.root);
return lineage.reverse();
};
// find path connecting a and b through their lowest common ancestor
GridRouter.prototype.findAncestorPathBetween = function (a, b) {
var aa = this.findLineage(a), ba = this.findLineage(b), i = 0;
while (aa[i] === ba[i])
i++;
// i-1 to include common ancestor only once (as first element)
return { commonAncestor: aa[i - 1], lineages: aa.slice(i).concat(ba.slice(i)) };
};
// when finding a path between two nodes a and b, siblings of a and b on the
// paths from a and b to their least common ancestor are obstacles
GridRouter.prototype.siblingObstacles = function (a, b) {
var _this = this;
var path = this.findAncestorPathBetween(a, b);
var lineageLookup = {};
path.lineages.forEach(function (v) { return lineageLookup[v.id] = {}; });
var obstacles = path.commonAncestor.children.filter(function (v) { return !(v in lineageLookup); });
path.lineages
.filter(function (v) { return v.parent !== path.commonAncestor; })
.forEach(function (v) { return obstacles = obstacles.concat(v.parent.children.filter(function (c) { return c !== v.id; })); });
return obstacles.map(function (v) { return _this.nodes[v]; });
};
// for the given routes, extract all the segments orthogonal to the axis x
// and return all them grouped by x position
GridRouter.getSegmentSets = function (routes, x, y) {
// vsegments is a list of vertical segments sorted by x position
var vsegments = [];
for (var ei = 0; ei < routes.length; ei++) {
var route = routes[ei];
for (var si = 0; si < route.length; si++) {
var s = route[si];
s.edgeid = ei;
s.i = si;
var sdx = s[1][x] - s[0][x];
if (Math.abs(sdx) < 0.1) {
vsegments.push(s);
}
}
}
vsegments.sort(function (a, b) { return a[0][x] - b[0][x]; });
// vsegmentsets is a set of sets of segments grouped by x position
var vsegmentsets = [];
var segmentset = null;
for (var i = 0; i < vsegments.length; i++) {
var s = vsegments[i];
if (!segmentset || Math.abs(s[0][x] - segmentset.pos) > 0.1) {
segmentset = { pos: s[0][x], segments: [] };
vsegmentsets.push(segmentset);
}
segmentset.segments.push(s);
}
return vsegmentsets;
};
// for all segments in this bundle create a vpsc problem such that
// each segment's x position is a variable and separation constraints
// are given by the partial order over the edges to which the segments belong
// for each pair s1,s2 of segments in the open set:
// e1 = edge of s1, e2 = edge of s2
// if leftOf(e1,e2) create constraint s1.x + gap <= s2.x
// else if leftOf(e2,e1) create cons. s2.x + gap <= s1.x
GridRouter.nudgeSegs = function (x, y, routes, segments, leftOf, gap) {
var n = segments.length;
if (n <= 1)
return;
var vs = segments.map(function (s) { return new cola.vpsc.Variable(s[0][x]); });
var cs = [];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if (i === j)
continue;
var s1 = segments[i], s2 = segments[j], e1 = s1.edgeid, e2 = s2.edgeid, lind = -1, rind = -1;
// in page coordinates (not cartesian) the notion of 'leftof' is flipped in the horizontal axis from the vertical axis
// that is, when nudging vertical segments, if they increase in the y(conj) direction the segment belonging to the
// 'left' edge actually needs to be nudged to the right
// when nudging horizontal segments, if the segments increase in the x direction
// then the 'left' segment needs to go higher, i.e. to have y pos less than that of the right
if (x == 'x') {
if (leftOf(e1, e2)) {
//console.log('s1: ' + s1[0][x] + ',' + s1[0][y] + '-' + s1[1][x] + ',' + s1[1][y]);
if (s1[0][y] < s1[1][y]) {
lind = j, rind = i;
}
else {
lind = i, rind = j;
}
}
}
else {
if (leftOf(e1, e2)) {
if (s1[0][y] < s1[1][y]) {
lind = i, rind = j;
}
else {
lind = j, rind = i;
}
}
}
if (lind >= 0) {
//console.log(x+' constraint: ' + lind + '<' + rind);
cs.push(new cola.vpsc.Constraint(vs[lind], vs[rind], gap));
}
}
}
var solver = new cola.vpsc.Solver(vs, cs);
solver.solve();
vs.forEach(function (v, i) {
var s = segments[i];
var pos = v.position();
s[0][x] = s[1][x] = pos;
var route = routes[s.edgeid];
if (s.i > 0)
route[s.i - 1][1][x] = pos;
if (s.i < route.length - 1)
route[s.i + 1][0][x] = pos;
});
};
GridRouter.nudgeSegments = function (routes, x, y, leftOf, gap) {
var vsegmentsets = GridRouter.getSegmentSets(routes, x, y);
// scan the grouped (by x) segment sets to find co-linear bundles
for (var i = 0; i < vsegmentsets.length; i++) {
var ss = vsegmentsets[i];
var events = [];
for (var j = 0; j < ss.segments.length; j++) {
var s = ss.segments[j];
events.push({ type: 0, s: s, pos: Math.min(s[0][y], s[1][y]) });
events.push({ type: 1, s: s, pos: Math.max(s[0][y], s[1][y]) });
}
events.sort(function (a, b) { return a.pos - b.pos + a.type - b.type; });
var open = [];
var openCount = 0;
events.forEach(function (e) {
if (e.type === 0) {
open.push(e.s);
openCount++;
}
else {
openCount--;
}
if (openCount == 0) {
GridRouter.nudgeSegs(x, y, routes, open, leftOf, gap);
open = [];
}
});
}
};
// obtain routes for the specified edges, nicely nudged apart
// warning: edge paths may be reversed such that common paths are ordered consistently within bundles!
GridRouter.prototype.routeEdges = function (edges, gap, source, target) {
var _this = this;
var routePaths = edges.map(function (e) { return _this.route(source(e), target(e)); });
var order = cola.GridRouter.orderEdges(routePaths);
var routes = routePaths.map(function (e) { return cola.GridRouter.makeSegments(e); });
cola.GridRouter.nudgeSegments(routes, 'x', 'y', order, gap);
cola.GridRouter.nudgeSegments(routes, 'y', 'x', order, gap);
cola.GridRouter.unreverseEdges(routes, routePaths);
return routes;
};
// path may have been reversed by the subsequence processing in orderEdges
// so now we need to restore the original order
GridRouter.unreverseEdges = function (routes, routePaths) {
routes.forEach(function (segments, i) {
var path = routePaths[i];
if (path.reversed) {
segments.reverse(); // reverse order of segments
segments.forEach(function (segment) {
segment.reverse(); // reverse each segment
});
}
});
};
GridRouter.angleBetween2Lines = function (line1, line2) {
var angle1 = Math.atan2(line1[0].y - line1[1].y, line1[0].x - line1[1].x);
var angle2 = Math.atan2(line2[0].y - line2[1].y, line2[0].x - line2[1].x);
var diff = angle1 - angle2;
if (diff > Math.PI || diff < -Math.PI) {
diff = angle2 - angle1;
}
return diff;
};
// does the path a-b-c describe a left turn?
GridRouter.isLeft = function (a, b, c) {
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) <= 0;
};
// for the given list of ordered pairs, returns a function that (efficiently) looks-up a specific pair to
// see if it exists in the list
GridRouter.getOrder = function (pairs) {
var outgoing = {};
for (var i = 0; i < pairs.length; i++) {
var p = pairs[i];
if (typeof outgoing[p.l] === 'undefined')
outgoing[p.l] = {};
outgoing[p.l][p.r] = true;
}
return function (l, r) { return typeof outgoing[l] !== 'undefined' && outgoing[l][r]; };
};
// returns an ordering (a lookup function) that determines the correct order to nudge the
// edge paths apart to minimize crossings
GridRouter.orderEdges = function (edges) {
var edgeOrder = [];
for (var i = 0; i < edges.length - 1; i++) {
for (var j = i + 1; j < edges.length; j++) {
var e = edges[i], f = edges[j], lcs = new cola.LongestCommonSubsequence(e, f);
var u, vi, vj;
if (lcs.length === 0)
continue; // no common subpath
if (lcs.reversed) {
// if we found a common subpath but one of the edges runs the wrong way,
// then reverse f.
f.reverse();
f.reversed = true;
lcs = new cola.LongestCommonSubsequence(e, f);
}
if ((lcs.si <= 0 || lcs.ti <= 0) &&
(lcs.si + lcs.length >= e.length || lcs.ti + lcs.length >= f.length)) {
// the paths do not diverge, so make an arbitrary ordering decision
edgeOrder.push({ l: i, r: j });
continue;
}
if (lcs.si + lcs.length >= e.length || lcs.ti + lcs.length >= f.length) {
// if the common subsequence of the
// two edges being considered goes all the way to the
// end of one (or both) of the lines then we have to
// base our ordering decision on the other end of the
// common subsequence
u = e[lcs.si + 1];
vj = e[lcs.si - 1];
vi = f[lcs.ti - 1];
}
else {
u = e[lcs.si + lcs.length - 2];
vi = e[lcs.si + lcs.length];
vj = f[lcs.ti + lcs.length];
}
if (GridRouter.isLeft(u, vi, vj)) {
edgeOrder.push({ l: j, r: i });
}
else {
edgeOrder.push({ l: i, r: j });
}
}
}
//edgeOrder.forEach(function (e) { console.log('l:' + e.l + ',r:' + e.r) });
return cola.GridRouter.getOrder(edgeOrder);
};
// for an orthogonal path described by a sequence of points, create a list of segments
// if consecutive segments would make a straight line they are merged into a single segment
// segments are over cloned points, not the original vertices
GridRouter.makeSegments = function (path) {
function copyPoint(p) {
return { x: p.x, y: p.y };
}
var isStraight = function (a, b, c) { return Math.abs((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) < 0.001; };
var segments = [];
var a = copyPoint(path[0]);
for (var i = 1; i < path.length; i++) {
var b = copyPoint(path[i]), c = i < path.length - 1 ? path[i + 1] : null;
if (!c || !isStraight(a, b, c)) {
segments.push([a, b]);
a = b;
}
}
return segments;
};
// find a route between node s and node t
// returns an array of indices to verts
GridRouter.prototype.route = function (s, t) {
var _this = this;
var source = this.nodes[s], target = this.nodes[t];
this.obstacles = this.siblingObstacles(source, target);
var obstacleLookup = {};
this.obstacles.forEach(function (o) { return obstacleLookup[o.id] = o; });
this.passableEdges = this.edges.filter(function (e) {
var u = _this.verts[e.source], v = _this.verts[e.target];
return !(u.node && u.node.id in obstacleLookup
|| v.node && v.node.id in obstacleLookup);
});
// add dummy segments linking ports inside source and target
for (var i = 1; i < source.ports.length; i++) {
var u = source.ports[0].id;
var v = source.ports[i].id;
this.passableEdges.push({
source: u,
target: v,
length: 0
});
}
for (var i = 1; i < target.ports.length; i++) {
var u = target.ports[0].id;
var v = target.ports[i].id;
this.passableEdges.push({
source: u,
target: v,
length: 0
});
}
var getSource = function (e) { return e.source; }, getTarget = function (e) { return e.target; }, getLength = function (e) { return e.length; };
var shortestPathCalculator = new cola.shortestpaths.Calculator(this.verts.length, this.passableEdges, getSource, getTarget, getLength);
var bendPenalty = function (u, v, w) {
var a = _this.verts[u], b = _this.verts[v], c = _this.verts[w];
var dx = Math.abs(c.x - a.x), dy = Math.abs(c.y - a.y);
// don't count bends from internal node edges
if (a.node === source && a.node === b.node || b.node === target && b.node === c.node)
return 0;
return dx > 1 && dy > 1 ? 1000 : 0;
};
// get shortest path
var shortestPath = shortestPathCalculator.PathFromNodeToNodeWithPrevCost(source.ports[0].id, target.ports[0].id, bendPenalty);
// shortest path is reversed and does not include the target port
var pathPoints = shortestPath.reverse().map(function (vi) { return _this.verts[vi]; });
pathPoints.push(this.nodes[target.id].ports[0]);
// filter out any extra end points that are inside the source or target (i.e. the dummy segments above)
return pathPoints.filter(function (v, i) {
return !(i < pathPoints.length - 1 && pathPoints[i + 1].node === source && v.node === source
|| i > 0 && v.node === target && pathPoints[i - 1].node === target);
});
};
GridRouter.getRoutePath = function (route, cornerradius, arrowwidth, arrowheight) {
var result = {
routepath: 'M ' + route[0][0].x + ' ' + route[0][0].y + ' ',
arrowpath: ''
};
if (route.length > 1) {
for (var i = 0; i < route.length; i++) {
var li = route[i];
var x = li[1].x, y = li[1].y;
var dx = x - li[0].x;
var dy = y - li[0].y;
if (i < route.length - 1) {
if (Math.abs(dx) > 0) {
x -= dx / Math.abs(dx) * cornerradius;
}
else {
y -= dy / Math.abs(dy) * cornerradius;
}
result.routepath += 'L ' + x + ' ' + y + ' ';
var l = route[i + 1];
var x0 = l[0].x, y0 = l[0].y;
var x1 = l[1].x;
var y1 = l[1].y;
dx = x1 - x0;
dy = y1 - y0;
var angle = GridRouter.angleBetween2Lines(li, l) < 0 ? 1 : 0;
//console.log(cola.GridRouter.angleBetween2Lines(li, l))
var x2, y2;
if (Math.abs(dx) > 0) {
x2 = x0 + dx / Math.abs(dx) * cornerradius;
y2 = y0;
}
else {
x2 = x0;
y2 = y0 + dy / Math.abs(dy) * cornerradius;
}
var cx = Math.abs(x2 - x);
var cy = Math.abs(y2 - y);
result.routepath += 'A ' + cx + ' ' + cy + ' 0 0 ' + angle + ' ' + x2 + ' ' + y2 + ' ';
}
else {
var arrowtip = [x, y];
var arrowcorner1, arrowcorner2;
if (Math.abs(dx) > 0) {
x -= dx / Math.abs(dx) * arrowheight;
arrowcorner1 = [x, y + arrowwidth];
arrowcorner2 = [x, y - arrowwidth];
}
else {
y -= dy / Math.abs(dy) * arrowheight;
arrowcorner1 = [x + arrowwidth, y];
arrowcorner2 = [x - arrowwidth, y];
}
result.routepath += 'L ' + x + ' ' + y + ' ';
if (arrowheight > 0) {
result.arrowpath = 'M ' + arrowtip[0] + ' ' + arrowtip[1] + ' L ' + arrowcorner1[0] + ' ' + arrowcorner1[1]
+ ' L ' + arrowcorner2[0] + ' ' + arrowcorner2[1];
}
}
}
}
else {
var li = route[0];
var x = li[1].x, y = li[1].y;
var dx = x - li[0].x;
var dy = y - li[0].y;
var arrowtip = [x, y];
var arrowcorner1, arrowcorner2;
if (Math.abs(dx) > 0) {
x -= dx / Math.abs(dx) * arrowheight;
arrowcorner1 = [x, y + arrowwidth];
arrowcorner2 = [x, y - arrowwidth];
}
else {
y -= dy / Math.abs(dy) * arrowheight;
arrowcorner1 = [x + arrowwidth, y];
arrowcorner2 = [x - arrowwidth, y];
}
result.routepath += 'L ' + x + ' ' + y + ' ';
if (arrowheight > 0) {
result.arrowpath = 'M ' + arrowtip[0] + ' ' + arrowtip[1] + ' L ' + arrowcorner1[0] + ' ' + arrowcorner1[1]
+ ' L ' + arrowcorner2[0] + ' ' + arrowcorner2[1];
}
}
return result;
};
return GridRouter;
})();
cola.GridRouter = GridRouter;
})(cola || (cola = {}));
/**
* Use cola to do a layout in 3D!! Yay.
* Pretty simple for the moment.
*/
var cola;
(function (cola) {
var Link3D = (function () {
function Link3D(source, target) {
this.source = source;
this.target = target;
}
Link3D.prototype.actualLength = function (x) {
var _this = this;
return Math.sqrt(x.reduce(function (c, v) {
var dx = v[_this.target] - v[_this.source];
return c + dx * dx;
}, 0));
};
return Link3D;
})();
cola.Link3D = Link3D;
var Node3D = (function () {
function Node3D(x, y, z) {
if (x === void 0) { x = 0; }
if (y === void 0) { y = 0; }
if (z === void 0) { z = 0; }
this.x = x;
this.y = y;
this.z = z;
}
return Node3D;
})();
cola.Node3D = Node3D;
var Layout3D = (function () {
function Layout3D(nodes, links, idealLinkLength) {
var _this = this;
this.nodes = nodes;
this.links = links;
this.idealLinkLength = idealLinkLength;
this.constraints = null;
this.result = new Array(Layout3D.k);
for (var i = 0; i < Layout3D.k; ++i) {
this.result[i] = new Array(nodes.length);
}
nodes.forEach(function (v, i) {
for (var _i = 0, _a = Layout3D.dims; _i < _a.length; _i++) {
var dim = _a[_i];
if (typeof v[dim] == 'undefined')
v[dim] = Math.random();
}
_this.result[0][i] = v.x;
_this.result[1][i] = v.y;
_this.result[2][i] = v.z;
});
}
;
Layout3D.prototype.linkLength = function (l) {
return l.actualLength(this.result);
};
Layout3D.prototype.start = function (iterations) {
var _this = this;
if (iterations === void 0) { iterations = 100; }
var n = this.nodes.length;
var linkAccessor = new LinkAccessor();
cola.jaccardLinkLengths(this.links, linkAccessor, 1.5);
this.links.forEach(function (e) { return e.length *= _this.idealLinkLength; });
// Create the distance matrix that Cola needs
var distanceMatrix = (new cola.shortestpaths.Calculator(n, this.links, function (e) { return e.source; }, function (e) { return e.target; }, function (e) { return e.length; })).DistanceMatrix();
var D = cola.Descent.createSquareMatrix(n, function (i, j) { return distanceMatrix[i][j]; });
// G is a square matrix with G[i][j] = 1 iff there exists an edge between node i and node j
// otherwise 2.
var G = cola.Descent.createSquareMatrix(n, function () { return 2; });
this.links.forEach(function (_a) {
var source = _a.source, target = _a.target;
return G[source][target] = G[target][source] = 1;
});
this.descent = new cola.Descent(this.result, D);
this.descent.threshold = 1e-3;
this.descent.G = G;
//let constraints = this.links.map(e=> <any>{
// axis: 'y', left: e.source, right: e.target, gap: e.length*1.5
//});
if (this.constraints)
this.descent.project = new cola.vpsc.Projection(this.nodes, null, null, this.constraints).projectFunctions();
for (var i = 0; i < this.nodes.length; i++) {
var v = this.nodes[i];
if (v.fixed) {
this.descent.locks.add(i, [v.x, v.y, v.z]);
}
}
this.descent.run(iterations);
return this;
};
Layout3D.prototype.tick = function () {
this.descent.locks.clear();
for (var i = 0; i < this.nodes.length; i++) {
var v = this.nodes[i];
if (v.fixed) {
this.descent.locks.add(i, [v.x, v.y, v.z]);
}
}
return this.descent.rungeKutta();
};
Layout3D.dims = ['x', 'y', 'z'];
Layout3D.k = Layout3D.dims.length;
return Layout3D;
})();
cola.Layout3D = Layout3D;
var LinkAccessor = (function () {
function LinkAccessor() {
}
LinkAccessor.prototype.getSourceIndex = function (e) { return e.source; };
LinkAccessor.prototype.getTargetIndex = function (e) { return e.target; };
LinkAccessor.prototype.getLength = function (e) { return e.length; };
LinkAccessor.prototype.setLength = function (e, l) { e.length = l; };
return LinkAccessor;
})();
})(cola || (cola = {}));
//# sourceMappingURL=cola.js.map
Raw
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Constraint-based on a generated graph</title>
<style>
.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
fill: none;
stroke: #000;
stroke-width: 1.5px;
opacity: 0.4;
marker-end: url(#end-arrow);
}
</style>
</head>
<body>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.16/d3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="cola.min.js"></script>
<script>
var width = 960,
height = 500;
var d3cola = cola.d3adaptor()
.avoidOverlaps(true)
.size([width, height]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var nodeRadius = 5;
nodeSettings = {
emperor: {number: 1, color: "#005a32", size: 15},
governor: {number: 0, color: "#e5f5e0", size: 10},
hierarchical3: {number: 0, color: "#c7e9c0", size: 8},
hierarchical4: {number: 0, color: "#a1d99b", size: 6},
hierarchical5: {number: 0, color: "#74c476", size: 4},
hierarchical6: {number: 0, color: "#41ab5d", size: 2},
outsiderA: {number: 0, color: "#99AD99", size: 8},
outsiderB: {number: 2, color: "#9BB3A7", size: 4}
}
graph = graphConstructor();
graph.nodes.forEach(function (v) {
v.height = 8 * nodeSettings[v.type].size;
v.width = 2 * nodeSettings[v.type].size; });
d3cola
.nodes(graph.nodes)
.links(graph.links)
.flowLayout("y", 30)
.symmetricDiffLinkLengths(25)
.start(10,40,80);
// define arrow markers for graph links
svg.append('svg:defs').append('svg:marker')
.attr('id', 'end-arrow')
.attr('viewBox', '0 -5 10 10')
.attr('refX', 6)
.attr('markerWidth', 3)
.attr('markerHeight', 3)
.attr('orient', 'auto')
.append('svg:path')
.attr('d', 'M0,-5L10,0L0,5')
.attr('fill', '#000');
var path = svg.selectAll(".link")
.data(graph.links)
.enter().append('svg:path')
.attr('class', 'link');
var node = svg.selectAll(".node")
.data(graph.nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", function (d) { return nodeSettings[d.type].size})
.style("fill", function (d) { return nodeSettings[d.type].color ; })
.call(d3cola.drag);
node.append("title")
.text(function (d) { return d.name; });
d3cola.on("tick", function () {
path.attr('d', function (d) {
var deltaX = d.target.x - d.source.x,
deltaY = d.target.y - d.source.y,
dist = Math.sqrt(deltaX * deltaX + deltaY * deltaY),
normX = deltaX / dist,
normY = deltaY / dist,
sourcePadding = nodeSettings[d.source.type].size,
targetPadding = nodeSettings[d.target.type].size + 2,
sourceX = d.source.x + (sourcePadding * normX),
sourceY = d.source.y + (sourcePadding * normY),
targetX = d.target.x - (targetPadding * normX),
targetY = d.target.y - (targetPadding * normY);
return 'M' + sourceX + ',' + sourceY + 'L' + targetX + ',' + targetY;
});
node.attr("cx", function (d) { return d.x; })
.attr("cy", function (d) { return d.y; });
});
function graphConstructor() {
var nodes = [], links = [];
var verticalEdgeSettings =
[
{source: "governor", target: "emperor", number: 6, numbermin: 4},
{source: "hierarchical3", target: "governor", number: 3, numbermin: 2},
{source: "hierarchical4", target: "hierarchical3", number: 3, numbermin: 1},
{source: "hierarchical5", target: "hierarchical4", number: 3, numbermin: 1},
{source: "hierarchical6", target: "hierarchical5", number: 5, numbermin: 0},
{source: "outsiderA", target: "emperor", number: 2, numbermin: 2}
]
var horizontalEdgeSettings =
[
{source: "governor", target: "governor", probability: .01},
{source: "hierarchical3", target: "hierarchical3", probability: .05},
{source: "hierarchical4", target: "hierarchical4", probability: .025},
{source: "hierarchical5", target: "hierarchical5", probability: .01},
{source: "outsiderA", target: "emperor", probability: .1},
{source: "outsiderA", target: "governor", probability: .25},
{source: "outsiderB", target: "governor", probability: .1},
{source: "outsiderB", target: "hierarchical3", probability: .2}
]
for (nodeClass in nodeSettings) {
var x = 1;
while (x <= nodeSettings[nodeClass].number) {
var topNode = {label: nodeClass + "-" + x, type: nodeClass}
nodes.push(topNode);
x++;
}
}
var node = 0;
while (node < nodes.length && node < 500) {
for (verticalEdge in verticalEdgeSettings) {
if (nodes[node].type == verticalEdgeSettings[verticalEdge].target) {
var x = 1;
var x = Math.min(verticalEdgeSettings[verticalEdge].number - verticalEdgeSettings[verticalEdge].numbermin, Math.ceil(verticalEdgeSettings[verticalEdge].number * Math.random()))
while (x < verticalEdgeSettings[verticalEdge].number) {
var spawnNode = {label: verticalEdgeSettings[verticalEdge].source + "-" + x, type: verticalEdgeSettings[verticalEdge].source}
nodes.push(spawnNode);
var newLink = {source: nodes[node], target: spawnNode, weight: 2, type: "vertical"};
links.push(newLink);
x++;
}
}
}
node++;
}
for (nodex in nodes) {
for (nodey in nodes) {
for (horizontalEdge in horizontalEdgeSettings) {
if (horizontalEdgeSettings[horizontalEdge].source == nodes[nodex].type && horizontalEdgeSettings[horizontalEdge].target == nodes[nodey].type) {
var randomChance = Math.random();
if (randomChance < horizontalEdgeSettings[horizontalEdge].probability) {
var newLink = {source: nodes[nodex], target: nodes[nodey], weight: 1, type: "horizontal"};
links.push(newLink);
}
}
}
}
}
genNodes = nodes;
genEdges = links;
var returnObject = {links: genEdges, nodes: genNodes};
return returnObject;
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment