Skip to content

Home

Jump to bottom Edit New page
Max Franz edited this page Mar 7, 2016 · 36 revisions

Dagre is a JavaScript library that makes it easy to lay out directed graphs on the client-side.

Table of Contents

Design Priorities

  1. Completely client-side computed layout. There are great, feature-rich alternatives, like graphviz, 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.

Installing

npm Install

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

To get dagre from npm, use:

$ npm install dagre

Bower Install

You can install dagre with bower using the following command:

$ bower install dagre

Browser Scripts

You can get the latest browser-ready scripts:

You can also get the scripts for a particular version. For example, to get v0.5.1:

Look at the releases page to find a list of versions.

Source Build

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 few options for rendering:

  • 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.
  • Cytoscape.js is a complete graph library, supporting visualisation and analysis usecases, that can use Dagre as a layout. Cytoscape.js has sophisticated rendering that is specified by CSS-like stylesheets.

An Example Layout

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

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

In node.js you use:

var dagre = require("dagre");

We use graphlib to create graphs in dagre, so its probably worth taking a look at its API. 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:

// Create a new directed graph 
var g = new dagre.graphlib.Graph();

// Set an object for the graph label
g.setGraph({});

// Default to assigning a new object as a label for each new edge.
g.setDefaultEdgeLabel(function() { return {}; });

// 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.setNode("kspacey",    { label: "Kevin Spacey",  width: 144, height: 100 });
g.setNode("swilliams",  { label: "Saul Williams", width: 160, height: 100 });
g.setNode("bpitt",      { label: "Brad Pitt",     width: 108, height: 100 });
g.setNode("hford",      { label: "Harrison Ford", width: 168, height: 100 });
g.setNode("lwilson",    { label: "Luke Wilson",   width: 144, height: 100 });
g.setNode("kbacon",     { label: "Kevin Bacon",   width: 121, height: 100 });

// Add edges to the graph.
g.setEdge("kspacey",   "swilliams");
g.setEdge("swilliams", "kbacon");
g.setEdge("bpitt",     "kbacon");
g.setEdge("hford",     "lwilson");
g.setEdge("lwilson",   "kbacon");

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

dagre.layout(g);

The graph is update with layout information. Nodes get the following properties:

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

Edges get a points property that includes control point coordinates for the edge with points where the edge intersects with the node, assuming a rectangular shape:

  • 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:

g.nodes().forEach(function(v) {
     console.log("Node " + v + ": " + JSON.stringify(g.node(v)));
});
g.edges().forEach(function(e) {
    console.log("Edge " + e.v + " -> " + e.w + ": " + JSON.stringify(g.edge(e)));
});

Prints:

Node kspacey: {"label":"Kevin Spacey","width":144,"height":100,"x":80,"y":50}
Node swilliams: {"label":"Saul Williams","width":160,"height":100,"x":80,"y":200}
Node bpitt: {"label":"Brad Pitt","width":108,"height":100,"x":264,"y":200}
Node hford: {"label":"Harrison Ford","width":168,"height":100,"x":440,"y":50}
Node lwilson: {"label":"Luke Wilson","width":144,"height":100,"x":440,"y":200}
Node kbacon: {"label":"Kevin Bacon","width":121,"height":100,"x":264,"y":350}

Edge kspacey -> swilliams: {"points":[{"x":80,"y":100},{"x":80,"y":125},{"x":80,"y":150}]}
Edge swilliams -> kbacon: {"points":[{"x":80,"y":250},{"x":80,"y":275},{"x":203.5,"y":325.3396739130435}]}
Edge bpitt -> kbacon: {"points":[{"x":264,"y":250},{"x":264,"y":275},{"x":264,"y":300}]}
Edge hford -> lwilson: {"points":[{"x":440,"y":100},{"x":440,"y":125},{"x":440,"y":150}]}
Edge lwilson -> kbacon: {"points":[{"x":440,"y":250},{"x":440,"y":275},{"x":324.5,"y":324.21875}]}

Configuring the Layout

The layout can be configured by either setting the properties in the table below on the appropriate objects in the graph or by passing a second arg to layout with these properties set. The latter takes precedence.

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.
graph align TB Alignment for rank nodes. Can be UL, UR, DL, or DR, where U = up, D = down, L = left, and R = right.
graph nodesep 50 Number of pixels that separate nodes horizontally in the layout.
graph edgesep 10 Number of pixels that separate edges horizontally in the layout.
graph ranksep 50 Number of pixels between each rank in the layout.
graph marginx 0 Number of pixels to use as a margin around the left and right of the graph.
graph marginy 0 Number of pixels to use as a margin around the top and bottom of the graph.
node width 0 The width of the node in pixels.
node height 0 The height of the node in pixels.
edge minlen 1 The number of ranks to keep between the source and target of the edge.
edge weight 1 The weight to assign edges. Higher weight edges are generally made shorter and straighter than lower weight edges.
edge width 0 The width of the edge label in pixels.
edge height 0 The height of the edge label in pixels.
edge labelpos r Where to place the label relative to the edge. l = left, c = center r = right.
edge labeloffset 10 How many pixels to move the label away from the edge. Applies only when labelpos is l or r.

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, edge x For nodes, the x-coordinate for the center of the node. For edges the x-coordinate for the center of the edge label.
node, edge y For nodes, the y-coordinate for the center of the node. For edges the y-coordinate for the center of the edge label.
edge points An array of { x, y } pairs for the control points of the edge.

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 that makes it possible to interactively explore graphs. In his demo, you can highlight paths, collapse subgraphs, view detailed node information, and more!

nomnoml 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.

Cytoscape.js is a fully featured graph theory library that has support for Dagre as a layout.

Recommended 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 network simplex algorithm for ranking. If there is one paper to start with when learning about layered graph drawing, this is 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 adjustments to get tighter graphs when node and edges sizes vary greatly.

The implementation for clustering derives extensively from Sander, "Layout of Compound Directed Graphs." It is an excellent paper that details the impact of clustering on all phases of layout and also covers many of the associated problems. Crossing reduction with clustered graphs derives from two papers by Michael Forster, "Applying Crossing Reduction Strategies to Layered Compound Graphs" and "A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction."

License

Dagre is licensed under the terms of the MIT License. See LICENSE for details.

Add a custom footer
Add a custom sidebar
Clone this wiki locally