d3 / d3-hierarchy Goto Github PK
View Code? Open in Web Editor NEW2D layout algorithms for visualizing hierarchical data.
Home Page: https://d3js.org/d3-hierarchy
License: ISC License
2D layout algorithms for visualizing hierarchical data.
Home Page: https://d3js.org/d3-hierarchy
License: ISC License
This is a little difficult to remember:
root.eachBefore(function(d) {
var h = 0;
do d.height = h;
while ((d = d.parent) && (d.height < ++h));
});
We could compute it by default, as we do for depth. Or perhaps have a node.computeHeight() method.
If you do the simple thing and subtract a fixed amount of padding from the computed cells in a partition layout, you introduce distortion because small cells are disproportionately affected. It might be nice if the partition layout knew about padding, so that it could preserve the relative areas of padded cells.
See #19 for a description of a similar problem with the treemap layout.
Rather than taking a tree as input (and a children accessor), it might be simpler if we took a table of nodes as input with id and parent accessors. For example:
id | parent | value |
---|---|---|
add | methods | 593 |
AgglomerativeCluster | cluster | 3938 |
AggregateExpression | query | 1616 |
analytics | flare | |
AnchorControl | controls | 2138 |
and | methods | 330 |
And | query | 1027 |
animate | flare | |
Arithmetic | query | 3891 |
ArrayInterpolator | interpolate | 1983 |
Arrays | util | 8258 |
ArrowType | render | 698 |
AspectRatioBanker | optimization | 7074 |
I am working with some large-ish hierarchies, with over 10,000 nodes, and a bit of custom data. Too large to be in the DOM all at once, so they need to be queried. I am finding that I often need to be able to traverse a hierarchy, starting from a given node, looking for a node that satisfies some condition. This is straightforward to do manually, but in results in a lot of for
loops, which aren't really in the D3 idiom. The existing each-* methods have the slight performance disadvantage that there is no way early-exit the loop once the target node has been found. It might be nice to have that option as an API refinement.
Another option could be jQuery-esque .closest
and .find
methods that looked up and down the hierarchy, respectively, and returned the first "matching" node.
Thanks.
What if this:
var root = treemap(data);
Were equivalent to this:
var root = treemap(d3.hierarchy(data).sum(function(d) { return d.value; }));
You might even sort by default, like this?
var root = treemap(d3.hierarchy(data)
.sum(function(d) { return d.value; })
.sort(function(a, b) { return b.value - a.value; }));
And perhaps this:
var root = treemap(data, function(d) { return d.size; });
Could be equivalent to this (sorting TBD):
var root = treemap(d3.hierarchy(data).sum(function(d) { return d.size; }));
Which is a bit like how the d3-array methods take value accessors. It would add a bit of code to each hierarchy layout, but it feels like it might be convenient for the common case… albeit less self-describing.
We should be able to generate stable layouts for either squarified or binary treemaps (and slice, dice, and sliceDice, but that’s trivial since those tiling methods are inherently stable). The stable update should be independent of the tiling method, since the relative positions of the cells are fixed for a stable update. Ideally, it could infer the adjacency of siblings by just looking at the previously-computed positions—then the tiling methods wouldn’t be required to explicitly enumerate the rows and their orientation.
Perhaps there should be a treemap.update method which recursively modifies the given root? Or, it could take a root, and then return a clone with the updated layout.
Currently we compute the enclosing circle using none of the information previously gained from packing siblings, but surely it would be more efficient to only consider circles in the front chain when computing the enclosing circle.
Supersedes d3/d3-shape#28.
I'm using the new v4 treemap layout with a squarified tile.
The ending at the bottom righ corner seems strange, whats the issue here?
<script>
var width = 800,
height = 680;
var format = d3.format(",d");
var color = d3.scaleOrdinal()
.range(d3.scaleOrdinal(d3.schemeCategory10).range()
.map(function(c) { c = d3.rgb(c); c.opacity = 0.6; return c; }));
var stratify = d3.stratify()
.parentId(function(d) { return d.id.substring(0, d.id.lastIndexOf(".")); });
var treemap = d3.treemap()
.size([width, height])
.padding(1)
.round(true)
.tile(d3["treemapSquarify"] ); // Squarify, Slice, SliceDice, Binary
d3.csv("product_view.csv", type, function(error, data) {
if (error) throw error;
var root = stratify(data)
.sum(function(d) { return d.value; })
treemap(root);
d3.select("body")
.selectAll(".node")
.data(root.leaves())
.enter().append("div")
.attr("class", "node")
.attr("title", function(d) { return d.id + "\n" + format(d.value); })
.style("left", function(d) { return d.x0 + "px"; })
.style("top", function(d) { return d.y0 + "px"; })
.style("width", function(d) { return d.x1 - d.x0 + "px"; })
.style("height", function(d) { return d.y1 - d.y0 + "px"; })
.style("background", function(d) { while (d.depth > 1) d = d.parent; return color(d.id); })
.text(function(d) { return d.id.substring(d.id.lastIndexOf(".") + 1).split(/(?=[A-Z][^A-Z])/g).join("\n"); })
.append("div")
.attr("class", "node-value")
.text(function(d) { return format(d.value); });
});
function type(d) {
d.value = +d.value;
return d;
}
</script>
When a squarified layout is first calculated, partition decisions are cached on the tree nodes. If one then updates treemap.tile
to use a squarified layout with a different target aspect ratio, this new ratio is effectively ignored in favor of the cached data. While stable layout is valuable in many situations, it is not always desired. In the case of assigning a new tiling method, my expectation was that this assignment would (by default) override any cached results. Perhaps the API could include a mechanism to make this determination user controllable.
This issue affects changes to the treemap.size
parameter as well. Sometimes one may want the treemap to re-partition on changes of width/height rather than stay stable.
For now, it appears that the resolution is to either generate a new hierarchy instance or walk the existing hierarchy and clear out the _squarify
caches.
Related d3/d3#1145 d3/d3#1929.
Also this was my “#1” regret on my AMA.
Test case incoming.
Aside from making it more extensible, it would be handy to have the ability to keep the parentId
& id
out of the node's data
property.
I'm working on it at the moment, just raising the issue.
We need lots of tests.
It seems to be one of those JavaScriptisms that really infuriate me, but I will leave this as a suggestion.
The hierarchy
method fills the children
field with a list of children if any, and undefined
otherwise.
It seems to me that returning an empty list would be much more elegant and practical. For instance I could do:
// using ES5+ operators
node.children.map(...)
node.children.reduce(...)
Is there any good reason for not returning an empty list?
Good thing TypeScript with strictNullChecks
warned me...
Related d3/d3#1821.
Found a bug in treemapDice that calculates an incorrect k value. Since parent.value
includes the count of itself, k should be calculated as follows:
k = parent.value && (x1 - x0) / (parent.value-1)
rather than
k = parent.value && (x1 - x0) / parent.value
Found this bug since there were tiny gaps at the bottom of my partition map that was equal to size of the leaf node.
Currently nodes are returned in pre-order depth-first traversal. This means that siblings are adjacent and in their original order.
I believe it would be preferable to return nodes in breadth-first traversal order, by ascending depth. The root is first, as before, and then siblings are returned in the order defined by hierarchy.sort, defaulting to descending value. Thus, nodes at depth i + 1 are always drawn on top of nodes of depth i—not just their direct ancestors.
This could help avoid inconsistencies due to rounding error, e.g., when a child exceeds the bounds of its parent (related d3/d3#2685):
d.parent.x + d.parent.dx // 0.26717557251908397
d.x + d.dx // 0.267175572519084
Would it be possible to generalize the stable update of an existing treemap? Currently the squarify layout stores its arrangement in node._squarify, but it seems like it should be possible to infer the arrangement from the previous node positions, and simply rescale them to fit the new values.
The treemap implementation subtracts a fixed amount of padding from the computed node sizes. This is simple to implement but disproportionately affects the size of small nodes, since the relative area of the subtracted padding is much higher with a small node than a big node.
In d3-shape’s pie generator, we go to some effort to ensure that the relative areas of padded arcs are preserved. We don’t do that with the treemap layout, in part because I presume it is more challenging to implement, but it would be lovely if we could. A two-pass approach might be an acceptable if imperfect solution: compute the layout without padding, compute the area lost to padding for each cell, add this to the value for the cell, and then recompute the layout.
Perhaps I should start by visualizing the distortion using the Flare hierarchy as an example dataset.
Related d3/d3-shape#41.
Hi,
I was re-implementing the circle packing algorithm by Wang et al. in C, based on the old implementation in Protovis and noticed that you changed their algorithm so that each circle is put next to the previously placed circle instead of the location closest to the center of the plot. I assume it was intentional to keep nodes with the same color next to each other even so the final layout is less round, but more snail-shaped.
It's just a little modification to the code to change the placement according to the original algorithm, and I could provide it if desired (modified the big D3.js and it worked). Let me know..
Also: great work on D3 btw :)
cheers
Apparently, it only exists to support sticky treemaps, and we should design a better API for it.
Supersedes d3/d3-shape#27.
I think it puts the smallest cell in the top-left by default, now.
The problem is that the root isn’t constructed until you call treemap(data), which makes it hard to use the node API to compute things like node height. So… maybe we should change the hierarchical layouts to once again take a node as input rather than data, and use node.clone if you don’t want to mutate the data.
Related d3/d3#2536; see demo.
Hi,
how can I set the horizontal or vertical layout for the treemap independent of the width/height ration?
I would like to create a wide treemap with the fields appearing underneath thus the labels are better readable.
Screenshot 1 (wider than higher) should be like Screenshot 2 (higher than wider).
In the existing d3.stratify examples, it seems parent nodes must be included in the original CSV.
Example: http://bl.ocks.org/mbostock/9d0899acb5d3b8d839d9d613a9e1fe04
id,value
flare,
flare.analytics,
flare.analytics.cluster,
flare.analytics.cluster.AgglomerativeCluster,3938
It would be convenient if the first 3 rows in the above weren't required. In other words, this would be sufficient:
id,value
flare.analytics.cluster.AgglomerativeCluster,3938
flare.analytics.cluster.CommunityStructure,3812
flare.analytics.cluster.HierarchicalCluster,6714
flare.analytics.cluster.MergeEdge,743
The nodes flare
, flare.analytics
, and flare.analytics.cluster
would be created automatically in the resulting hierarchy. Currently running the stratify
function against the above CSV would throw an error like this:
Error: missing: flare.analytics.cluster
From this line of d3.stratify:
Line 47 in 8b4c396
if (!parent) throw new Error("missing: " + nodeId);
Related #7. It’s possible to do this with a dummy node, but I’m not sure that’s a good idea. Does it really make sense for internal nodes to have value in a pack layout? There’s typically a lot of wasted space due to the enclosing circle having greater area than the sum of all children, so it’s not clear that visualizing this internal node value would be meaningful.
When creating a custom bundle using rollup 0.36.1 and the treemap function exported by d3-hierarchy, I get the following error in the browser console:
Uncaught TypeError: Cannot create property 'y0' on number '1.618033988749895'
Which points to the following line:
https://github.com/d3/d3-hierarchy/blob/master/src/treemap/index.js#L20
It only happens when I initialize the treemap function. If I comment out the line treemap()
it bundles correctly.
import {treemap} from "d3-hierarchy";
export default function() {
treemap();
}
Not sure if this is a d3-hierarchy bug or a rollup bug, so I apologize if this issue is misplaced.
Related d3/d3#1821.
The squarified treemap layout hides metadata in node._squarify so that it can perform a stable update of a squarified layout. However, if node.sort is called in the interim, then the order of nodes change, breaking the meaning if node._squarify (which is currently one plus the index of the last node in the current row).
The desired behavior is that the squarified layout is remains stable even after sorting, effectively ignoring the sort. (The nodes would be reordered, but retain their relative positions.)
One way to fix this would be to store the rows as arrays of nodes rather than indexes, such that any reordering of the children does not affect the stored metadata.
What if, at each step, we evaluated all possible positions along the front-chain based on the resulting smallest enclosing circle? Would that be too slow?
This would be especially helpful to people using d3-stratify for the first time, such as forking an example like Tidy Tree and trying to input their own data.
Some ideas about what the text might be.
nodeId
nodeId
matches two parentsThe squarified treemap layout stores the squarified layout in node._squarify. This means you can clear the metadata to recompute a non-stable layout like so:
treemap(root.eachBefore(function(d) { delete d._squarify; }));
Yet this is non-obvious and not documented.
I know it’s pretty trivial, but I think it’d be convenient.
Node.prototype.links = function() {
var root = this, links = [];
root.each(function(node) {
if (node !== root) { // Don’t include the root’s parent, if any.
links.push({source: node.parent, target: node});
}
});
return links;
};
The first example under the node.sort(compare) contains the code snippet:
.sort(function(a, b) { return b.value - a.value; });
This should probably read:
.sort(function(a, b) { return b.data.value - a.data.value; });
as the sort function passes in nodes.
The change in 0.2.1 makes d3.packSiblings somewhat unpredictable, since the weighted centroid can drift an arbitrary distance away from the origin. It’d be better to translate everything back to the origin when we’re done. Although note that this step is not necessary for d3.pack, since that will compute the enclosing circle and translate to its center. We should probably have a private method for packing siblings that is separate from the public one.
It’d be nice to have an example which uses d3.nest to create a hierarchical visualization. For example:
var root = d3.hierarchy(data, function(d) { return d.values; });
It’d be nice to:
Perhaps treemap.padding should take a function, as in 3.x.
Related d3/d3#1876. Seems doable.
here is my code :
var svg = d3.select('#test');
var g = svg.append("g");
var root = null;
var tree = d3.tree().size([svg.height,svg.width]);
d3.json('orgTreeData.json',function(err,data){
if(err){
throw err.stack;
}
root = d3.hierarchy(data, function(d) {
return d.children;
});
tree(root);
var link = g.selectAll(".link")
.data(root.descendants().slice(1))
.enter().append("path")
.attr("class", "link")
.attr("d", function(d) {
console.log("attr d",d);
return "M" + d.y + "," + d.x
+ "C" + (d.y + d.parent.y) / 2 + "," + d.x
+ " " + (d.y + d.parent.y) / 2 + "," + d.parent.x
+ " " + d.parent.y + "," + d.parent.x;
});
//..........
});
`
the problem is each node 's x , y attribut is NaN.
Back in d3 3.x, d3 would populate my nodes with hierarchical/layout data (fields like parent
, x
, y
).
Therefore, if I had a rootNode
, and an otherNode
that was reachable from rootNode
, I could access otherNode.parent
, otherNode.x
, etc.
With d3 4.x, d3 creates a hierarchyRootNode
which contains the field parent
, and whose data
field contains my rootNode
. Similarly, were I to search for it from hierarchyRootNode
, I could find another hierarchy node whose data
field points to my otherNode
.
My question is: is there an existing way of obtaining that node? That is, given a data node, how can I best obtain its hierarchy container?
I am currently doing an inefficient:
const hierarchyOtherNode = hierarchyRootNode.descendants().find(d => d.data.id === otherNode.id)
Is there a simpler way to get around this?
Using the partition layout I have created a Icicle tree using both d3v3 and d3v4 where the height of a node should be the number of children it contains. However, the d3v4 hierarchy.sum() produces different dimensions than d3v3 partition.value().
var partition = d3Old.layout.partition()
.size([height,width])
.value(function(d) { return 1; })
.children(getChildren)
.sort(null)
var nodes = partition.nodes(data);
g2.selectAll("rect")
.data(nodes)
.enter()
.append("rect")
.attr("x", function(d) { return d.y; })
.attr("y", function(d) { return d.x; })
.attr("width", function(d) { return d.dy; })
.attr("height", function(d) { return d.dx; })
.attr('fill', function(d) {
var type = htmlElementType[d.name];
//debugging
if(type === undefined) {
console.log(d.data);
return colorScale(16);
} else {
return colorScale(COLOR[type]);
}
})
.attr('stroke', 'black')
var root = d3.hierarchy(data, getChildren)
.sum( function(d) {
return 1;
})
.sort(null);
var partition = d3.partition()
.size([height, width])
.padding(0)
//.round(f);
partition(root);
var nodes = g1.selectAll('rect')
.data(root.descendants())
.enter()
.append('rect')
.attr('fill', function(d) {
var type = htmlElementType[d.data.name];
//debugging
if(type === undefined) {
console.log(d.data);
return colorScale(16);
} else {
return colorScale(COLOR[type]);
}
})
.attr('stroke', 'black')
.attr("x", function(d) { return d.y0; })
.attr("y", function(d) { return d.x0; })
.attr("width", function(d) { return d.y1 - d.y0; })
.attr("height", function(d) { return d.x1 - d.x0; })
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.