Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

dagre

Package Overview
Dependencies
Maintainers
1
Versions
47
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

dagre - npm Package Compare versions

Comparing version 0.2.0 to 0.3.0

13

CHANGELOG.md

@@ -0,1 +1,14 @@

v0.3.0
======
**Backwards incompatible** changes:
* Dagre now takes a `dagre.Digraph` or `dagre.Graph` as input for layout. See
[README.md](README.md) for details.
* `util` is no longer exported from dagre.
Backwards compatible changes:
* Dagre can now perform layout for undirected graphs (dagre.Graph).
v0.2.0

@@ -2,0 +15,0 @@ ======

4

index.js

@@ -22,5 +22,5 @@ /*

*/
exports.dot = require("./lib/dot");
exports.Digraph = require("graphlib").Digraph;
exports.Graph = require("graphlib").Graph;
exports.layout = require("./lib/layout/layout");
exports.util = require("./lib/util");
exports.version = require("./lib/version");

119

lib/layout/layout.js
var util = require("../util"),
rank = require("./rank"),
acyclic = require("./acyclic"),
Digraph = require("graphlib").Digraph;
Digraph = require("graphlib").Digraph,
Graph = require("graphlib").Graph,
Set = require("graphlib").data.Set;

@@ -9,6 +11,2 @@ module.exports = function() {

var config = {
// Nodes to lay out. At minimum must have `width` and `height` attributes.
nodes: [],
// Edges to lay out. At mimimum must have `source` and `target` attributes.
edges: [],
// How much debug information to include?

@@ -28,5 +26,2 @@ debugLevel: 0,

self.nodes = util.propertyAccessor(self, config, "nodes");
self.edges = util.propertyAccessor(self, config, "edges");
self.orderIters = delegateProperty(order.iterations);

@@ -66,49 +61,29 @@

*/
function buildAdjacencyGraph() {
function buildAdjacencyGraph(inputGraph) {
var g = new Digraph();
var nextId = 0;
// Get the node id for the type ("source" or "target") or throw if we
// haven't seen the node.
function safeGetNodeId(type, edge) {
var nodeId;
if (type in edge) {
nodeId = edge[type].dagre.id;
} else {
if (!(type + "Id" in edge)) {
throw new Error("Edge must have either a " + type + " or " + type + "Id attribute");
}
nodeId = edge[type + "Id"];
edge[type] = g.node(nodeId);
}
if (!g.hasNode(nodeId)) {
throw new Error(type + " node for '" + e + "' not in node list");
}
return nodeId;
}
// Tag each node so that we can properly represent relationships when
// we add edges. Also copy relevant dimension information.
config.nodes.forEach(function(u) {
var id = "id" in u ? u.id : "_N" + nextId++;
u.dagre = { id: id, width: u.width, height: u.height };
g.addNode(id, u.dagre);
inputGraph.eachNode(function(u, value) {
if (value === undefined) value = {};
g.addNode(u, {
width: value.width,
height: value.height
});
});
config.edges.forEach(function(e) {
var source = safeGetNodeId("source", e);
var target = safeGetNodeId("target", e);
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: []
};
e.dagre = { points: [] };
g.addEdge(null, u, v, newValue);
// Track edges that aren't self loops - layout does nothing for self
// loops, so they can be skipped.
if (source !== target) {
var id = "id" in e ? e.id : "_E" + nextId++;
e.dagre.id = id;
e.dagre.minLen = e.minLen || 1;
e.dagre.width = e.width || 0;
e.dagre.height = e.height || 0;
g.addEdge(id, source, target, e.dagre);
// If input graph is not directed, we create also add a reverse edge.
// After we've run the acyclic algorithm we'll remove one of these edges.
if (!inputGraph.isDirected()) {
g.addEdge(null, v, u, newValue);
}

@@ -120,12 +95,13 @@ });

function run () {
function run(inputGraph) {
var rankSep = self.rankSep();
var g;
try {
if (!config.nodes.length) {
return;
// Build internal graph
g = buildAdjacencyGraph(inputGraph);
if (g.order() === 0) {
return g;
}
// Build internal graph
var g = buildAdjacencyGraph();
// Make space for edge labels

@@ -141,2 +117,10 @@ g.eachEdge(function(e, s, t, a) {

// Our intermediate graph is always directed. However, the input graph
// may be undirected, so we create duplicate edges in opposite directions
// in the buildAdjacencyGraph function. At this point one of each pair of
// edges was reversed, so we remove the redundant edge.
if (!inputGraph.isDirected()) {
removeDupEdges(g);
}
// Determine the rank for each node. Nodes with a lower rank will appear

@@ -166,7 +150,18 @@ // above nodes of higher rank.

acyclic.undo(g);
// Construct final result graph and return it
return createFinalGraph(g, inputGraph.isDirected());
} finally {
self.rankSep(rankSep);
}
}
return self;
function removeDupEdges(g) {
var visited = new Set();
g.eachEdge(function(e, u, v, value) {
if (visited.has(value.e)) {
g.delEdge(e);
}
visited.add(value.e);
});
}

@@ -222,4 +217,2 @@

function undoNormalize(g) {
var visited = {};
g.eachNode(function(u, a) {

@@ -246,2 +239,12 @@ if (a.dummy && "index" in a) {

function createFinalGraph(g, isDirected) {
var out = isDirected ? new Digraph() : new Graph();
g.eachNode(function(u, value) { out.addNode(u, value); });
g.eachEdge(function(e, u, v, value) {
out.addEdge("e" in value ? value.e : e, u, v, value);
delete value.e;
});
return out;
}
/*

@@ -248,0 +251,0 @@ * Given a function, a new function is returned that invokes the given

10

lib/layout/rank.js
var util = require("../util"),
components = require("../algo/components"),
prim = require("../algo/prim"),
PriorityQueue = require("../data/PriorityQueue"),
Set = require("../data/Set");
components = require("graphlib").alg.components,
filter = require("graphlib").filter;
PriorityQueue = require("graphlib").data.PriorityQueue,
Set = require("graphlib").data.Set;

@@ -13,3 +13,3 @@ module.exports = function(g, debugLevel) {

components(g).forEach(function(cmpt) {
var subgraph = g.subgraph(cmpt);
var subgraph = g.filterNodes(filter.nodesFromList(cmpt));
feasibleTree(subgraph);

@@ -16,0 +16,0 @@ normalize(subgraph);

76

lib/util.js
/*
* Copies attributes from `src` to `dst`. If an attribute name is in both
* `src` and `dst` then the attribute value from `src` takes precedence.
*/
exports.mergeAttributes = function(src, dst) {
Object.keys(src).forEach(function(k) { dst[k] = src[k]; });
};
/*
* Returns the smallest value in the array.

@@ -45,9 +37,2 @@ */

/*
* Joins all of the given arrays into a single array.
*/
exports.concat = function(arrays) {
return Array.prototype.concat.apply([], arrays);
};
/*
* Returns an array of all values in the given object.

@@ -59,63 +44,2 @@ */

/*
* Treats each input array as a set and returns the union of all of the arrays.
* This function biases towards the last array. That is, if an "equivalent"
* key appears in more than on array, the resulting array will contain the last
* "equivalent" key.
*/
exports.union = function(arrays) {
var obj = {};
for (var i = 0; i < arrays.length; ++i) {
var a = arrays[i];
for (var j = 0; j < a.length; ++j) {
var v = a[j];
obj[v] = v;
}
}
var results = [];
for (var k in obj) {
results.push(obj[k]);
}
return results;
};
exports.intersectRect = function(rect, point) {
var x = rect.x;
var y = rect.y;
// For now we only support rectangles
// 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;
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 = dy === 0 ? 0 : h * dx / dy;
sy = h;
} else {
// Intersection is left or right of rect.
if (dx < 0) {
w = -w;
}
sx = w;
sy = dx === 0 ? 0 : w * dy / dx;
}
return {x: x + sx, y: y + sy};
};
exports.pointStr = function(point) {
return point.x + "," + point.y;
};
exports.createTimer = function(enabled) {

@@ -122,0 +46,0 @@ var self = {};

2

lib/version.js

@@ -1,1 +0,1 @@

module.exports = '0.2.0';
module.exports = '0.3.0';

17

package.json
{
"name": "dagre",
"version": "0.2.0",
"version": "0.3.0",
"description": "Directed graph rendering",

@@ -11,3 +11,9 @@ "main": "index.js",

"scripts": {
"test": "make test"
"blanket": {
"pattern": "lib",
"data-cover-never": [
"node_modules",
"test"
]
}
},

@@ -18,11 +24,12 @@ "keywords": [

"devDependencies": {
"blanket": "1.x.x",
"browserify": "2.28.x",
"chai": "1.7.x",
"graphlib-dot": "0.4.1",
"mocha": "1.12.x",
"semver": "2.1.x",
"uglify-js": "2.4.x"
"uglify-js": "1.2.3"
},
"dependencies": {
"graphlib": "0.1.x",
"graphlib-dot": "0.0.x"
"graphlib": "0.5.7"
},

@@ -29,0 +36,0 @@ "author": "Chris Pettitt <chris@samsarin.com>",

113

README.md

@@ -30,11 +30,2 @@ # dagre - Directed graph rendering

## Demo
Try our [interactive demo](http://cpettitt.github.com/project/dagre/latest/demo/demo.html)!
Or see an example of rendering the [TCP state diagram](http://cpettitt.github.com/project/dagre/latest/demo/demo-d3.html).
These demos and more can be found in the `demo` folder of the project. Simply
open them in your browser - there is no need to start a web server.
## Getting Dagre

@@ -76,18 +67,9 @@

For a simple starting point, we suggest looking at the user contributed
`demo/dagre-d3-simple.js` script for doing good but easy rendering. To get
started look at `demo/sentence-tokenization.html`.
There are a couple of options for rendering:
Another option is to use [JointJS][]. See the link for an article about how to
use it with Dagre. The ability to manipulate nodes and edges after they are
layed out and renderer can be very useful!
* [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.
For even more control over rendering you can write a custom renderer or take
advantage or a library like [D3][], which makes it easier to creates graphs
with SVG. The code in `demo/dagre-d3-simple.js` uses D3, so this may be a
good place to start.
Ultimately we plan to make available some basic renderers for Dagre in the
near future.
### An Example Layout

@@ -108,7 +90,8 @@

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-d3. In this section, we'll show you how to
create a simple graph.
The current version of Dagre takes an array of nodes and edges, along with some
optional configuration, and attaches layout information to the nodes and edges
in the `dagre` property.
A node must be an object with the following properties:

@@ -122,31 +105,27 @@

An edge must be an object with either references to its adjacent nodes:
* `source` - a reference to the source node
* `target` - a reference to the target node
Or with the ids of its adjacent nodes:
* `sourceId` - the id of the source node
* `targetId` - the id of the target node
Here's a quick example of how to set up nodes and edges:
```js
var nodes = [
{ id: "kspacey", label: "Kevin Spacey", width: 144, height: 100 },
{ id: "swilliams", label: "Saul Williams", width: 168, height: 100 },
{ id: "bpitt", label: "Brad Pitt", width: 108, height: 100 },
{ id: "hford", label: "Harrison Ford", width: 168, height: 100 },
{ id: "oplat", label: "Oliver Platt", width: 144, height: 100 },
{ id: "kbacon", label: "Kevin Bacon", width: 121, height: 100 },
// Create a new directed graph
var g = new dagre.Digraph();
];
var edges = [
{ sourceId: "kspacey", targetId: "swilliams" },
{ sourceId: "swilliams", targetId: "kbacon" },
{ sourceId: "bpitt", targetId: "kbacon" },
{ sourceId: "hford", targetId: "oplat" },
{ sourceId: "oplat", targetId: "kbacon" }
];
// 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");
```

@@ -158,6 +137,3 @@

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

@@ -182,8 +158,7 @@

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

@@ -199,3 +174,3 @@ ```

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 oplat: {"id":"oplat","width":144,"height":100,"rank":2,"order":2,"ul":364,"ur":364,"dl":364,"dr":364,"x":448,"y":180}
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}

@@ -206,4 +181,4 @@

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 -> oplat: {"points":[{"x":448,"y":115,"ul":364,"ur":364,"dl":364,"dr":364}],"id":"_E3","minLen":2,"width":0,"height":0}
Edge oplat -> kbacon: {"points":[{"x":448,"y":245,"ul":364,"ur":364,"dl":364,"dr":364}],"id":"_E4","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}
```

@@ -229,8 +204,6 @@

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

@@ -237,0 +210,0 @@ 

lib/algo/components.js
lib/algo/prim.js
lib/data/PriorityQueue.js
lib/data/Set.js
lib/dot-grammar.js
lib/dot.js
.npmignore

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc