Graphviz (Sugiyama) layout.

[mbostock]

Something along these lines: http://www.graphviz.org/Documentation/TSE93.pdf

[jasondavies]

Also may be of use: http://research.microsoft.com/pubs/64284/gd2007-glee.pdf (describes methods used in MSAGL).

Bundled edge routing would also be nice: http://research.microsoft.com/en-us/um/people/holroyd/papers/bundle.pdf

[kbrock]

I found Mike's post so informative, that I wanted to include with this thread

The algorithm that you are describing is probably the one by Sugiyama: K. Sugiyama, S. Tagawa and M. Toda, “Methods for Visual Understanding of Hierarchical Systems”, IEEE Trans. Systems, Man, and Cybernetics 11 (1981), 109–125. We haven't implemented such a layout in D3, yet, but it's definitely possible. There are a few slides on how it works here:

http://hci.stanford.edu/courses/cs448b/w09/lectures/20090204-GraphsAndTrees.pdf

Another algorithm to consider is Dig-CoLa by Dwyer et. al:

http://www2.research.att.com/~north/papers_videos/pdf/DBLP-conf-infovis-DwyerK05.pdf

Although, I also quite like Tim Dwyer's more recent paper on constrained graph layout, which motivated the implementation of D3's force layout, which can easily be extended with custom constraints:

http://www.csse.monash.edu.au/~tdwyer/Dwyer2009FastConstraints.pdf

More of Tim's work here:

http://www.csse.monash.edu.au/~tdwyer/

Mike

(--Keenan)

[reconbot]

I'm working on replacing a graphviz generated png with a proper user interface and interactive graph. I'd love to see this too.

[kimgr]

I'm trying to visualize a dependency network of 7500 nodes and 35000 edges, so a layout that helps with incrementally drilling into the graph contents would be much appreciated.

[reconbot]

@mbostock you mentioned adding constraints (I assume on the tick event) like those mentioned in Tim Dwyer's "Fast Constraints" might be easy. I'm not sure I agree, this kind of math is new to me. =p

From what I see, barring a new Sugiyama layout a few "core" constraints for the fore directed graph would be welcome. (From the pdf - awesome read btw)

• Oriented Directed Edges
• Circular cycles
• Non-overlap of Convex Polygonal Node and Cluster Boundaries

And I suppose clustering in general.

I also think the gravity might interfere with some of these constraints (especially the oriented edges) so maybe some other way of orienting a "top level" node towards a point of the grid? (say the top middle)

I have no idea if I'm barking up the wrong tree =)

[ghost]

Hello Mike,
I'm hanging out for this layout. Have you been able to look into it at all ?
Thankyou.
Andrew W

[mbostock]

No, I haven't had a chance to work on it.

[ghost]

Thanks for the reply. I'll start to dive into it, but I'm not a JavaScript
guy.
Regards
Andrew W

On Wednesday, May 30, 2012, Mike Bostock wrote:

No, I haven't had a chance to work on it.

---

Reply to this email directly or view it on GitHub:
#349 (comment)

[reconbot]

@awilliman01 I am! but I'm not a "graphing/math theory guy", I'm more then happy to collaborate. If you can help dissect some of the existing Sugiyama layout code or plan out how to process the data from the whitepaper I can work it in to a d3 layout object.

I started attacking this from the whitepaper and quickly got lost, so I went at it from graphviz's implementation and quickly got lost. Barring a good teacher, I either need a more similar system (here is some data and here are some x,y coordinates) or a more similar language (my c/c++.. is not good) to port from.

[ghost]

Hi Francis,
Great !
I know a bit of Python though, so I was going to approach the solution
indirectly by first understanding the theory through a python mockup.
I was going to take something like force.js as the way to a layout in d3,
and hammer the logic into this structure. I am sure to struggle in the
last piece.
I'll drop a line to you, mostly likely in a week or so, with where I'm up
to.
Looking forward to it.
Andrew W

On Thursday, May 31, 2012, Francis wrote:

@awilliman01 I am! but I'm not a "graphing/math theory guy", I'm more then
happy to collaborate. If you can help dissect some of the existing Sugiyama
layout code or plan out how to process the data from the whitepaper I can
work it in to a d3 layout object.

I started attacking this from the whitepaper and quickly got lost, so I
went at it from graphviz's implementation and quickly got lost. Barring a
good teacher, I either need a more similar system (here is some data and
here are some x,y coordinates) or a more similar language (my c/c++.. is
not good) to port from.

---

Reply to this email directly or view it on GitHub:
#349 (comment)

[ghost]

Where can one find the original paper? Is it only available from IEEE?

[reconbot]

The first link in this thread should be it. http://www.graphviz.org/Documentation/TSE93.pdf

[ghost]

Thanks, I was actually talking about Sugiyama's paper, but this is graphviz's dot algorithm paper, and the one I probably should be reading anyway. It was here all along !

[ls233]

I'm really looking forward for the release of the D3 implementation of the layered network layout. I need to present a mid-size network (up to 30 nodes) in a browser. The nodes are distributed among time slices that need to be drawn hierarchically. I don't find the graphviz functionality sufficient for my needs.

[reconbot]

@awilliman01 did you have any success with the python mockup?

[ghost]

I have started to look into it, but I have been working on a few higher priorities. Sorry for the delay.

[reconbot]

Don't worry @awilliman01 you don't work for us. However can you share some notes on how you intend on going about it?

[whitequark]

I'd love to see this in d3, too!

[ghost]

The good thing about the Sugiyama layout is that it is actually a series of
independent steps, which make it a little easier to get you head around
each one.

My approach is/will be:
Understand the steps/logic by reading the various papers and source code
that's out there.
I'm a big fan of the web2py framework and I've been using that as my
backend data source for my prototype d3 work to date. My data is in a
database and I'm using web2py to extract the data and make available a json
resource. Any layout work will be in the python controller (mvc) piece.
I've been initially toying around with the force layout as a start point
but feeding it predetermined x,y coordinates.
My poor mans layout so far is to workout the start and end points, stretch
them apart to either ends (fixed), and let the force layout work out the
rest. I will progressively work through each of the sugiyama steps to
fully specifiy the layout.

graphviz also allows you to have grouped clusters, picture a pack hierarchy
http://mbostock.github.com/d3/talk/20111116/pack-hierarchy.html to define
the clusters with a force layout to link the nodes. However, I'll leave
that idea for a later day.

My progress is slow so far as it is a low priority against other tasks, but
I'll slowly chip away at it. I'm also learning d3 as I go.

On Thu, Jul 5, 2012 at 4:18 PM, Peter Zotov <
reply@reply.github.com

wrote:

I'd love to see this in d3, too!

---

Reply to this email directly or view it on GitHub:
#349 (comment)

[ghost]

Hi Francis,
I replied to the last email on the list, which was to Peter, not yourself.
If you look at the Issues list you'll see my reply.

On Wed, Jul 4, 2012 at 9:32 AM, Francis <
reply@reply.github.com

wrote:

Don't worry @awilliman01 you don't work for us. However can you share some
notes on how you intend on going about it?

---

Reply to this email directly or view it on GitHub:
#349 (comment)

[cpettitt]

FWIW, I'm working through the graphviz paper right now for a javascript project I'm working on in my spare time. It's not too far along yet - I've got an initial ranking algorithm complete - but since it is up on github, I thought I'd share it if anyone is interested in following or collaborating. Repo: https://github.com/cpettitt/dig.js.

My goal is to do layout via the algorithms in the paper and then produce a data structure that is usable through d3, since I'm using d3 for other visualizations.

[reconbot]

I'd be happy to help. Its not too obvious to me where to find the relevant code though. What needs doing?

[cpettitt]

Awesome. So here's where I'm at with the 4 phases (from http://www.graphviz.org/Documentation/TSE93.pdf):

1. rank - very basic start. Acyclic + initRank are done, but network simplex is missing.
2. ordering - mostly done. I'm using the barycenter heuristic.
3. position - not started
4. splines - not started

So, work on any of #1, #3, or #4 would help drive the project forward.

I came across a paper with some interesting ideas (and a summary of the graphviz paper), but it's probably a longer term improvement: http://emis.library.cornell.edu/journals/JGAA/accepted/2005/EiglspergerSiebenhallerKaufmann2005.9.3.pdf.

Most of the code specific to graphviz layout is in src/dig/dot/layout.js and test/dig/dot/layout-test.js.

Feel free to coordinate over email. My current thinking is to make a dash through #3 and #4 and then fill in with better heuristics after the pipeline is complete.

[cpettitt]

Thought I would post an update:

I have a dot language parser, and I can do layouts of nodes (edges aren't done yet). Here's a simple gist that shows an example of D3 + dig.js: http://bl.ocks.org/3663170. It's still a work in progress and is likely to have bugs :).

[ghost]

Great work, Sorry I haven't replied earlier. I'll download your files and take a look, I've been working through the paper but unfortunately I don't have much to show so far. Hopefully I can add to what you've done.

[cpettitt]

No worries - I myself have had very limited time to work on this. So, I have straight edges in now, along with a dynamic renderer: http://bl.ocks.org/3671618. You can change the graph description in the text box and it will re-render on the fly.

I could definitely use help on the D3 integration side. It would be slick if we could get the size of the text labels (using something like getBBox?) and set it as "width" and "height" attributes on the nodes in the graph. It would also be nice to shorten the arrow heads so that they stop short of the shape bordering the text.

It looks like I still have some work to do around optimizing the horizontal placement, but at least we have something with which we can iterate.

[robopeter]

Hey cpettitt! Nice work on this so far! I am really interested in seeing this capability in D3; possibly while allowing nodes to have a size and contain full fledged HTML within the SVG through the use of foreignObjects. I was looking around your github account and couldn't help but notice your dagre project which looks like it's a little bit further along than this feature in D3 and a great start for for working on this. I was curious how hard it would be to add HTML node support to your dagre project and managed to whip up the following. I'm new to GIT (I'm more of a mercurial guy) so I don't know the proper way to send to you so I've included it as a diff below.

diff --git a/demo.html b/demo.html
index 7386d29..2e3f0fd 100644
--- a/demo.html
+++ b/demo.html
@@ -17,7 +17,7 @@ h2 {
 <textarea id="input" rows="5" cols="80" style="display: block" onKeyUp="tryDraw();">
 /* Example */
 digraph {
-    A [label="A Big Source!", fontSize=25];
+    A [label="<div>A Big <span style='color:red;'>HTML</span> Source!</div>", fontSize=25];
     C [fontColor=red];
     E [label="A blue sink!", fontName=arial, fill="#aaccff"];
     A -&gt; B -&gt; C [color=green, strokeWidth=3];
diff --git a/src/pre-layout.js b/src/pre-layout.js
index ad55049..8cc51e7 100644
--- a/src/pre-layout.js
+++ b/src/pre-layout.js
@@ -56,13 +56,13 @@ dagre.preLayout = function(g) {
     // The font size to use for the node's label
     defaultInt(attrs, "fontSize", 14);

-    var text = createTextNode(u);
-    svg.appendChild(text);
+    var svgNode = createSVGNode(u);
+    svg.appendChild(svgNode);

-    var bbox = text.getBBox();
+    var bbox = svgNode.getBBox();
     attrs.width = Math.max(attrs.width, bbox.width);
     attrs.height = Math.max(attrs.height, bbox.height);
-    svg.removeChild(text);
+    svg.removeChild(svgNode);
   });

   g.edges().forEach(function(e) {
diff --git a/src/render.js b/src/render.js
index d31bdf7..0abcb5b 100644
--- a/src/render.js
+++ b/src/render.js
@@ -54,8 +54,14 @@ dagre.render = function(g, svg) {
                                   "stroke: " + u.attrs.color].join("; "));
       group.appendChild(rect);

-      var text = createTextNode(u);
-      group.appendChild(text);
+      var svgNode = createSVGNode(u);
+      if(svgNode.nodeName == "foreignObject"){
+        svgNode.setAttribute("x", -(u.attrs.marginX + u.attrs.width / 2 + u.attrs.strokeWidth / 2));
+        svgNode.setAttribute("y",  -(u.attrs.marginY + u.attrs.height / 2 + u.attrs.strokeWidth / 2));
+        svgNode.setAttribute("width", u.attrs.width + 2 * u.attrs.marginX + u.attrs.strokeWidth);
+        svgNode.setAttribute("height", u.attrs.height + 2 * u.attrs.marginY + u.attrs.strokeWidth);
+      }
+      group.appendChild(svgNode);
     });
   }

diff --git a/src/util.js b/src/util.js
index b20cf18..aa22177 100644
--- a/src/util.js
+++ b/src/util.js
@@ -8,6 +8,32 @@ function createSVGElement(tag) {
  * Performs some of the common rendering that is used by both preLayout and
  * render.
  */
+function createSVGNode(node, x){
+  if(node.attrs.label[0] == '<'){
+    return createHTMLNode(node, x);
+  }else{
+    return createTextNode(node, x);
+  }
+}
+
+function createHTMLNode(node, x){
+  var fo = createSVGElement("foreignObject");
+  var div = document.createElementNS("http://www.w3.org/1999/xhtml", "div");
+  div.innerHTML = node.attrs.label;
+  div.setAttribute("id", "temporaryDiv");
+  var body = document.getElementsByTagName('body')[0];
+  body.appendChild(div);
+  var td = document.getElementById("temporaryDiv");
+  td.setAttribute("style", "width:10;float:left;");
+  fo.setAttribute("width", td.clientWidth);
+  fo.setAttribute("height", td.clientHeight);
+  body.removeChild(td);
+  div.setAttribute("id", "");
+  
+  fo.appendChild(div);
+  return fo;
+}
+
 function createTextNode(node, x) {
   var fontSize = node.attrs.fontSize;
   var text = createSVGElement("text");

[cpettitt]

Quick update. I've integrated with d3 in the latest version of dagre. I'll be doing incremental improvements to the layout algorithms (edge labels, clustering, better crossing minimization, etc). The rendering / d3 side could probably use some attention from someone more knowledgeable about d3 and css.

Here are a few examples:

Inline D3
Interactive (dot)
Miserables.json

[ksiomelo]

you're doing a great job cpettitt!! The dagre layout works very well for some cases. I just started using it, and I might work on some crossing minimization issues it has.

[cpettitt]

Thanks! Crossing minimization would definitely benefit from some attention. If you can share graphs that demonstrate too many crossings that would also be helpful - we could track them as tickets in dagre.

[mimicimim]

Hi, mbostock. What the progress for Graphviz (Sugiyama) layout now? Thanks.

[tunnij]

Cpettit - good stuff. In terms of crossing in your d3 example, the 'last-ack' node should probably be on the right side of the 'closing' which would get rid of your crossings in that example. I'll try and take a look over the next few days but that's a good example to try and look at. Would also be worth comparing vs the actual graphviz implementation.

[cpettitt]

Thanks for taking a look @tunnij. In the latest code (master on github) that crossing doesn't occur anymore. I'm sure there is more than can be done to minimize crossings though. I'm currently working on ordering constraints in wip/cluster, which adds some restrictions to ordering (based on Forster's A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction paper) - like locking us into using a barycenter heuristic. Its possible that adding the extra dummy nodes for edge labels after ordering would improve things further, but I haven't had time to investigate.

[kbrock]

wow @cpettitt this is beautiful. The demo-d3 looks so similar to other d3 code that it makes the code very approachable.

thanks

[ArgentiApparatus]

I am currently taking a stab at implementing a something very similar for a descendancy chart (people, pairings and children) . In this case the graph is guaranteed to be acylic and directed, and people and pairings can be relatively easily sorted into layers.

In my design I'm separating the layering, ordering and positioning phases into different 'sub-layouts'. I think it would be nice if a native D3 implementation did the same.

I think it would be beneficial for users if they could choose sub-layouts to use, for instance: implement their own layering and use D3 ordering and positioning.

[mbostock]

Adding another related solution to this thread, cola.js (WebCoLa): http://marvl.infotech.monash.edu/webcola/

Here’s an example with a downward edge constraint: http://marvl.infotech.monash.edu/webcola/examples/downwardedges.html

[gaitat]

Just wondering what is the status of the Sugiyama layout in d3

thank you

[kbrock]

Hello @gaitat

The main 2 javascript Sugiyama layout entries I use are:

• http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html
• https://github.com/mdaines/viz.js/ ( http://www.webgraphviz.com/ )

That first one is very d3 friendly, just not as dynamic as we've grown accustomed to. Hard for anything to reach the fluidity of d3.

[magneticnorth]

Not sure if this thread is comatose already,but if anyone is implementing, you would want to at least look at more recent techniques for layered graph crossing reduction and coordinate assignment, like this work of Brandes and Köpf. http://algo.uni-konstanz.de/publications/bk-fshca-01.pdf There may be others from the same lab. Bachmaier et al had a sifting algorithm that seems quite effective and might reduce the problems of quadratic increase in graph size due to creation of virtual nodes; see http://www.emis.de/journals/JGAA/accepted/2011/BachmaierBrandenburgBrunnerHubner2011.15.5.pdf
Stephen North north@graphviz.org

[gaitat]

thank you very much for your suggestions.

[whitequark]

We've solved this a long time ago using dagre, e.g. see https://github.com/evilmartians/furnace-xray/blob/master/lib/furnace-xray/app/assets/javascripts/lib/drawer.js.coffee

[cpettitt]

Dagre uses Brandes and Köpf's paper (with a few minor fixes), and also took a huge amount of inspiration from Dr. North's paper, "A Technique for Drawing Directed Graphs". There would be no dagre without the work of Gansner, Koutsofios, North, and Vo. I've read Bachmaier's paper but haven't implemented it - dagre uses a barycenter strategy for crossing minimization.

[kocokolo]

Hello @ALL ,I am using https://github.com/OpenKieler/klayjs to do this job and that meet my need .

[ericmiao]

Really appreciate the effort here from cpettitt, webgraphviz, webcola, klayjs, ... etc.

Can I ask what is the latest status? There seem to be many excellent solutions here with external code base, yet I'd really like to see d3 to have its own layout engine to cover this, either from one of these solutions or come up with its own, I don't mind using any of these, as long as it's well integrated.

Is there any plan for this? Anyone tried to send @mbostock any git pull? Or @mbostock has any concerns or ideas of any better alternative?

[testn]

I also came across https://github.com/mstefaniuk/graph-viz-d3-js

[waldyrious]

@mbostock for reference, what exactly was the reason this was closed?

[mbostock]

I bulk-closed all open D3 issues as any active issues should now be tracked in the appropriate D3 sub-repository.

Also I have no immediate plans to implement this specific functionality, and it makes perfect sense for it to be implemented as a D3 plugin.

[waldyrious]

it makes perfect sense for it to be implemented as a D3 plugin.

I was wondering if https://github.com/mstefaniuk/graph-viz-d3-js or https://github.com/cpettitt/dagre-d3/ could be converted into such a plugin. /cc @mstefaniuk, @cpettitt

[mstefaniuk]

Graphviz renderer is component currently using D3 v3. It has huge dependency (in size) of viz.js, it launches WebWorker for effective rendering and in fact parses xdot output to create data for d3.js input. I'm not sure if it can be considered as D3 plugin.

[magjac]

@waldyrious: I just released the new d3-graphviz plugin if you're still interested. It's also based on Viz.js.