d3 DAG visualization

[Robert Martin]

I know d3 has a number of beautiful built-in layouts but there doesn't seem to be one for a directed acyclic graph.

Does anyone know of good libraries to do this? Or, if I wrote something, would anyone else be interested?

Cheers,

Robert

[Jeremy Dunck]

On Tue, Jun 11, 2013 at 12:19 PM, Robert Martin <rdma...@gmail.com> wrote:

 Or, if I wrote something, would anyone else be interested?

I'd be interested in it.

[Christophe Viau]

I see this question more and more often. The challenge is in the automatic layered layout. I could collaborate on this if you want. Which algorithm should we start with?

--
You received this message because you are subscribed to the Google Groups "d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send an email to d3-js+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Christophe Viau]

There is an interesting implementation in Dagre, which is agnostic to the renderer: https://github.com/cpettitt/dagre/blob/master/src/layout/layout.js
Here is a discussion about it:
https://github.com/mbostock/d3/issues/349

We should maybe extract it as a layout?

[Casey Greene]

I'd also be interested in using this.

Thanks!

Casey

On Tue, Jun 11, 2013 at 7:33 PM, Casey Greene <Casey.S...@dartmouth.edu> wrote:

I'd also be interested in using this.

Thanks!

Casey

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH

[Johnson Chetty]

I would be interested too..
How do we go about working together on this?

[Christophe Viau]

The simplest way of doing it would be to turn the Dagre code into a D3 layout:
https://github.com/cpettitt/dagre/blob/master/src/layout/layout.js

I made a quick DAG generator for testing purpose. It generates an adjacency matrix and an adjacency list easy to turn into an object that can be fed to the layout we want.
http://bl.ocks.org/biovisualize/5365390

I will hunt for more ideas tomorrow with the Tulip team. I could also ask Tim Dwyer for algorithms. Here is a discussion about layouts:
https://github.com/mbostock/d3/issues/349

Once we choose the algorithm, we can share stuff on gist/bl.ocks/tributary and iterate.
Chris

[Robert Martin]

Well, I threw together a 1st approximation algorithm here:
https://github.com/bobbydavid/dag-visualization.git

It generates a DAG (size is configurable in dag.js), shows it using
d3.force, and using the new dag layout.

The dag layout algorithm is this:

1. Sort nodes topologically.
2. Set X-position on nodes to be the biggest parent's X-pos +1, or 0
if it has no parents.
3. Move X-positon to be min of children's X-pos -1 if it has children.
4. For each unplaced node N:
4.A. if no parents: Y-pos = nearestY(X-pos)
4.B. if >=1 parent P_i: Y-pos = nearestY(mean P_i X-pos)
4.C. while N is exactly 1 child C with exactly 1 parent N:
4.C.i. set C's Y-pos to N's Y-pos
4.C.ii. N = C

I think it could use improving. Probably it would be good to
explicitly list the visualization criteria like in the algorithm
behind d3.tree(). One idea I thought of would be a "who is joining
whom" function, to allow for situations where the dag has a concept of
a less important node joining up with a larger flow.

> You received this message because you are subscribed to a topic in the
> Google Groups "d3-js" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/d3-js/_jf_9z36hCo/unsubscribe?hl=en.
> To unsubscribe from this group and all its topics, send an email to

[Christophe Viau]

Pretty cool. I made a bl.ocks out of it for people to play with. Let me
see if I can improve it.
http://bl.ocks.org/biovisualize/raw/5801758/
Chris

[Robert Martin]

Here is a slightly improved version where nodes do a better job of finding their X-position.

https://bl.ocks.org/bobbydavid/raw/5841683/

One big problem still remains: sometimes lines go _through_ another node without touching it, and that is visually very confusing. I'm not quite sure how to resolve that problem.

an email to d3-js+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to the Google
Groups "d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send

an email to d3-js+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH
--
You received this message because you are subscribed to the Google Groups
"d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send an

email to d3-js+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups
"d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send an

email to d3-js+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to a topic in the
Google Groups "d3-js" group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/d3-js/_jf_9z36hCo/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to

d3-js+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to a topic in the Google Groups "d3-js" group.

To unsubscribe from this topic, visit https://groups.google.com/d/topic/d3-js/_jf_9z36hCo/unsubscribe.

To unsubscribe from this group and all its topics, send an email to d3-js+unsubscribe@googlegroups.com.

[Christophe Viau]

You could use bezier curves instead of straight lines
Chris

an email to d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to the Google
Groups "d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send

an email to d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH

--
Casey Greene
Assistant Professor
Department of Genetics
Institute for Quantitative Biomedical Sciences
Norris Cotton Cancer Center
The Geisel School of Medicine at Dartmouth
Hanover, NH
--
You received this message because you are subscribed to the Google Groups
"d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send an

email to d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups
"d3-js" group.
To unsubscribe from this group and stop receiving emails from it, send an

email to d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to a topic in the
Google Groups "d3-js" group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/d3-js/_jf_9z36hCo/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to

d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to a topic in the Google Groups "d3-js" group.

To unsubscribe from this topic, visit https://groups.google.com/d/topic/d3-js/_jf_9z36hCo/unsubscribe.

To unsubscribe from this group and all its topics, send an email to d3-js+un...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups "d3-js" group.

To unsubscribe from this group and stop receiving emails from it, send an email to d3-js+un...@googlegroups.com.

[Robert Martin]

I tried but it messed up the arrowhead orientations. They all would either point straight up or straight down...

[Christophe Viau]

You can explicitly set the orientation of your marker: http://bl.ocks.org/biovisualize/5369188
Chris

[Andrew W]

Great discussion, and thanks for the many examples.

Have a look at Issue 349 on the d3 wiki. The Graphviz (Sugiyama) layout was, I believe, the layout on which the work for dagre was based.

[Andrew W]

Oops, just saw your reference to it Chris. Anyway, I think it's worth a second mention.

[Dongke Jiang]

Maybe this dag would be ok.

https://github.com/jdk137/dag

在 2013年6月12日星期三UTC+8上午3时19分35秒，Robert Martin写道：