		@@ -0,1 +1,10 @@
		v0.5.0
		======

		Massive rewrite for a faster layout with experimental support for clustering.
		Please see the dagre wiki for details about how to use the new version. In
		addition this change pulls in a new version of graphlib that also has
		significant changes to the API. Please see the graphlib wiki at:
		https://github.com/cpettitt/graphlib/wiki.

		v0.4.6
		@@ -2,0 +11,0 @@ ======

index.js

		/*
		Copyright (c) 2012-2013 Chris Pettitt
		Copyright (c) 2012-2014 Chris Pettitt

		@@ -22,6 +22,10 @@ Permission is hereby granted, free of charge, to any person obtaining a copy
		*/
		exports.Digraph = require("graphlib").Digraph;
		exports.Graph = require("graphlib").Graph;
		exports.layout = require("./lib/layout");
		exports.version = require("./lib/version");
		exports.debug = require("./lib/debug");

		module.exports = {
		layout: require("./lib/layout"),
		debug: require("./lib/debug"),
		util: {
		time: require("./lib/util").time,
		notime: require("./lib/util").notime
		}
		};

lib/debug.js

		@@ -1,49 +0,34 @@
		'use strict';
		var _ = require("lodash"),
		util = require("./util"),
		Graph = require("graphlib").Graph;

		var util = require('./util');
		module.exports = {
		debugOrdering: debugOrdering
		};

		/**
		* Renders a graph in a stringified DOT format that indicates the ordering of
		* nodes by layer. Circles represent normal nodes. Diamons represent dummy
		* nodes. While we try to put nodes in clusters, it appears that graphviz
		* does not respect this because we're later using subgraphs for ordering nodes
		* in each layer.
		*/
		exports.dotOrdering = function(g) {
		var ordering = util.ordering(g.filterNodes(util.filterNonSubgraphs(g)));
		var result = 'digraph {';
		/* istanbul ignore next */
		function debugOrdering(g) {
		var layerMatrix = util.buildLayerMatrix(g);

		function dfs(u) {
		var children = g.children(u);
		if (children.length) {
		result += 'subgraph cluster_' + u + ' {';
		result += 'label="' + u + '";';
		children.forEach(function(v) {
		dfs(v);
		});
		result += '}';
		} else {
		result += u;
		if (g.node(u).dummy) {
		result += ' [shape=diamond]';
		}
		result += ';';
		}
		}
		var h = new Graph({ compound: true, multigraph: true }).setGraph({});

		g.children(null).forEach(dfs);
		_.each(g.nodes(), function(v) {
		h.setNode(v, { label: v });
		h.setParent(v, "layer" + g.node(v).rank);
		});

		ordering.forEach(function(layer) {
		result += 'subgraph { rank=same; edge [style="invis"];';
		result += layer.join('->');
		result += '}';
		_.each(g.edges(), function(e) {
		h.setEdge(e.v, e.w, {}, e.name);
		});

		g.eachEdge(function(e, u, v) {
		result += u + '->' + v + ';';
		_.each(layerMatrix, function(layer, i) {
		var layerV = "layer" + i;
		h.setNode(layerV, { rank: "same" });
		_.reduce(layer, function(u, v) {
		h.setEdge(u, v, { style: "invis" });
		return v;
		});
		});

		result += '}';

		return result;
		};
		return h;
		}

503

lib/layout.js

		@@ -1,269 +0,308 @@
		'use strict';
		"use strict";

		var util = require('./util'),
		rank = require('./rank'),
		order = require('./order'),
		CGraph = require('graphlib').CGraph,
		CDigraph = require('graphlib').CDigraph;
		var _ = require("lodash"),
		acyclic = require("./acyclic"),
		normalize = require("./normalize"),
		rank = require("./rank"),
		normalizeRanks = require("./util").normalizeRanks,
		parentDummyChains = require("./parent-dummy-chains"),
		removeEmptyRanks = require("./util").removeEmptyRanks,
		nestingGraph = require("./nesting-graph"),
		addBorderSegments = require("./add-border-segments"),
		order = require("./order"),
		position = require("./position"),
		util = require("./util"),
		Graph = require("graphlib").Graph;

		module.exports = function() {
		// External configuration
		var config = {
		// How much debug information to include?
		debugLevel: 0,
		// Max number of sweeps to perform in order phase
		orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
		// Use network simplex algorithm in ranking
		rankSimplex: false,
		// Rank direction. Valid values are (TB, LR)
		rankDir: 'TB'
		};
		module.exports = layout;

		// Phase functions
		var position = require('./position')();

		// This layout object
		var self = {};

		self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');

		self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');

		self.nodeSep = delegateProperty(position.nodeSep);
		self.edgeSep = delegateProperty(position.edgeSep);
		self.universalSep = delegateProperty(position.universalSep);
		self.rankSep = delegateProperty(position.rankSep);
		self.rankDir = util.propertyAccessor(self, config, 'rankDir');
		self.debugAlignment = delegateProperty(position.debugAlignment);

		self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
		util.log.level = x;
		position.debugLevel(x);
		function layout(g, opts) {
		var time = opts && opts.debugTiming ? util.time : util.notime;
		time("layout", function() {
		var layoutGraph = time(" buildLayoutGraph",
		function() { return buildLayoutGraph(g); });
		time(" runLayout", function() { runLayout(layoutGraph, time); });
		time(" updateInputGraph", function() { updateInputGraph(g, layoutGraph); });
		});
		}

		self.run = util.time('Total layout', run);
		function runLayout(g, time) {
		time(" makeSpaceForEdgeLabels", function() { makeSpaceForEdgeLabels(g); });
		time(" removeSelfEdges", function() { removeSelfEdges(g); });
		time(" acyclic", function() { acyclic.run(g); });
		time(" nestingGraph.run", function() { nestingGraph.run(g); });
		time(" rank", function() { rank(util.asNonCompoundGraph(g)); });
		time(" injectEdgeLabelProxies", function() { injectEdgeLabelProxies(g); });
		time(" removeEmptyRanks", function() { removeEmptyRanks(g); });
		time(" nestingGraph.cleanup", function() { nestingGraph.cleanup(g); });
		time(" normalizeRanks", function() { normalizeRanks(g); });
		time(" assignRankMinMax", function() { assignRankMinMax(g); });
		time(" removeEdgeLabelProxies", function() { removeEdgeLabelProxies(g); });
		time(" normalize.run", function() { normalize.run(g); });
		time(" parentDummyChains", function() { parentDummyChains(g); });
		time(" addBorderSegments", function() { addBorderSegments(g); });
		time(" order", function() { order(g); });
		time(" insertSelfEdges", function() { insertSelfEdges(g); });
		time(" position", function() { position(g); });
		time(" positionSelfEdges", function() { positionSelfEdges(g); });
		time(" removeBorderNodes", function() { removeBorderNodes(g); });
		time(" normalize.undo", function() { normalize.undo(g); });
		time(" assignNodeIntersects", function() { assignNodeIntersects(g); });
		time(" reversePoints", function() { reversePointsForReversedEdges(g); });
		time(" acyclic.undo", function() { acyclic.undo(g); });
		}

		self._normalize = normalize;
		/*
		* Copies final layout information from the layout graph back to the input
		* graph. This process only copies whitelisted attributes from the layout graph
		* to the input graph, so it serves as a good place to determine what
		* attributes can influence layout.
		*/
		function updateInputGraph(inputGraph, layoutGraph) {
		_.each(inputGraph.nodes(), function(v) {
		var inputLabel = inputGraph.node(v),
		layoutLabel = layoutGraph.node(v);

		return self;
		if (inputLabel) {
		inputLabel.x = layoutLabel.x;
		inputLabel.y = layoutLabel.y;

		/*
		* Constructs an adjacency graph using the nodes and edges specified through
		* config. For each node and edge we add a property `dagre` that contains an
		* object that will hold intermediate and final layout information. Some of
		* the contents include:
		*
		* 1) A generated ID that uniquely identifies the object.
		* 2) Dimension information for nodes (copied from the source node).
		* 3) Optional dimension information for edges.
		*
		* After the adjacency graph is constructed the code no longer needs to use
		* the original nodes and edges passed in via config.
		*/
		function initLayoutGraph(inputGraph) {
		var g = new CDigraph();

		inputGraph.eachNode(function(u, value) {
		if (value === undefined) value = {};
		g.addNode(u, {
		width: value.width,
		height: value.height
		});
		if (value.hasOwnProperty('rank')) {
		g.node(u).prefRank = value.rank;
		if (layoutGraph.children(v).length) {
		inputLabel.width = layoutLabel.width;
		inputLabel.height = layoutLabel.height;
		}
		});

		// Set up subgraphs
		if (inputGraph.parent) {
		inputGraph.nodes().forEach(function(u) {
		g.parent(u, inputGraph.parent(u));
		});
		}
		});

		inputGraph.eachEdge(function(e, u, v, value) {
		if (value === undefined) value = {};
		var newValue = {
		e: e,
		minLen: value.minLen \|\| 1,
		width: value.width \|\| 0,
		height: value.height \|\| 0,
		points: []
		};
		_.each(inputGraph.edges(), function(e) {
		var inputLabel = inputGraph.edge(e),
		layoutLabel = layoutGraph.edge(e);

		g.addEdge(null, u, v, newValue);
		});
		inputLabel.points = layoutLabel.points;
		if (_.has(layoutLabel, "x")) {
		inputLabel.x = layoutLabel.x;
		inputLabel.y = layoutLabel.y;
		}
		});
		}

		// Initial graph attributes
		var graphValue = inputGraph.graph() \|\| {};
		g.graph({
		rankDir: graphValue.rankDir \|\| config.rankDir,
		orderRestarts: graphValue.orderRestarts
		});
		var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"],
		graphDefaults = { ranksep: 50, edgesep: 10, nodesep: 50 },
		graphAttrs = ["acyclicer", "ranker", "rankdir", "align"],
		nodeNumAttrs = ["width", "height"],
		nodeDefaults = { width: 0, height: 0 },
		edgeNumAttrs = ["minlen", "weight", "width", "height"],
		edgeDefaults = { minlen: 1, weight: 1, width: 0, height: 0 };

		return g;
		}
		/*
		* Constructs a new graph from the input graph, which can be used for layout.
		* This process copies only whitelisted attributes from the input graph to the
		* layout graph. Thus this function serves as a good place to determine what
		* attributes can influence layout.
		*/
		function buildLayoutGraph(inputGraph) {
		var g = new Graph({ multigraph: true, compound: true });

		function run(inputGraph) {
		var rankSep = self.rankSep();
		var g;
		try {
		// Build internal graph
		g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
		g.setGraph(_.merge({},
		graphDefaults,
		selectNumberAttrs(inputGraph.graph(), graphNumAttrs),
		_.pick(inputGraph.graph(), graphAttrs)));

		if (g.order() === 0) {
		return g;
		}
		_.each(inputGraph.nodes(), function(v) {
		var label = inputGraph.node(v);
		g.setNode(v, _.defaults(selectNumberAttrs(label, nodeNumAttrs), nodeDefaults));
		g.setParent(v, inputGraph.parent(v));
		});

		// Make space for edge labels
		g.eachEdge(function(e, s, t, a) {
		a.minLen *= 2;
		});
		self.rankSep(rankSep / 2);
		_.each(inputGraph.edges(), function(e) {
		var label = inputGraph.edge(e);
		g.setEdge(e, _.defaults(selectNumberAttrs(label, edgeNumAttrs), edgeDefaults));
		});

		// Determine the rank for each node. Nodes with a lower rank will appear
		// above nodes of higher rank.
		util.time('rank.run', rank.run)(g, config.rankSimplex);
		return g;
		}

		// Normalize the graph by ensuring that every edge is proper (each edge has
		// a length of 1). We achieve this by adding dummy nodes to long edges,
		// thus shortening them.
		util.time('normalize', normalize)(g);
		/*
		* This idea comes from the Gansner paper: to account for edge labels in our
		* layout we split each rank in half by doubling minlen and halving ranksep.
		* Then we can place labels at these mid-points between nodes.
		*/
		function makeSpaceForEdgeLabels(g) {
		var graphLabel = g.graph();
		graphLabel.ranksep /= 2;
		_.each(g.edges(), function(e) {
		g.edge(e).minlen *= 2;
		});
		}

		// Order the nodes so that edge crossings are minimized.
		util.time('order', order)(g, config.orderMaxSweeps);
		/*
		* Creates temporary dummy nodes that capture the rank in which each edge's
		* label is going to, if it has one of non-zero width and height. We do this
		* so that we can safely remove empty ranks while preserving balance for the
		* label's position.
		*/
		function injectEdgeLabelProxies(g) {
		_.each(g.edges(), function(e) {
		var edge = g.edge(e);
		if (edge.width && edge.height) {
		var v = g.node(e.v),
		w = g.node(e.w),
		label = { rank: (w.rank - v.rank) / 2 + v.rank, e: e };
		util.addDummyNode(g, "edge-proxy", label, "_ep");
		}
		});
		}

		// Find the x and y coordinates for every node in the graph.
		util.time('position', position.run)(g);
		function assignRankMinMax(g) {
		var maxRank = 0;
		_.each(g.nodes(), function(v) {
		var node = g.node(v);
		if (node.borderTop) {
		node.minRank = g.node(node.borderTop).rank;
		node.maxRank = g.node(node.borderBottom).rank;
		maxRank = _.max(maxRank, node.maxRank);
		}
		});
		g.graph().maxRank = maxRank;
		}

		// De-normalize the graph by removing dummy nodes and augmenting the
		// original long edges with coordinate information.
		util.time('undoNormalize', undoNormalize)(g);
		function removeEdgeLabelProxies(g) {
		_.each(g.nodes(), function(v) {
		var node = g.node(v);
		if (node.dummy === "edge-proxy") {
		g.edge(node.e).labelRank = node.rank;
		g.removeNode(v);
		}
		});
		}

		// Reverses points for edges that are in a reversed state.
		util.time('fixupEdgePoints', fixupEdgePoints)(g);
		function assignNodeIntersects(g) {
		_.each(g.edges(), function(e) {
		var edge = g.edge(e),
		nodeV = g.node(e.v),
		nodeW = g.node(e.w),
		p1, p2;
		if (!edge.points) {
		edge.points = [];
		p1 = nodeW;
		p2 = nodeV;
		} else {
		p1 = edge.points[0];
		p2 = edge.points[edge.points.length - 1];
		}
		edge.points.unshift(util.intersectRect(nodeV, p1));
		edge.points.push(util.intersectRect(nodeW, p2));
		});
		}

		// Restore delete edges and reverse edges that were reversed in the rank
		// phase.
		util.time('rank.restoreEdges', rank.restoreEdges)(g);

		// Construct final result graph and return it
		return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
		} finally {
		self.rankSep(rankSep);
		function reversePointsForReversedEdges(g) {
		_.each(g.edges(), function(e) {
		var edge = g.edge(e);
		if (edge.reversed) {
		edge.points.reverse();
		}
		}
		});
		}

		/*
		* This function is responsible for 'normalizing' the graph. The process of
		* normalization ensures that no edge in the graph has spans more than one
		* rank. To do this it inserts dummy nodes as needed and links them by adding
		* dummy edges. This function keeps enough information in the dummy nodes and
		* edges to ensure that the original graph can be reconstructed later.
		*
		* This method assumes that the input graph is cycle free.
		*/
		function normalize(g) {
		var dummyCount = 0;
		g.eachEdge(function(e, s, t, a) {
		var sourceRank = g.node(s).rank;
		var targetRank = g.node(t).rank;
		if (sourceRank + 1 < targetRank) {
		for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
		var v = '_D' + (++dummyCount);
		var node = {
		width: a.width,
		height: a.height,
		edge: { id: e, source: s, target: t, attrs: a },
		rank: rank,
		dummy: true
		};
		function removeBorderNodes(g) {
		var rankdir = (g.graph().rankdir \|\| "tb").toLowerCase();
		_.each(g.nodes(), function(v) {
		if (g.children(v).length) {
		var node = g.node(v),
		t = g.node(node.borderTop),
		b = g.node(node.borderBottom),
		l = g.node(_.last(node.borderLeft)),
		r = g.node(_.last(node.borderRight)),
		tmp;

		// If this node represents a bend then we will use it as a control
		// point. For edges with 2 segments this will be the center dummy
		// node. For edges with more than two segments, this will be the
		// first and last dummy node.
		if (i === 0) node.index = 0;
		else if (rank + 1 === targetRank) node.index = 1;

		g.addNode(v, node);
		g.addEdge(null, u, v, {});
		u = v;
		}
		g.addEdge(null, u, t, {});
		g.delEdge(e);
		if (rankdir === "bt" \|\| rankdir === "rl") {
		tmp = t;
		t = b;
		b = tmp;
		}
		});
		}

		/*
		* Reconstructs the graph as it was before normalization. The positions of
		* dummy nodes are used to build an array of points for the original 'long'
		* edge. Dummy nodes and edges are removed.
		*/
		function undoNormalize(g) {
		g.eachNode(function(u, a) {
		if (a.dummy) {
		if ('index' in a) {
		var edge = a.edge;
		if (!g.hasEdge(edge.id)) {
		g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
		}
		var points = g.edge(edge.id).points;
		points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
		}
		g.delNode(u);
		if (rankdir === "lr" \|\| rankdir === "rl") {
		tmp = t;
		t = l;
		l = tmp;
		tmp = b;
		b = r;
		r = tmp;
		}
		});
		}

		/*
		* For each edge that was reversed during the `acyclic` step, reverse its
		* array of points.
		*/
		function fixupEdgePoints(g) {
		g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
		}
		node.width = r.x - l.x;
		node.height = b.y - t.y;
		node.x = l.x + node.width / 2;
		node.y = t.y + node.height / 2;
		}
		});

		function createFinalGraph(g, isDirected) {
		var out = isDirected ? new CDigraph() : new CGraph();
		out.graph(g.graph());
		g.eachNode(function(u, value) { out.addNode(u, value); });
		g.eachNode(function(u) { out.parent(u, g.parent(u)); });
		g.eachEdge(function(e, u, v, value) {
		out.addEdge(value.e, u, v, value);
		});
		_.each(g.nodes(), function(v) {
		if (g.node(v).dummy === "border") {
		g.removeNode(v);
		}
		});
		}

		// Attach bounding box information
		var maxX = 0, maxY = 0;
		g.eachNode(function(u, value) {
		if (!g.children(u).length) {
		maxX = Math.max(maxX, value.x + value.width / 2);
		maxY = Math.max(maxY, value.y + value.height / 2);
		function removeSelfEdges(g) {
		_.each(g.edges(), function(e) {
		if (e.v === e.w) {
		var node = g.node(e.v);
		if (!node.selfEdges) {
		node.selfEdges = [];
		}
		node.selfEdges.push({ e: e, label: g.edge(e) });
		g.removeEdge(e);
		}
		});
		}

		function insertSelfEdges(g) {
		var layers = util.buildLayerMatrix(g);
		_.each(layers, function(layer) {
		var orderShift = 0;
		_.each(layer, function(v, i) {
		var node = g.node(v);
		node.order = i + orderShift;
		_.each(node.selfEdges, function(selfEdge) {
		util.addDummyNode(g, "selfedge", {
		width: selfEdge.label.width,
		height: selfEdge.label.height,
		rank: node.rank,
		order: i + (++orderShift),
		e: selfEdge.e,
		label: selfEdge.label
		}, "_se");
		});
		delete node.selfEdges;
		});
		g.eachEdge(function(e, u, v, value) {
		var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
		var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
		maxX = Math.max(maxX, maxXPoints + value.width / 2);
		maxY = Math.max(maxY, maxYPoints + value.height / 2);
		});
		out.graph().width = maxX;
		out.graph().height = maxY;
		});
		}

		return out;
		}
		function positionSelfEdges(g) {
		_.each(g.nodes(), function(v) {
		var node = g.node(v);
		if (node.dummy === "selfedge") {
		var selfNode = g.node(node.e.v),
		x = selfNode.x + selfNode.width / 2,
		y = selfNode.y,
		dx = node.x - x,
		dy = selfNode.height / 2;
		g.setEdge(node.e, node.label);
		g.removeNode(v);
		node.label.points = [
		{ x: x + 2 * dx / 3, y: y - dy },
		{ x: x + 5 * dx / 6, y: y - dy },
		{ x: x + dx , y: y },
		{ x: x + 5 * dx / 6, y: y + dy },
		{ x: x + 2 * dx / 3, y: y + dy },
		];
		node.label.x = node.x;
		node.label.y = node.y;
		}
		});
		}

		/*
		* Given a function, a new function is returned that invokes the given
		* function. The return value from the function is always the `self` object.
		*/
		function delegateProperty(f) {
		return function() {
		if (!arguments.length) return f();
		f.apply(null, arguments);
		return self;
		};
		}
		};

		function selectNumberAttrs(obj, attrs) {
		return _.mapValues(_.pick(obj, attrs), Number);
		}

285

lib/util.js

		@@ -1,119 +0,236 @@
		'use strict';
		"use strict";

		/*
		* Returns the smallest value in the array.
		*/
		exports.min = function(values) {
		return Math.min.apply(Math, values);
		var _ = require("lodash"),
		Graph = require("graphlib").Graph;

		module.exports = {
		addDummyNode: addDummyNode,
		simplify: simplify,
		asNonCompoundGraph: asNonCompoundGraph,
		successorWeights: successorWeights,
		predecessorWeights: predecessorWeights,
		intersectRect: intersectRect,
		buildLayerMatrix: buildLayerMatrix,
		normalizeRanks: normalizeRanks,
		removeEmptyRanks: removeEmptyRanks,
		addBorderNode: addBorderNode,
		maxRank: maxRank,
		partition: partition,
		time: time,
		notime: notime
		};

		/*
		* Returns the largest value in the array.
		* Adds a dummy node to the graph and return v.
		*/
		exports.max = function(values) {
		return Math.max.apply(Math, values);
		};
		function addDummyNode(g, type, attrs, name) {
		var v;
		do {
		v = _.uniqueId(name);
		} while (g.hasNode(v));

		attrs.dummy = type;
		g.setNode(v, attrs);
		return v;
		}

		/*
		* Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
		* returns `false`. This function will return immediately if it finds a
		* case where `f(x)` does not hold.
		* Returns a new graph with only simple edges. Handles aggregation of data
		* associated with multi-edges.
		*/
		exports.all = function(xs, f) {
		for (var i = 0; i < xs.length; ++i) {
		if (!f(xs[i])) {
		return false;
		function simplify(g) {
		var simplified = new Graph().setGraph(g.graph());
		_.each(g.nodes(), function(v) { simplified.setNode(v, g.node(v)); });
		_.each(g.edges(), function(e) {
		var simpleLabel = simplified.edge(e.v, e.w) \|\| { weight: 0, minlen: 1 },
		label = g.edge(e);
		simplified.setEdge(e.v, e.w, {
		weight: simpleLabel.weight + label.weight,
		minlen: Math.max(simpleLabel.minlen, label.minlen)
		});
		});
		return simplified;
		}

		function asNonCompoundGraph(g) {
		var simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph());
		_.each(g.nodes(), function(v) {
		if (!g.children(v).length) {
		simplified.setNode(v, g.node(v));
		}
		}
		return true;
		};
		});
		_.each(g.edges(), function(e) {
		simplified.setEdge(e, g.edge(e));
		});
		return simplified;
		}

		/*
		* Accumulates the sum of elements in the given array using the `+` operator.
		*/
		exports.sum = function(values) {
		return values.reduce(function(acc, x) { return acc + x; }, 0);
		};
		function successorWeights(g) {
		var weightMap = _.map(g.nodes(), function(v) {
		var sucs = {};
		_.each(g.outEdges(v), function(e) {
		sucs[e.w] = (sucs[e.w] \|\| 0) + g.edge(e).weight;
		});
		return sucs;
		});
		return _.zipObject(g.nodes(), weightMap);
		}

		function predecessorWeights(g) {
		var weightMap = _.map(g.nodes(), function(v) {
		var preds = {};
		_.each(g.inEdges(v), function(e) {
		preds[e.v] = (preds[e.v] \|\| 0) + g.edge(e).weight;
		});
		return preds;
		});
		return _.zipObject(g.nodes(), weightMap);
		}

		/*
		* Returns an array of all values in the given object.
		* Finds where a line starting at point ({x, y}) would intersect a rectangle
		* ({x, y, width, height}) if it were pointing at the rectangle's center.
		*/
		exports.values = function(obj) {
		return Object.keys(obj).map(function(k) { return obj[k]; });
		};
		function intersectRect(rect, point) {
		var x = rect.x;
		var y = rect.y;

		exports.shuffle = function(array) {
		for (var i = array.length - 1; i > 0; --i) {
		var j = Math.floor(Math.random() * (i + 1));
		var aj = array[j];
		array[j] = array[i];
		array[i] = aj;
		// Rectangle intersection algorithm from:
		// http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes
		var dx = point.x - x;
		var dy = point.y - y;
		var w = rect.width / 2;
		var h = rect.height / 2;

		if (!dx && !dy) {
		throw new Error("Not possible to find intersection inside of the rectangle");
		}
		};

		exports.propertyAccessor = function(self, config, field, setHook) {
		return function(x) {
		if (!arguments.length) return config[field];
		config[field] = x;
		if (setHook) setHook(x);
		return self;
		};
		};
		var sx, sy;
		if (Math.abs(dy) * w > Math.abs(dx) * h) {
		// Intersection is top or bottom of rect.
		if (dy < 0) {
		h = -h;
		}
		sx = h * dx / dy;
		sy = h;
		} else {
		// Intersection is left or right of rect.
		if (dx < 0) {
		w = -w;
		}
		sx = w;
		sy = w * dy / dx;
		}

		return { x: x + sx, y: y + sy };
		}

		/*
		* Given a layered, directed graph with `rank` and `order` node attributes,
		* this function returns an array of ordered ranks. Each rank contains an array
		* of the ids of the nodes in that rank in the order specified by the `order`
		* attribute.
		* Given a DAG with each node assigned "rank" and "order" properties, this
		* function will produce a matrix with the ids of each node.
		*/
		exports.ordering = function(g) {
		var ordering = [];
		g.eachNode(function(u, value) {
		var rank = ordering[value.rank] \|\| (ordering[value.rank] = []);
		rank[value.order] = u;
		function buildLayerMatrix(g) {
		var layering = _.map(_.range(maxRank(g) + 1), function() { return []; });
		_.each(g.nodes(), function(v) {
		var node = g.node(v),
		rank = node.rank;
		if (!_.isUndefined(rank)) {
		layering[rank][node.order] = v;
		}
		});
		return ordering;
		};
		return layering;
		}

		/*
		* A filter that can be used with `filterNodes` to get a graph that only
		* includes nodes that do not contain others nodes.
		* Adjusts the ranks for all nodes in the graph such that all nodes v have
		* rank(v) >= 0 and at least one node w has rank(w) = 0.
		*/
		exports.filterNonSubgraphs = function(g) {
		return function(u) {
		return g.children(u).length === 0;
		function normalizeRanks(g) {
		var min = _.min(_.map(g.nodes(), function(v) { return g.node(v).rank; }));
		_.each(g.nodes(), function(v) {
		var node = g.node(v);
		if (_.has(node, "rank")) {
		node.rank -= min;
		}
		});
		}

		function removeEmptyRanks(g) {
		// Ranks may not start at 0, so we need to offset them
		var offset = _.min(_.map(g.nodes(), function(v) { return g.node(v).rank; }));

		var layers = [];
		_.each(g.nodes(), function(v) {
		var rank = g.node(v).rank - offset;
		if (!_.has(layers, rank)) {
		layers[rank] = [];
		}
		layers[rank].push(v);
		});

		var delta = 0,
		nodeRankFactor = g.graph().nodeRankFactor;
		_.each(layers, function(vs, i) {
		if (_.isUndefined(vs) && i % nodeRankFactor !== 0) {
		--delta;
		} else if (delta) {
		_.each(vs, function(v) { g.node(v).rank += delta; });
		}
		});
		}

		function addBorderNode(g, prefix, rank, order) {
		var node = {
		width: 0,
		height: 0
		};
		};
		if (arguments.length >= 4) {
		node.rank = rank;
		node.order = order;
		}
		return addDummyNode(g, "border", node, prefix);
		}

		function maxRank(g) {
		return _.max(_.map(g.nodes(), function(v) {
		var rank = g.node(v).rank;
		if (!_.isUndefined(rank)) {
		return rank;
		}
		}));
		}

		/*
		* Returns a new function that wraps `func` with a timer. The wrapper logs the
		* time it takes to execute the function.
		*
		* The timer will be enabled provided `log.level >= 1`.
		* Partition a collection into two groups: `lhs` and `rhs`. If the supplied
		* function returns true for an entry it goes into `lhs`. Otherwise it goes
		* into `rhs.
		*/
		function time(name, func) {
		return function() {
		var start = new Date().getTime();
		try {
		return func.apply(null, arguments);
		} finally {
		log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
		function partition(collection, fn) {
		var result = { lhs: [], rhs: [] };
		_.each(collection, function(value) {
		if (fn(value)) {
		result.lhs.push(value);
		} else {
		result.rhs.push(value);
		}
		};
		});
		return result;
		}
		time.enabled = false;

		exports.time = time;

		/*
		* A global logger with the specification `log(level, message, ...)` that
		* will log a message to the console if `log.level >= level`.
		* Returns a new function that wraps `fn` with a timer. The wrapper logs the
		* time it takes to execute the function.
		*/
		function log(level) {
		if (log.level >= level) {
		console.log.apply(console, Array.prototype.slice.call(arguments, 1));
		function time(name, fn) {
		var start = _.now();
		try {
		return fn();
		} finally {
		console.log(name + " time: " + (_.now() - start) + "ms");
		}
		}
		log.level = 0;

		exports.log = log;
		function notime(name, fn) {
		return fn();
		}

lib/version.js

		@@ -1,1 +0,1 @@
		module.exports = '0.4.6';
		module.exports = "0.5.0";

package.json

		{
		"name": "dagre",
		"version": "0.4.6",
		"version": "0.5.0",
		"description": "Graph layout for JavaScript",
		"author": "Chris Pettitt <cpettitt@gmail.com>",
		"main": "index.js",
		@@ -10,17 +11,20 @@ "keywords": [
		],
		"dependencies": {
		"graphlib": "0.8.0",
		"lodash": "^2.4.1"
		},
		"devDependencies": {
		"browserify": "~2.33.1",
		"chai": "1.8.x",
		"graphlib-dot": "0.4.8",
		"jshint": "2.1.x",
		"istanbul": "~0.1.44",
		"mocha": "1.12.x",
		"semver": "2.1.x",
		"uglify-js": "1.2.3"
		"benchmark": "^1.0.0",
		"browserify": "^5.10.1",
		"chai": "^1.9.1",
		"istanbul": "^0.3.0",
		"jscs": "^1.5.9",
		"jshint": "^2.5.5",
		"jshint-stylish": "^0.4.0",
		"lodash": "^2.4.1",
		"mocha": "^1.21.4",
		"semver": "^3.0.1",
		"sprintf": "^0.1.4",
		"uglify-js": "^2.4.15"
		},
		"dependencies": {
		"cp-data": "1.1.3",
		"graphlib": "0.7.4"
		},
		"author": "Chris Pettitt <chris@samsarin.com>",
		"repository": {
		@@ -27,0 +31,0 @@ "type": "git",

273

README.md

		@@ -8,270 +8,5 @@ # dagre - Graph layout for JavaScript

		Key priorities for this library are:
		For more details, including examples and configuration options, please see our
		[wiki](https://github.com/cpettitt/dagre/wiki).

		1. Completely client-side computed layout. There are great, feature-rich
		alternatives, like [graphviz](http://www.graphviz.org), if client-side
		layout is not a requirement for you.

		2. Speed. Dagre must be able to draw medium sized graphs quickly, potentially
		at the cost of not being able to adopt more optimal or exact algorithms.

		3. Rendering agnostic. Dagre requires only very basic information to lay out
		graphs, such as the dimensions of nodes. You're free to render the graph using
		whatever technology you prefer. We use [D3][]
		in some of our examples and highly recommend it if you plan to render using
		CSS and SVG.

		Note that dagre is current a pre-1.0.0 library. We will do our best to
		maintain backwards compatibility for patch level increases (e.g. 0.0.1 to
		0.0.2) but make no claim to backwards compatibility across minor releases (e.g.
		0.0.1 to 0.1.0). Watch our [CHANGELOG](CHANGELOG.md) for details on changes.

		## Getting Dagre

		### Browser Scrips

		You can get the latest browser-ready scripts:

		* [dagre.js](http://cpettitt.github.io/project/dagre/latest/dagre.js)
		* [dagre.min.js](http://cpettitt.github.io/project/dagre/latest/dagre.min.js)

		### NPM Install

		Before installing this library you need to install the [npm package manager].

		To get dagre from npm, use:

		$ npm install dagre

		### Build From Source

		Before building this library you need to install the [npm package manager].

		Check out this project and run this command from the root of the project:

		$ make dist

		This will generate `dagre.js` and `dagre.min.js` in the `dist` directory
		of the project.

		## Using Dagre

		### A Note on Rendering

		As mentioned above, dagre's focus in on graph layout only. This means that you
		need something to actually render the graphs with the layout information from
		dagre.

		There are a couple of options for rendering:

		* [dagre-d3](https://github.com/cpettitt/dagre-d3) is a D3-based renderer for
		dagre.
		* [JointJS][] is a renderer that provides facilities for editing a graph after
		it has been rendered.

		### An Example Layout

		First we need to load the dagre library. In an HTML page you do this by adding
		the following snippet:

		```html
		<script src="http://PATH/TO/dagre.min.js"></script>
		```

		In node.js you use:

		```js
		var dagre = require("dagre");
		```

		We use [graphlib](https://github.com/cpettitt/graphlib) to create graphs in
		dagre, so its probably worth taking a look at its
		[API](http://cpettitt.github.io/project/graphlib/latest/doc/index.html).
		Graphlib comes bundled with dagre. In this section, we'll show you how to
		create a simple graph.

		A node must be an object with the following properties:

		* `width` - how wide the node should be in pixels
		* `height` - how tall the node should be in pixels

		The attributes would typically come from a rendering engine that has already
		determined the space needed for a node.

		Here's a quick example of how to set up nodes and edges:

		```js
		// Create a new directed graph
		var g = new dagre.Digraph();

		// Add nodes to the graph. The first argument is the node id. The second is
		// metadata about the node. In this case we're going to add labels to each of
		// our nodes.
		g.addNode("kspacey", { label: "Kevin Spacey", width: 144, height: 100 });
		g.addNode("swilliams", { label: "Saul Williams", width: 160, height: 100 });
		g.addNode("bpitt", { label: "Brad Pitt", width: 108, height: 100 });
		g.addNode("hford", { label: "Harrison Ford", width: 168, height: 100 });
		g.addNode("lwilson", { label: "Luke Wilson", width: 144, height: 100 });
		g.addNode("kbacon", { label: "Kevin Bacon", width: 121, height: 100 });

		// Add edges to the graph. The first argument is the edge id. Here we use null
		// to indicate that an arbitrary edge id can be assigned automatically. The
		// second argument is the source of the edge. The third argument is the target
		// of the edge.
		g.addEdge(null, "kspacey", "swilliams");
		g.addEdge(null, "swilliams", "kbacon");
		g.addEdge(null, "bpitt", "kbacon");
		g.addEdge(null, "hford", "lwilson");
		g.addEdge(null, "lwilson", "kbacon");
		```

		Next we can ask dagre to do the layout for these nodes and edges. This is done
		with the following code:

		```js
		var layout = dagre.layout().run(g);
		```

		An object with layout information will be attached to each node and edge under
		the `dagre` property.

		The node's `dagre` object has the following properties:

		* x - the x-coordinate of the center of the node
		* y - the y-coordinate of the center of the node

		The edge's `dagre` object has a `points` property, which is an array of objects
		with the following properties:

		* x - the x-coordinate for the center of this bend in the edge
		* y - the y-coordinate for the center of this bend in the edge

		For example, the following layout information is generated for the above objects:

		```js
		layout.eachNode(function(u, value) {
		console.log("Node " + u + ": " + JSON.stringify(value));
		});
		layout.eachEdge(function(e, u, v, value) {
		console.log("Edge " + u + " -> " + v + ": " + JSON.stringify(value));
		});
		```

		Prints:

		```
		Node kspacey: {"id":"kspacey","width":144,"height":100,"rank":0,"order":0,"ul":0,"ur":0,"dl":0,"dr":0,"x":84,"y":50}
		Node swilliams: {"id":"swilliams","width":168,"height":100,"rank":2,"order":0,"ul":0,"ur":0,"dl":0,"dr":0,"x":84,"y":180}
		Node bpitt: {"id":"bpitt","width":108,"height":100,"rank":2,"order":1,"ul":188,"ur":188,"dl":188,"dr":188,"x":272,"y":180}
		Node hford: {"id":"hford","width":168,"height":100,"rank":0,"order":1,"ul":364,"ur":364,"dl":364,"dr":364,"x":448,"y":50}
		Node lwilson: {"id":"lwilson","width":144,"height":100,"rank":2,"order":2,"ul":364,"ur":364,"dl":364,"dr":364,"x":448,"y":180}
		Node kbacon: {"id":"kbacon","width":121,"height":100,"rank":4,"order":0,"ul":188,"ur":188,"dl":0,"dr":364,"x":272,"y":310}

		Edge kspacey -> swilliams: {"points":[{"x":84,"y":115,"ul":0,"ur":0,"dl":0,"dr":0}],"id":"_E0","minLen":2,"width":0,"height":0}
		Edge swilliams -> kbacon: {"points":[{"x":84,"y":245,"ul":0,"ur":0,"dl":0,"dr":0}],"id":"_E1","minLen":2,"width":0,"height":0}
		Edge bpitt -> kbacon: {"points":[{"x":272,"y":245,"ul":188,"ur":188,"dl":188,"dr":188}],"id":"_E2","minLen":2,"width":0,"height":0}
		Edge hford -> lwilson: {"points":[{"x":448,"y":115,"ul":364,"ur":364,"dl":364,"dr":364}],"id":"_E3","minLen":2,"width":0,"height":0}
		Edge lwilson -> kbacon: {"points":[{"x":448,"y":245,"ul":364,"ur":364,"dl":364,"dr":364}],"id":"_E4","minLen":2,"width":0,"height":0}
		```

		Besides just the `x` and `y` coordinates there are other debug attributes that
		are not guaranteed to be present.

		### Configuring the Layout

		Here are a few methods you can call on the layout object to change layout behavior:

		* `debugLevel(x)` sets the level of logging verbosity to the number `x`. Currently 4 is th max.
		* `nodeSep(x)` sets the separation between adjacent nodes in the same rank to `x` pixels.
		* `edgeSep(x)` sets the separation between adjacent edges in the same rank to `x` pixels.
		* `rankSep(x)` sets the sepration between ranks in the layout to `x` pixels.
		* `rankDir(x)` sets the direction of the layout.
		* Defaults to `"TB"` for top-to-bottom layout
		* `"LR"` sets layout to left-to-right

		For example, to set node separation to 20 pixels and the rank direction to left-to-right:

		```js
		var layout = dagre.layout()
		.nodeSep(20)
		.rankDir("LR")
		.run(g);
		```

		### Input Graph

		The input graph supplied for layout can have the following attributes:

		Object \| Attribute \| Default \| Description
		------ \| --------- \| ------- \| -----------
		graph \| rankDir \| TB \| Direction for rank nodes. Can be `TB`, `BT`, `LR`, or `RL`, where T = top, B = bottom, L = left, and R = right.
		node \| height \| \| The height of the node.
		node \| width \| \| The width of the node.
		edge \| minLen \| 1 \| The number of ranks to keep between the source and target of the edge.


		### Output Graph

		The output graph has the following attributes:

		Object \| Attribute \| Description
		------ \| --------- \| -----------
		graph \| height \| The height of the entire graph.
		graph \| width \| The width of the entire graph.
		node \| x \| The x-coordinate for the center of the node.
		node \| y \| The y-coordinate for the center of the node.
		edge \| points \| An array of { x, y } pairs for the control points of the edge.

		## Resources

		* [Issue tracker](https://github.com/cpettitt/dagre/issues)
		* [Mailing list](https://groups.google.com/group/dagre)

		### Recommend Reading

		This work was produced by taking advantage of many papers and books. If you're
		interested in how dagre works internally here are some of the most important
		papers to read.

		The general skeleton for Dagre comes from *Gansner, et al., "A Technique for
		Drawing Directed Graphs"*, which gives both an excellent high level overview of
		the phases involved in layered drawing as well as diving into the details and
		problems of each of the phases. Besides the basic skeleton, we specifically
		used the technique described in the paper to produce an acyclic graph, and we
		use the idea of a minimum spanning tree for ranking. We do not currently use
		the network simplex algorithm for ranking. If there is one paper to start with
		when learning about layered graph drawing, this seems to be it!

		For crossing minimization we used *Jünger and Mutzel, "2-Layer Straightline
		Crossing Minimization"*, which provides a comparison of the performance of
		various heuristics and exact algorithms for crossing minimization.

		For counting the number of edge crossings between two layers we use the `O(\|E\|
		log \|V_small\|)` algorithm described in *Barth, et al., "Simple and Efficient
		Bilayer Cross Counting"*.

		For positioning (or coordinate assignment), we derived our algorithm from
		Brandes and Köpf, "Fast and Simple Horizontal Coordinate Assignment". We made
		some some adjustments to get tighter graphs when node and edges sizes vary
		greatly.

		## Third Party Examples

		Dagre has been included as a part of some very cool projects. Here are just a
		few that stand out:

		[JointJS][] has a plugin that uses dagre for layout. JointJS focuses on
		rendering and interaction with diagrams, which synergizes well with Dagre. If
		you want the ability to move nodes and manipulate edges interactively, this is
		a good place to start!

		Jonathan Mace has a
		[demo](http://cs.brown.edu/people/jcmace/d3/graph.html?id=small.json) that
		makes it possible to interactively explore graphs. In his demo, you can
		highlight paths, collapse subgraphs, via detailed node information, and more!

		[nomnoml](http://www.nomnoml.com/) is a tool for drawing UML diagrams in a
		browser. It uses a custom renderer with dagre to draw the diagrams in an
		HTML5 canvas.

		## License
		@@ -281,5 +16,1 @@
		for details.

		[npm package manager]: http://npmjs.org/
		[D3]: https://github.com/mbostock/d3
		[JointJS]: http://www.daviddurman.com/automatic-graph-layout-with-jointjs-and-dagre.html

lib/order.js

lib/order/crossCount.js

lib/order/initLayerGraphs.js

lib/order/initOrder.js

lib/order/sortLayer.js

lib/position.js

lib/rank.js

lib/rank/acyclic.js

lib/rank/buildWeightGraph.js

lib/rank/constraints.js

lib/rank/feasibleTree.js

lib/rank/initRank.js

lib/rank/rankUtil.js

lib/rank/simplex.js

.jshintrc

Sorry, the diff of this file is not supported yet

.travis.yml

Sorry, the diff of this file is not supported yet

LICENSE

Sorry, the diff of this file is not supported yet

dagre - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics

Worsened metrics

Dependency changes