This is prelude to constructing tree-like graphs using the force layout.
when coding constraints which are really strict, e.g. binding a certain node or set of nodes
to a specific y coordinate (node.depth ~ y position in a vertical tree), it is opportune
to ‘insinuate’ the constraint rather than enforce it, i.e. you should apply the constraint
as if it was a force, i.e. verlet-integrate the delta, using the tick.alpha strength.
Of course nothing stops you from strengthening the applicatiuon of the constraint
when the alpha value is near zero (i.e. we’re almost stable/at the end of the force iteration).
you can edit both .x/.y and .px/.py in the tick handler, but any ‘force-like’ constraints
should best be applied to the .px/.py components as then they will mix with the repulse and
verlet integration logic in the next round.
given the two items above, it is opportune to code a constraint like ‘stay within visible area’ as a dual constraint: one which clips the x/y node coordinates to ensure they stick within the visible area, and a second part which is a ‘force’ applied to repulse any nodes close to the edge(s): if you don’t do the latter, you’ll get graph views where a lot of nodes hug the edge(s) and don’t resolve themselves to move back into the visible area proper. (Drag any graph to the edge with such a constraint and you’re getting a very jittery graph where a lot of the nodes bounce against the edges but don’t ‘move away’. That’s why you need such a second ‘repulse force’ to make this happen and make the graph look good, even when dragged near the edge.
All constraints are applied in the force.on(“tick”) event handler.
We also implement drag behaviour, which, like any other use of node.fixed, will add a .px/.py coordinate
pair for each node under the hood. To prevent any ‘Crazy Ivan jumping’ of nodes and other unexpected behaviour, we must ensure that
.x/.y and .px/.py match once we are done in the force.tick handler, otherwise the
next mouseenter/drag will behave very oddly.
It is always a good rule to set both .px/.py and .x/.y when you update force nodes’ x/y coordinates.
This example is derived off the D3 example examples/force/force-collapsible.html.
The code requires a D3 version which includes (pull request #803](https://github.com/mbostock/d3/pull/803).
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<title>Force-Directed Graph: Collapsible, Hierarchical</title>
<script src="readme.js"></script> <!-- hide d3.v2.js from bl.ocks.org output by naming it readme.ls -->
<style type="text/css">
circle.node {
cursor: pointer;
stroke: #000;
stroke-width: .5px;
}
line.link {
fill: none;
stroke: #9ecae1;
stroke-width: 1.5px;
}
</style>
</head>
<body>
<div id="chart"></div>
<script type="text/javascript" src="//gerhobbelt.github.com/bl.ocks.org-hack/fixit.js" ></script>
<script type="text/javascript">
var width = 960,
height = 500,
node,
link,
root;
var force = d3.layout.force()
.on("tick", tick)
.charge(function(d) {
return d._children ? -d.size / 100 : d.children ? -100 : -30;
})
.linkDistance(function(d) {
return d.target._children ? 50 : 30;
})
.size([width, height]);
var vis = d3.select("#chart").append("svg")
.attr("width", width)
.attr("height", height);
d3.json("flare.json", function(json) {
root = json;
root.fixed = true;
root.px = root.py = 0;
update();
});
function update(nodes) {
var nodes = flatten(root);
var links = d3.layout.hierarchy().links(nodes);
// make sure we set .px/.py as well as node.fixed will use those .px/.py to 'stick' the node to:
if (!root.px) {
// root have not be set / dragged / moved: set initial root position
root.px = root.x = width / 2;
root.py = root.y = circle_radius(root) + 2;
}
// Restart the force layout.
force
.nodes(nodes)
.links(links)
.start();
// Update the links…
link = vis.selectAll("line.link")
.data(links, function(d) { return d.target.id; });
// Enter any new links.
link.enter().insert("line", ".node")
.attr("class", "link")
.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
// Exit any old links.
link.exit().remove();
// Update the nodes…
node = vis.selectAll("circle.node")
.data(nodes, function(d) { return d.id; })
.style("fill", color);
node.transition()
.attr("cy", function(d) { return d.y; })
.attr("r", function(d) { return circle_radius(d); });
// Enter any new nodes.
node.enter().append("circle")
.attr("class", "node")
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", function(d) { return circle_radius(d); })
.style("fill", color)
.on("click", click)
.call(force.drag);
// Exit any old nodes.
node.exit().remove();
}
function tick() {
// Apply the constraints:
//
force.nodes().forEach(function(d) {
if (!d.fixed) {
var r = circle_radius(d) + 4, dx, dy, ly = 30;
// #1: constraint all nodes to the visible screen:
//d.x = Math.min(width - r, Math.max(r, d.x));
//d.y = Math.min(height - r, Math.max(r, d.y));
// #1.0: hierarchy: same level nodes have to remain with a 1 LY band vertically:
if (d.children || d._children) {
var py = 0;
if (d.parent) {
py = d.parent.y;
}
d.py = d.y = py + d.depth * ly + r;
}
// #1a: constraint all nodes to the visible screen: links
dx = Math.min(0, width - r - d.x) + Math.max(0, r - d.x);
dy = Math.min(0, height - r - d.y) + Math.max(0, r - d.y);
d.x += 2 * Math.max(-ly, Math.min(ly, dx));
d.y += 2 * Math.max(-ly, Math.min(ly, dy));
// #1b: constraint all nodes to the visible screen: charges ('repulse')
dx = Math.min(0, width - r - d.px) + Math.max(0, r - d.px);
dy = Math.min(0, height - r - d.py) + Math.max(0, r - d.py);
d.px += 2 * Math.max(-ly, Math.min(ly, dx));
d.py += 2 * Math.max(-ly, Math.min(ly, dy));
// #2: hierarchy means childs must be BELOW parents in Y direction:
if (d.parent) {
d.y = Math.max(d.y, d.parent.y + ly);
d.py = Math.max(d.py, d.parent.py + ly);
}
}
});
link.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
}
// Color leaf nodes orange, and packages white or blue.
function color(d) {
return d._children ? "#3182bd" : d.children ? "#c6dbef" : "#fd8d3c";
}
function circle_radius(d) {
return d.children ? 4.5 : Math.sqrt(d.size) / 10;
}
// Toggle children on click.
function click(d) {
if (d.children) {
d._children = d.children;
d.children = null;
} else {
d.children = d._children;
d._children = null;
}
update();
}
// Returns a list of all nodes under the root.
//
// Also assign each node a reasonable starting x/y position: we can do better than random placement since we're force-layout-ing a hierarchy!
function flatten(root) {
var nodes = [], i = 0, depth = 0, level_widths = [1], max_width, max_depth = 1, kx, ky;
function recurse(node, parent, depth, x) {
if (node.children) {
var w = level_widths[depth + 1] || 0;
level_widths[depth + 1] = w + node.children.length;
max_depth = Math.max(max_depth, depth + 1);
node.size = node.children.reduce(function(p, v, i) {
return p + recurse(v, node, depth + 1, w + i);
}, 0);
}
if (!node.id) node.id = ++i;
node.parent = parent;
node.depth = depth;
if (!node.px) {
node.y = depth;
node.x = x;
}
nodes.push(node);
return node.size;
}
root.size = recurse(root, null, 0);
// now correct/balance the x positions:
max_width = 1;
for (i = level_widths.length; --i > 0; ) {
max_width = Math.max(max_width, level_widths[i]);
}
kx = (width - 20) / max_width;
ky = (height - 20) / max_depth;
for (i = nodes.length; --i >= 0; ) {
var node = nodes[i];
if (!node.px) {
node.y *= ky;
node.y += 10 + ky / 2;
node.x *= kx;
node.x += 10 + kx / 2;
}
}
return nodes;
}
</script>
</body>
</html>
{
"name": "flare",
"children": [
{
"name": "analytics",
"children": [
{
"name": "cluster",
"children": [
{"name": "AgglomerativeCluster", "size": 3938},
{"name": "CommunityStructure", "size": 3812},
{"name": "HierarchicalCluster", "size": 6714},
{"name": "MergeEdge", "size": 743}
]
},
{
"name": "graph",
"children": [
{"name": "BetweennessCentrality", "size": 3534},
{"name": "LinkDistance", "size": 5731},
{"name": "MaxFlowMinCut", "size": 7840},
{"name": "ShortestPaths", "size": 5914},
{"name": "SpanningTree", "size": 3416}
]
},
{
"name": "optimization",
"children": [
{"name": "AspectRatioBanker", "size": 7074}
]
}
]
},
{
"name": "animate",
"children": [
{"name": "Easing", "size": 17010},
{"name": "FunctionSequence", "size": 5842},
{
"name": "interpolate",
"children": [
{"name": "ArrayInterpolator", "size": 1983},
{"name": "ColorInterpolator", "size": 2047},
{"name": "DateInterpolator", "size": 1375},
{"name": "Interpolator", "size": 8746},
{"name": "MatrixInterpolator", "size": 2202},
{"name": "NumberInterpolator", "size": 1382},
{"name": "ObjectInterpolator", "size": 1629},
{"name": "PointInterpolator", "size": 1675},
{"name": "RectangleInterpolator", "size": 2042}
]
},
{"name": "ISchedulable", "size": 1041},
{"name": "Parallel", "size": 5176},
{"name": "Pause", "size": 449},
{"name": "Scheduler", "size": 5593},
{"name": "Sequence", "size": 5534},
{"name": "Transition", "size": 9201},
{"name": "Transitioner", "size": 19975},
{"name": "TransitionEvent", "size": 1116},
{"name": "Tween", "size": 6006}
]
},
{
"name": "data",
"children": [
{
"name": "converters",
"children": [
{"name": "Converters", "size": 721},
{"name": "DelimitedTextConverter", "size": 4294},
{"name": "GraphMLConverter", "size": 9800},
{"name": "IDataConverter", "size": 1314},
{"name": "JSONConverter", "size": 2220}
]
},
{"name": "DataField", "size": 1759},
{"name": "DataSchema", "size": 2165},
{"name": "DataSet", "size": 586},
{"name": "DataSource", "size": 3331},
{"name": "DataTable", "size": 772},
{"name": "DataUtil", "size": 3322}
]
},
{
"name": "display",
"children": [
{"name": "DirtySprite", "size": 8833},
{"name": "LineSprite", "size": 1732},
{"name": "RectSprite", "size": 3623},
{"name": "TextSprite", "size": 10066}
]
},
{
"name": "flex",
"children": [
{"name": "FlareVis", "size": 4116}
]
},
{
"name": "physics",
"children": [
{"name": "DragForce", "size": 1082},
{"name": "GravityForce", "size": 1336},
{"name": "IForce", "size": 319},
{"name": "NBodyForce", "size": 10498},
{"name": "Particle", "size": 2822},
{"name": "Simulation", "size": 9983},
{"name": "Spring", "size": 2213},
{"name": "SpringForce", "size": 1681}
]
},
{
"name": "query",
"children": [
{"name": "AggregateExpression", "size": 1616},
{"name": "And", "size": 1027},
{"name": "Arithmetic", "size": 3891},
{"name": "Average", "size": 891},
{"name": "BinaryExpression", "size": 2893},
{"name": "Comparison", "size": 5103},
{"name": "CompositeExpression", "size": 3677},
{"name": "Count", "size": 781},
{"name": "DateUtil", "size": 4141},
{"name": "Distinct", "size": 933},
{"name": "Expression", "size": 5130},
{"name": "ExpressionIterator", "size": 3617},
{"name": "Fn", "size": 3240},
{"name": "If", "size": 2732},
{"name": "IsA", "size": 2039},
{"name": "Literal", "size": 1214},
{"name": "Match", "size": 3748},
{"name": "Maximum", "size": 843},
{
"name": "methods",
"children": [
{"name": "add", "size": 593},
{"name": "and", "size": 330},
{"name": "average", "size": 287},
{"name": "count", "size": 277},
{"name": "distinct", "size": 292},
{"name": "div", "size": 595},
{"name": "eq", "size": 594},
{"name": "fn", "size": 460},
{"name": "gt", "size": 603},
{"name": "gte", "size": 625},
{"name": "iff", "size": 748},
{"name": "isa", "size": 461},
{"name": "lt", "size": 597},
{"name": "lte", "size": 619},
{"name": "max", "size": 283},
{"name": "min", "size": 283},
{"name": "mod", "size": 591},
{"name": "mul", "size": 603},
{"name": "neq", "size": 599},
{"name": "not", "size": 386},
{"name": "or", "size": 323},
{"name": "orderby", "size": 307},
{"name": "range", "size": 772},
{"name": "select", "size": 296},
{"name": "stddev", "size": 363},
{"name": "sub", "size": 600},
{"name": "sum", "size": 280},
{"name": "update", "size": 307},
{"name": "variance", "size": 335},
{"name": "where", "size": 299},
{"name": "xor", "size": 354},
{"name": "_", "size": 264}
]
},
{"name": "Minimum", "size": 843},
{"name": "Not", "size": 1554},
{"name": "Or", "size": 970},
{"name": "Query", "size": 13896},
{"name": "Range", "size": 1594},
{"name": "StringUtil", "size": 4130},
{"name": "Sum", "size": 791},
{"name": "Variable", "size": 1124},
{"name": "Variance", "size": 1876},
{"name": "Xor", "size": 1101}
]
},
{
"name": "scale",
"children": [
{"name": "IScaleMap", "size": 2105},
{"name": "LinearScale", "size": 1316},
{"name": "LogScale", "size": 3151},
{"name": "OrdinalScale", "size": 3770},
{"name": "QuantileScale", "size": 2435},
{"name": "QuantitativeScale", "size": 4839},
{"name": "RootScale", "size": 1756},
{"name": "Scale", "size": 4268},
{"name": "ScaleType", "size": 1821},
{"name": "TimeScale", "size": 5833}
]
},
{
"name": "util",
"children": [
{"name": "Arrays", "size": 8258},
{"name": "Colors", "size": 10001},
{"name": "Dates", "size": 8217},
{"name": "Displays", "size": 12555},
{"name": "Filter", "size": 2324},
{"name": "Geometry", "size": 10993},
{
"name": "heap",
"children": [
{"name": "FibonacciHeap", "size": 9354},
{"name": "HeapNode", "size": 1233}
]
},
{"name": "IEvaluable", "size": 335},
{"name": "IPredicate", "size": 383},
{"name": "IValueProxy", "size": 874},
{
"name": "math",
"children": [
{"name": "DenseMatrix", "size": 3165},
{"name": "IMatrix", "size": 2815},
{"name": "SparseMatrix", "size": 3366}
]
},
{"name": "Maths", "size": 17705},
{"name": "Orientation", "size": 1486},
{
"name": "palette",
"children": [
{"name": "ColorPalette", "size": 6367},
{"name": "Palette", "size": 1229},
{"name": "ShapePalette", "size": 2059},
{"name": "SizePalette", "size": 2291}
]
},
{"name": "Property", "size": 5559},
{"name": "Shapes", "size": 19118},
{"name": "Sort", "size": 6887},
{"name": "Stats", "size": 6557},
{"name": "Strings", "size": 22026}
]
},
{
"name": "vis",
"children": [
{
"name": "axis",
"children": [
{"name": "Axes", "size": 1302},
{"name": "Axis", "size": 24593},
{"name": "AxisGridLine", "size": 652},
{"name": "AxisLabel", "size": 636},
{"name": "CartesianAxes", "size": 6703}
]
},
{
"name": "controls",
"children": [
{"name": "AnchorControl", "size": 2138},
{"name": "ClickControl", "size": 3824},
{"name": "Control", "size": 1353},
{"name": "ControlList", "size": 4665},
{"name": "DragControl", "size": 2649},
{"name": "ExpandControl", "size": 2832},
{"name": "HoverControl", "size": 4896},
{"name": "IControl", "size": 763},
{"name": "PanZoomControl", "size": 5222},
{"name": "SelectionControl", "size": 7862},
{"name": "TooltipControl", "size": 8435}
]
},
{
"name": "data",
"children": [
{"name": "Data", "size": 20544},
{"name": "DataList", "size": 19788},
{"name": "DataSprite", "size": 10349},
{"name": "EdgeSprite", "size": 3301},
{"name": "NodeSprite", "size": 19382},
{
"name": "render",
"children": [
{"name": "ArrowType", "size": 698},
{"name": "EdgeRenderer", "size": 5569},
{"name": "IRenderer", "size": 353},
{"name": "ShapeRenderer", "size": 2247}
]
},
{"name": "ScaleBinding", "size": 11275},
{"name": "Tree", "size": 7147},
{"name": "TreeBuilder", "size": 9930}
]
},
{
"name": "events",
"children": [
{"name": "DataEvent", "size": 2313},
{"name": "SelectionEvent", "size": 1880},
{"name": "TooltipEvent", "size": 1701},
{"name": "VisualizationEvent", "size": 1117}
]
},
{
"name": "legend",
"children": [
{"name": "Legend", "size": 20859},
{"name": "LegendItem", "size": 4614},
{"name": "LegendRange", "size": 10530}
]
},
{
"name": "operator",
"children": [
{
"name": "distortion",
"children": [
{"name": "BifocalDistortion", "size": 4461},
{"name": "Distortion", "size": 6314},
{"name": "FisheyeDistortion", "size": 3444}
]
},
{
"name": "encoder",
"children": [
{"name": "ColorEncoder", "size": 3179},
{"name": "Encoder", "size": 4060},
{"name": "PropertyEncoder", "size": 4138},
{"name": "ShapeEncoder", "size": 1690},
{"name": "SizeEncoder", "size": 1830}
]
},
{
"name": "filter",
"children": [
{"name": "FisheyeTreeFilter", "size": 5219},
{"name": "GraphDistanceFilter", "size": 3165},
{"name": "VisibilityFilter", "size": 3509}
]
},
{"name": "IOperator", "size": 1286},
{
"name": "label",
"children": [
{"name": "Labeler", "size": 9956},
{"name": "RadialLabeler", "size": 3899},
{"name": "StackedAreaLabeler", "size": 3202}
]
},
{
"name": "layout",
"children": [
{"name": "AxisLayout", "size": 6725},
{"name": "BundledEdgeRouter", "size": 3727},
{"name": "CircleLayout", "size": 9317},
{"name": "CirclePackingLayout", "size": 12003},
{"name": "DendrogramLayout", "size": 4853},
{"name": "ForceDirectedLayout", "size": 8411},
{"name": "IcicleTreeLayout", "size": 4864},
{"name": "IndentedTreeLayout", "size": 3174},
{"name": "Layout", "size": 7881},
{"name": "NodeLinkTreeLayout", "size": 12870},
{"name": "PieLayout", "size": 2728},
{"name": "RadialTreeLayout", "size": 12348},
{"name": "RandomLayout", "size": 870},
{"name": "StackedAreaLayout", "size": 9121},
{"name": "TreeMapLayout", "size": 9191}
]
},
{"name": "Operator", "size": 2490},
{"name": "OperatorList", "size": 5248},
{"name": "OperatorSequence", "size": 4190},
{"name": "OperatorSwitch", "size": 2581},
{"name": "SortOperator", "size": 2023}
]
},
{"name": "Visualization", "size": 16540}
]
}
]
}#! /bin/bash
#
# copy latest d3.js from local D3 work repo
#
rm -f d3.v2.js readme.js
pushd ../html/js/d3/
make
popd
cp ../html/js/d3/d3.v2.js ./readme.js