See this graph.

I would like to know how Dagre determines which nodes are drawn at the top, and which are located at the bottom.
We have a set of nodes that have an ID which is numbered from N1, ..., Nn. Every time it is run, N1 appears at the very bottom, but it would be nice if it was at the top. Here is an example dot file:

digraph {
    N4 [label="4"];
    N1 [label="1"];
    N4 -> N1;
    N5 [label="5"];
    N2 [label="2"];
    N5 -> N2;
    N3 [label="3"];
    N3 -> N4;
    N5 -> N1;
    N2 -> N1;
    N2 -> N3;
    N3 -> N1;
}

The d3 integration is great!

Thanks a lot,
Moritz

Example bad input:

digraph {
    A-> B -> C; C -> A
}

Error reported:

Uncaught TypeError: Cannot call method 'tail' of undefined dagre.js:1024
collapseChain dagre.js:1024

Hi Chris,

Thanks a ton for dagre.

I found a bug and made a possible fix to barycenterLayer(). Your cleanup of that function's code introduced a bug where not all nodes in the movable layer remain in the layer after reordering, and some nodes wind up getting inserted more than once in the layer. I think the idea is that nodes without predecessors are left alone, which means that the toSort array should not contain those nodes.

Since the function is small, I'll simply show you my modified version here:

  function barycenterLayer(fixed, movable, predecessors) {
    var pos = layerPos(movable);
    var bs = barycenters(fixed, movable, predecessors);

    var toSort = [];
    movable.forEach(function(u) {
      if (bs[u] !== -1) {
        toSort.push(u);
      }
    });

    toSort.sort(function(x, y) {
      return bs[x] - bs[y] || pos[x] - pos[y];
    });

    for (var i = movable.length - 1; i >= 0; --i) {
      if (bs[movable[i]] !== -1) {
        movable[i] = toSort.pop();
      }
    }
  }

Best regards,
Paul

Allow custom placement of nodes and edge bends in the interactive demo. The first pass at this can be pretty naive. A follow up ticket will propose something even better.

digraph { A->B; B->C; D->G->C; A->I; E->F->A->G;I->G1;I->G2 ;I->G3;}

A->I; crosses D->G. Should not be necessary. Dot output is:

For example, this graph below places "A" far too low. This is most obvious with larger font sizes.

This graph shows examples of both cases (multi-edges and short cycles) that produce overlapping edges.

DOT syntax (as used in graphviz) allows HTML to be used as part of labels. HTML can be embeded in SVG through the use of a "foreignObject" element. Please add better support for HTML labels in dagre. Thanks!

It could be a good way to show how use Dagre with other rendering engine.

The graphviz scheme is to add an extra dummy node for each segment and to set the rankSep /= 2. One of the dummy nodes is assigned the text (so it's height and width would change). Layout then does proper separation for the label.

For example, this graph should have B and D closer to C.

Once we're doing with the ordering phase we should save order information in the nodes. We can use this to do incremental repositioning later.

This is needed to implement #20.

Imagine this: the graph layout algorithm has done a pretty good job of laying things out, but for clarity you want to slightly tweak the layout. With this feature you'd just drag things to the appropriate locations and we'd only rerun portions of the layout algorithm (for example the positioning algorithm, but not the ranking or ordering algorithms).

Hi there-
First of all, I would like to thank you for providing this library, it just fits my needs perfectly! Switching to dagre from a not-so-complete d3 layout took less than an hour!

In order to support actions when clicking on nodes it would be great if I could attach html content or a callback function to nodes, something like:

dagre.nodeOnClick(myCallback);
// later:
function myCallback(target) {...}

Allowing HTML content in the SVG could be used to provide the same functionality.

Thanks a lot,
Moritz

Graphviz allows "HTML strings" in the dot language spec. HTML strings are enclosed in angle brackets: <...>

We should track graph rendering time in the interactive demo.

Hey hey,

we're using dagre.js for quickly layouting inline declarative-style graphs in a MediaWiki wiki. This works quite well, but there's one issue with layout.

When we have lots of different node widths, there is a lot of variation in node center x positions. You can see this here:

(This is also live at http://www.sewiki.de/)

I think this would visually look much more clean if all the center nodes were aligned exactly below each others.

One way of implementing that would be to align the lanes. In that case even "Synchrone Vorlesung" would have the same center x as "Technische Infrastruktur" and "Grillfest" the same as "Räume für...", in addition to all center nodes being aligned.

An alternative would be to just align "continuous flows". This would mean that all the nodes in the middle of the graph would get the same center x values.

I'm not sure if that explanation was clear. If not, please tell me and I'll try to draw a picture. :)

Thanks a lot!
— Florian Gross

There are a number of unnecessary bends in the inner segments of this graph.

I wanted to give you a heads up about UglifyJS and Safari 6.0.1 (Webkit 536.26.14). I was seeing a graph drawing issue in Safari 6.0.1 on a mac. Took me a long time, but I narrowed it down to the uglified version of dagre.util.intersectRect(). I was getting back bogus y values for some calls to this function for a large graph (strange!).

If I add the option --no-seqs to the uglify command used to generate dagre.min.js, the problem goes away! I also experimented by breaking out just the intersectRect function and uglifying only that code with --no-seqs, and the problem goes away. I have not seen this issue occur in any other browser/webkit version, including Safari 5.x.

I'm not really looking for any action here, I just thought I would share my findings. Maybe using the --no-seqs option would be safer.

Paul

Missing 'var' for the following locals in position.js:

prevLayer, currLayer, mid, alignment

One of the cool parts about having an HTML label within a node is you can do all sorts of dynamic HTML stuff like having content collapse and expand with click interactions, auto-growing text areas, etcetera. Unfortunately these things would likely cause the node's size to grow or shrink. It would be super cool if we could detect the changing size of a node and incrementally change the graph layout to fit the new content.

I'm not sure how to automatically tell when the size of the HTML in a node has changed (once it's been displayed) but perhaps for now there could be some sort of function to call to just refresh the sizes (or the size of a particular node) (which could be called at the end of java script interactions which are known to change the size of the HTML.

Also, thanks for the continued great work on this! I've been watching the progress but unfortunately unable to do much in-depth poking as unfortunately I've been busy doing my day job!

https://github.com/cpettitt/dagre/blob/master/demo/demo-d3.html#L161-L189 – to balance labels, rects and dagre node coordinates, we use negative offsets currently. It's pretty difficult to programmatically navigate resulting SVG groups tree.

Instead of that we can use following approach:

# Use relative positioning, skip setting x,y for rects
# and set them equal to padding for labels
labels.each (d) ->
  bbox = @getBBox()
  d.bbox = bbox
  d.width = bbox.width + 2 * padding
  d.height = bbox.height + 2 * padding

rects
  .attr("width", (d) -> d.width)
  .attr("height", (d) -> d.height)

labels
  .attr("x", (d) -> padding)
  .attr("y", (d) -> padding)

# Use calculated dimensions to position node properly
nodes.attr "transform", (d) ->
  "translate(#{d.dagre.x - d.width/2},#{d.dagre.y - d.height/2})"

I believe most of dagre consumers will just copy your demo code to start from so it's probably makes sense to improve it :). I also think it's a bit easier to read and understand :).

The down-right position alignment is broken.

digraph {
graph [debugPosDir="down-right"]
 A -> B -> C; D -> B -> E; F -> B -> G
}

Compare with:

digraph {
graph [debugPosDir="up-right"]
 A -> B -> C; D -> B -> E; F -> B -> G
}

digraph {
graph [debugPosDir="down-left"]
 A -> B -> C; D -> B -> E; F -> B -> G
}

digraph {
graph [debugPosDir="up-left"]
 A -> B -> C; D -> B -> E; F -> B -> G
}

down-right aligns B with D, but it should be aligned with F.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.4692

digraph {
    graph [debugPosDir="up-left"]
    A-> B -> C -> D;  B -> D; C [width=280]
}

In the above input the edge (B, D) does not properly route around node C, which is made to be quite wide. Instead the edge has a dummy node inside C.

Exact integration details need to be fleshed out.

Ideally we could use CSS for styling and width / height detection. Then the rendering work for D3 becomes very simple: we should need to provide only the coordinates for nodes and edges.

Suggestions / D3-specific feature requests? Please add a comment!

The current ranking algorithm could be improved (though it finds reasonably good solutions). The graphviz ranking algorithm uses network simplex to reduce the number of dummy nodes required to render a graph.

This is an example of a graph that could be improved with a better ranking algorithm. The node "15" should appear lower in the graph (on the same rank as "8").

Currently when we drag nodes we don't try to recalculate the intersection between the edge and the node.

For example, it's possible to drag a node below another node and cause the edges between those nodes to cross over the moved node. If we rerun the intersection function then the edges will intersect the moved node on the top after the move.

We need a perf test suite as we start to look at some optimizations. Using something like Haskell's criterion in Javascript would be awesome.

For this graph, the order of the nodes is switched for the down-right alignment. This appears to be an issue with horizontalCompaction.

We had subpar support for self-loops before switching to d3. During the transition we removed all support for self-loops. When we add them back we should support labels on self loop and otherwise treat self loop edges as a proper element of layout. Most likely we'll need something like constraints to place the loop edge on the same rank as the node.

Label with one whitespace is ok:

digraph {
    A [label=" "];
}

... but node with empty label fails.

digraph {
    A [label=""];
}

SyntaxError: Expected comment, identifier or whitespace but "\"" found.

I thought string in dagre should behave like regular string.

This involves a couple of changes, which we may want to break out into separate tickets:

• Adding subgraph support to the parser
• Making changes to enable cluster layout during the order and positioning phases

I think that having our space to talk about the future of Dagre, provide help and feedback about it, etc. would be useful to improve the project.

This change involves building some abstraction for handling shapes. In particular, we need the shape to take a rectangle it must surround and have it give us width and height. During edge layout, we also need to determine where an edge intersections the boundary of the shape.

Looks like another positioning (horizontalCompaction) related issue. This graph has the edge from (I, F) pass through the G node. Note that the large widths for nodes A and E are necessary to get this broken positioning.

Currently we will return a control point for each layer in the graph. Since we're using the Brandes-Köpf positioning algorithm we can be sure that there will be a maximum of two bends and thus we need at most two control points.

One consideration is label placement. Our label placement scheme is currently pretty naive. The one change we'll need to make is to find the midpoint when there are two control points - previously we'd just try to align with the center control point.

Currently we can drag nodes and edges in the D3 demo. One nice improvement would be the ability to change the size of the middle segment for edges that have 2 bends. This would allow the user to place nodes closer than they were with the original rendering while keeping a good edge shape (e.g. monotonically increasing (decreasing) in y).