dagre

What is dagre?

The dagre npm package is a JavaScript library that provides facilities for graph layout. It is particularly useful for arranging nodes and edges in a directed graph, ensuring that the layout is visually appealing and easy to understand. Dagre uses a combination of algorithms to position nodes and edges in a way that minimizes edge crossings and distributes nodes evenly.

What are dagre's main functionalities?

Graph Creation

This feature allows you to create a new graph, add nodes, and define edges between them. The code sample demonstrates how to initialize a graph, set default properties, and add nodes and edges.

const dagre = require('dagre');
const g = new dagre.graphlib.Graph();
g.setGraph({});
g.setDefaultEdgeLabel(() => ({}));
g.setNode('a', { label: 'Node A', width: 50, height: 50 });
g.setNode('b', { label: 'Node B', width: 50, height: 50 });
g.setEdge('a', 'b');

Graph Layout

This feature performs the layout of the graph, positioning the nodes and edges in a visually appealing manner. The code sample shows how to apply the layout algorithm to the graph and retrieve the computed positions of the nodes.

const dagre = require('dagre');
const g = new dagre.graphlib.Graph();
g.setGraph({});
g.setDefaultEdgeLabel(() => ({}));
g.setNode('a', { label: 'Node A', width: 50, height: 50 });
g.setNode('b', { label: 'Node B', width: 50, height: 50 });
g.setEdge('a', 'b');
dagre.layout(g);
console.log(g.node('a')); // { label: 'Node A', width: 50, height: 50, x: 50, y: 50 }
console.log(g.node('b')); // { label: 'Node B', width: 50, height: 50, x: 150, y: 50 }

Other packages similar to dagre

cytoscape

Cytoscape is a graph theory library for visualizing and analyzing network data. It provides a wide range of layout algorithms and is highly customizable. Compared to dagre, Cytoscape offers more advanced features for interactive graph visualization and analysis.

d3-force

d3-force is a module of the D3.js library that provides force-directed graph layout algorithms. It is highly flexible and can be used to create dynamic, interactive visualizations. While dagre focuses on directed graphs, d3-force is more general-purpose and can handle various types of graph layouts.

elkjs

ELK (Eclipse Layout Kernel) is a layout engine for graph visualization. The elkjs package is a JavaScript port of ELK. It offers a variety of layout algorithms and is known for its high-quality layouts. Compared to dagre, ELK provides more options and fine-tuning capabilities for complex graph layouts.

README

dagre - Directed graph rendering

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

Key priorities for this library are:

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.

Demo

Try our interactive demo!

If you've checked out the project, you can build the Dagre library and then try out the demo by opening demo.html in your browser. There is no need to use a web server for the demo.

Building

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

Then follow these steps in this directory:

$ make

If you want to verify the integrity of the library, use:

$ make test

References

This work was produced by taking advantage of many papers and books. Here we summarize the sources used to develop Dagre.

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.

License

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