tree layout with variable-sized nodes

[Chris Maloney]

I've been working on this problem for about a week, and just discovered this github issue / feature request, https://github.com/mbostock/d3/issues/1992, yesterday.

As I mentioned on that ticket, I've got it mostly working, see this demo: http://klortho.github.io/d3-flextree/. Nodes can vary in size in both x and y: I'm adding the ability to set nodeSize as a function that returns [x,y].

I also mentioned on that ticket a design problem with regards to reconciling this with the separation() function.  In a nutshell, the problem is this: separation return values are in "node size units". So:

  d3.layout.tree().separation(function() { return 1; }).nodeSize([10, 10]);

Gives you a tree in which nodes are properly spaced 10 units apart. This is because the tree is layed out first, using "node size units", and then scaled at the end. But if the node size is variable, then what are "node size units"? I.e., how should the layout algorithm work for the following?

  d3.layout.tree().separation(function() { return 1; }).nodeSize(function() { return [10, 10]; })

The layout algorithm can't know that the node size is a constant -- can't assume anything about the values for any given node.  It would be more convenient if we could specify them in the same, drawing units:

  d3.layout.tree().separation(function() { return 10; }).nodeSize(function() { return [10, 10]; })

But that would break backwards compatibility.

Here's the solution that I've come up with. I want to throw it out, to get feedback. I decided to send it to this list instead of putting it on the GH ticket, in case the D3 authors don't appreciate me taking over that ticket.

The key point of the design is to use the size of the root node to define "node size units". Then, keep separation() working the same, for backwards compatibility, but add a new function, margin(), that is probably what people will want to use when nodes have a variable x-size.

Design constraints:

* Library needs to be backwards-compatible

* tree().nodeSize(function {return constant;}) should work exactly the same as tree.nodeSize(constant).

* Don't change the meaning/scale of the value returned by separation().

Design:

* Right now, whether or not size or nodeSize is used, the algorithm computes coordinates first in "node size units". Then, they are scaled at the end.

* Keep that policy, but now, a "node size unit" is the size of the root node.

* To do that, as part of wrapTree(), set x_size and y_size on every wrapper, regardless of the sizing scheme, in "node size units".

* In apportion(), keep the condition that every node is stepped if !variableNodeSize, even though maybe we don't need it, just to avoid potential pitfalls with floating point values not exactly matching

* The default separation function should:

    * If !variableNodeSize, do exactly what it does now

    * else access the wrapper nodes, and return 1/2 the sum of the two y_sizes, plus, if a.parent != b.parent, the node size y.

* That means it will need to be a closure -- its exact behavior depends on the value set on the root node of the tree. Is it okay to make the default function a closure?

* Add a margin(a, b, g) function for convenience, that allows the user to set the actual separation in the drawing units -- same units that nodeSize uses.

    * When it is set, separation() is not used (they are mutually exclusive)

    * During the algorithm's execution, margin() is used in place of separation, but it is rescaled to nominal "node size units"; so, instead of separation, use the value (a.x_size + b.x_size) / 2 + margin / root.y_size.

Any feedback is very welcome!

Thanks,

Chris

[Chris Maloney]

I finished this up, as a plugin (https://github.com/Klortho/d3-flextree), and as a fork of D3 with a pull request (https://github.com/mbostock/d3/pull/2571).

Demo here: http://klortho.github.io/d3-flextree/

Enjoy!

[timelyportfolio]

This is fantastic.  I look forward to working with it.  Thanks.

Kent

[Curran]

Great work!

[Suguru Ishizaki]

Thanks for posting your plug-in! I just found this post today, and this is exactly what I need, except that I am interested in using this for drawing a sentence diagram (like this one: https://upload.wikimedia.org/wikipedia/commons/f/ff/Argument2.jpg). So, I was wondering if this plugin can be used to draw a cluster diagram where all the leaf nodes (of varying size) are lined up at the bottom. I am guessing that I may need to make some minor changes to the source code of the plug in. Do you think that'd be a way to go, or should I consider creating my own. Any suggestions you may have would be appreciated. By the way, I am new to D3.

Thanks!

[Drew Winget]

Cola.js is another option, if you have more geometric/conceptual constraints in mind (as opposed to an algorithmic approach). http://marvl.infotech.monash.edu/webcola/

You can still use d3 for the data join, updates, and rendering. Cola will just calculate the layout parameters for you using a somewhat more hybrid conceptual model.

--
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/d/optout.

[Chris Maloney]

Hi, Suguru,

Thanks for the compliment. Glancing at your diagram, I'd say that yes, flextree would work fine, but I'm not sure it would be your easiest solution. D3 has a bit of a learning curve, and I'm not sure if you want to spend the time. 

You're layout problem is very simple, compared to the general one that flextree addresses. You could model the leaf nodes as having infinite (or very large) heights, so they's all have to fit side-by-side in the order they appear in the traversal.

But, the layout really is simple in this case, and you might be better off just hand-coding it, rather than trying to learn D3. Question: do you want it to be animated? D3 is good for animating dynamic data, because it lets you bind the data to the elements. 

Chris

--
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/O4hHCS-XXqY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to d3-js+un...@googlegroups.com.