Chicken/egg problem with D3 tree

[RickB]

I'm trying to use the D3 tree to render a software dependency graph.
Functionally, it works just fine. However, the current implementation
seems to require that the height and width of the tree be
predetermined. Has anyone created a dynamic layout model for things
like trees and network diagrams that doesn't require that the
dimensions of the tree be known in advance?

It seems a rather severe limitation on the functionality...

Thanks,

Rick

[Justin Donaldson]

Typically, you create the data first, using one of the layout methods.  You should be able to extract values from this layout (such as the max tree depth, etc.), and then use that to set the height of the graph itself.

Typically, I try to make the graph scale to fit a 960px/500px area.  Then, if things get too cramped, I expand accordingly (hopefully I can just alter the height). 

Best,
-Justin

--
Justin Donaldson, BigML, Inc.
o: 313-31BIGML | c: 919-BUZZJJD

[RickB]

Hi, Justin.

Sounds encouraging, but can anything in the d3 layout package do those
calculations or do I have to do them myself? Are there accessors for
those metrics? It's a fairly non-trivial graph, so the calculation
process if I have to do it manually could be quite involved.

Thanks,

Rick

On Sep 11, 7:06 pm, Justin Donaldson <donald...@bigml.com> wrote:
> Typically, you create the data first, using one of the layout methods.  You
> should be able to extract values from this layout (such as the max tree
> depth, etc.), and then use that to set the height of the graph itself.
>
> Typically, I try to make the graph scale to fit a 960px/500px area.  Then,
> if things get too cramped, I expand accordingly (hopefully I can just alter
> the height).
>
> Best,
> -Justin
>

[Kyle Foreman]

The d3.layout.tree functions should be able to take care of the calculations for you: https://github.com/mbostock/d3/wiki/Tree-Layout

[Justin Donaldson]

The tree layout does take care of the specifics of the layout, but you still have to give it some height/width values to start from, or else it will use 1 by 1. 

I have a tree layout right now that defaults to 960 w x 500 h.  If the depth is greater than 25 (each depth level needs  ~20px) then I set the height to depth * 20.
You can also update this with transitions and animations.


-Justin

 

On Sun, Sep 11, 2011 at 5:12 PM, Kyle Foreman <kylef...@gmail.com> wrote:

The d3.layout.tree functions should be able to take care of the calculations for you: https://github.com/mbostock/d3/wiki/Tree-Layout

[Kyle Foreman]

You have to give it a default size for the entire layout or it'll default to 1x1, but that's not node specific, that's just the total size of the entire tree. You don't need to compute anything to choose those values.

[Justin Donaldson]

True, but I'm pretty sure this isn't Rick's problem.  He wants the graph dimensions to be dynamic, so that it can change depending on how many nodes are in the network.  This is probably for legibility reasons.

I'd still recommend extracting some of the dimensions from the tree.  E.g, get the max depth, and use it to help define a height.

var tree = d3.layout.tree()
   .size([w, h])
   .separation(function(a, b) { return (a.parent == b.parent ? 1 : 2) / a.depth; });

var nodes = tree.nodes(some_json);
var max_depth = d3.max(nodes, function(x) { return x.depth;});
var w = 960; // or, calculate the width based on the max branch width.
var h = Math.max(max_depth*100, 500);

Then, set the size to be some function of the max depth:

var tree = d3.layout.tree()
    .size([w, h])...

You can update the graph dimensions later on, but you'll need to completely recalculate the tree.

Hope that helps,
-Justin

On Sun, Sep 11, 2011 at 8:02 PM, Kyle Foreman <kylef...@gmail.com> wrote:

You have to give it a default size for the entire layout or it'll default to 1x1, but that's not node specific, that's just the total size of the entire tree. You don't need to compute anything to choose those values.

[RickB]

Well, we're getting closer...

It seems that max depth is actually representative of the maximum
*horizontal* depth of a single set of linked nodes, not related to
what the *height* of the effective tree will be. Looking at the
source for the tree layout, it seems that the necessary calculation
logic is probably in there, just masked in some fairly opaque variable
names like mod, vim, vop, sop, sip, sim, and som. Sorta like a Dr.
Seuss book... ;-)

If anyone can shed some insight on the internals of the layout
algorithm, I'm sure I can get there. Ultimately, my end goal can be
stated as simply resizing the layout container (parent SVG element)
and re-triggering layout so that each node has a horizontal space
allocation of a fixed amount (nH) and a vertical space allocation of a
fixed amount (nV).

On Sep 12, 12:53 am, Justin Donaldson <donald...@bigml.com> wrote:
> True, but I'm pretty sure this isn't Rick's problem.  He wants the graph
> dimensions to be dynamic, so that it can change depending on how many nodes
> are in the network.  This is probably for legibility reasons.
>
> I'd still recommend extracting some of the dimensions from the tree.  E.g,
> get the max depth, and use it to help define a height.
>
> var tree = d3.layout.tree()
>    .size([w, h])
>    .separation(function(a, b) { return (a.parent == b.parent ? 1 : 2) /
> a.depth; });
>
> var nodes = tree.nodes(some_json);
> var max_depth = d3.max(nodes, function(x) { return x.depth;});
> var w = 960; // or, calculate the width based on the max branch width.
> var h = Math.max(max_depth*100, 500);
>
> Then, set the size to be some function of the max depth:
>
> var tree = d3.layout.tree()
>     .size([w, h])...
>
> You can update the graph dimensions later on, but you'll need to completely
> recalculate the tree.
>
> Hope that helps,
> -Justin
>

[RickB]

Just wanted to let you all know that I came up with a fairly clean
solution. I had to hack d3.layout.js slightly, but it works pretty
cool.

Basically, instead of fitting all the tree nodes into predetermined
size (via the .size([w,h]) function), I added the ability to specify
the space to be allocated to each node via a new
function, .elementsize([w,h])

I then modded treeVisitAfter to look for the presence of either size
or elementsize, then act accordingly.

d3_layout_treeVisitAfter(root, function(node) {
if(size === undefined || size == null) {
node.x = (node.x - x0) * elementsize[0];
node.y = node.depth * elementsize[1];
}
else {
node.x = (node.x - x0) / (x1 - x0) * size[0];
node.y = node.depth / y1 * size[1];
}
delete node._tree;
});

Note also that is then a fairly trivial task to call d3.max on the
nodes x and y properties to determine the bounding box to use for
declaring an SVG element to render the layout (SVG width = max y +
element width and SVG height max x + element height).

[Justin Donaldson]

Nice hack.

Sorry that I forgot to mention... I was in the habit of drawing my trees oriented up and down, rather than left and right.  Tree depth was vertical for me.

The max depth is very easy to get, but the max width is harder, especially if you are changing the separation between nodes.

I think your way might be the best way to handle all of that, thanks.

Best,
-Justin

[Brennan Thompson]

Hey Rick,

Where exactly did you modify the library to accomplish this? I see a couple places that you may have done it. Also where does elementsize get set?

[RickBullotta]

Hi, Brennan.

Here are the tweaks (all in d3.layout.tree).  Also, when you instantiate a tree, you should set size to null and elementsize to your preferred size, as in:

  var tree = d3.layout.tree()

  .size(null)

  .elementsize([elementHeight,elementWidth])

  .sort(null)

  .children(function(d) {

       .........

  }

- Rick

Replace

      var hierarchy = d3.layout.hierarchy().sort(null).value(null), separation = d3_layout_treeSeparation, size = [ 1, 1 ];

...with...

      var hierarchy = d3.layout.hierarchy().sort(null).value(null), separation = d3_layout_treeSeparation, size = [ 1, 1 ], elementsize = [1, 1];

Replace:

      d3_layout_treeVisitAfter(root, function(node) {

        node.x = (node.x - x0) / (x1 - x0) * size[0];

        node.y = node.depth / y1 * size[1];

        delete node._tree;

      });

...with...

      d3_layout_treeVisitAfter(root, function(node) {

        if(size === undefined || size == null) {

     node.x = (node.x - x0) * elementsize[0];

     node.y = node.depth * elementsize[1];

        }

        else {

     node.x = (node.x - x0) / (x1 - x0) * size[0];

     node.y = node.depth / y1 * size[1];

        }

        delete node._tree;

      });

Add:

    tree.elementsize = function(x) {

      if (!arguments.length) return elementsize;

      elementsize = x;

      return tree;

    };

[Henry Rogers]

Thank you Rick, exactly what I was needing. I can pack custom node shapes, calculate tree bounds and zoom chart to fix viewport.

[David McClelland]

And then a newer version of D3 is required for the platform and the tree widget breaks, and I come here because I have good Google-foo.

Developer supporting Rick's code 5-6 years later (for real)