Skip to content

Instantly share code, notes, and snippets.

@cool-Blue

cool-Blue/2015-08-31_22-31-57.png

Last active September 1, 2015 19:16
Show Gist options
  • Save cool-Blue/ae365cfb13ad972c65f4 to your computer and use it in GitHub Desktop.
Save cool-Blue/ae365cfb13ad972c65f4 to your computer and use it in GitHub Desktop.
Download ZIP
self sorting nodes in d3 fdg III
Raw
readme.md

Force Directed Graph with self sorting nodes

The nodes arrange themselves by size, with the larger nodes migrating toward the center.

Features

  • Metrics display and inputs
    The metrics panel across the top of the svg element gives a live display of the layout state. The inputs on the left allow for the number of nodes and the force gravity and the friction to be adjusted live. The current alpha value for the layout is displayed along with instantaneous and averaged tick time and the average calculation rate of the layout. Changing any of the inputs re-starts the layout.
  • Accelerated annealing
    The annealing calc is done every tick but, until alpha drops below 0.05, the viz is only updated every nth tick (n is currently 4). This delivers significant reductions in the time to reach equilibrium (roughly a factor of 2).
  • Force dynamics
    The force dynamics are a function of alpha, with two phases. The initial phase has zero charge, low gravity and low damping. This is designed to maximise mixing and sorting. The second phase has a higher gravity and a large, negative charge and much higher damping, this is designed to clean up and stabilise the presentation of the nodes.
  • Collisions between nodes
    Based on this example but enhanced to sort the radial position of the nodes based on size, with larger nodes closer to the center. Every collision is used as an opportunity to correct the relative positions. If they are out of position then the radial ordinates of the colliding nodes (in polar coordinates) are swapped. The sorting efficiency is therefore reliant on good mixing in the collisions. In order to maximise the mixing, the nodes are all created at the same point in the center of the graph. When the nodes are swapped, the velocity of the bigger node is preserved while the smaller node is accelerated. Thus, the sorting efficiency is enhanced because the smaller nodes are flung out from the collision point. The mass is calculated assuming the nodes are spheres, using r3, and the rebounds calculated according to relative "mass".

d3 features used

  1. d3.layout.force
  2. Ordinal Scales
  3. d3.format
  4. d3.range
  5. d3.geom.quadtree
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
/*margin: 200px 500px 100px 500px;*/
/*font-size: 10px;*/
}
#inputs {
display: inline-block;
margin: 0 0 0 0.5em;
}
#panel {
display: inline-block;
margin: 0 0 0 100px;
border: none;
box-sizing: border-box;
background-color: black;
}
#metrics {
display: inline-block;
}
label, input {
/*font-size: 10px;*/
text-align: left;
width: 3.5em;
color: orange;
/*padding-left: 1em;*/
background-color: black;
outline: none;
border: none;
}
circle {
stroke: black;
/*stroke: #ccc;*/
/*stroke-opacity: 0.5;*/
/*stroke-width: 6;*/
}
svg {
display: block;
overflow: visible;
border: none;
background: black;
margin: 0 100px 0 100px;
}
text {
text-anchor: middle;
}
rect {
stroke: #ccc;
}
</style>
<body>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<!--<script src="d3 CB.js"></script>-->
<script
src="https://cdnjs.cloudflare.com/ajax/libs/tinycolor/1.1.2/tinycolor.min.js"></script>
<script src="https://gitcdn.xyz/repo/cool-Blue/d3-lib/master/filters/shadow.js"></script>
<script
src="https://gitcdn.xyz/repo/cool-Blue/d3-lib/master/elapsedTime/elapsed-time-2.0.js"></script>
<script>
!(function() {
var inputs = d3.select("body").append("div")
.attr("id", "metrics")
.append("div").attr({id: "panel"})
.append("div").attr({id: "inputs"}),
nodeCount = inputs.append("label")
.attr("for", "nodeCount")
.text("nodes: ")
.append("input")
.attr({
id : "nodeCount",
class : "numIn",
type : "number",
min : "100",
max : "5,000",
step : "100",
inputmode: "numeric"
});
var elapsedTime = outputs.ElapsedTime("#panel", {
border : 0, margin: 0, "box-sizing": "border-box",
padding: "0 0 0 3px", background: "black", "color": "orange"
})
.message(function(value) {
var this_lap = this.lap().lastLap, aveLap = this.aveLap(this_lap)
return 'q:' + d3.format(" >4,.0f")(force.charge())
+ '\talpha:' + d3.format(" >7,.3f")(value)
+ '\ttick time:' + d3.format(" >8,.4f")(this_lap)
+ ' (' + d3.format(" >4,.3f")(this.aveLap(this_lap)) + ')'
+ '\tframe rate:' + d3.format(" >5,.1f")(1 / aveLap) + " fps"
+ '\ttime:' + d3.format(" >4,.1f")(this.t()) + " sec"
}),
width = 960 - 200,
height = 500 - elapsedTime.selection.node().clientHeight,
padding = 0, // separation between nodes
maxRadius = 5;
elapsedTime.consoleOn = false;
var n0 = 500,
m = 1,
c = 10,
g = 0.01, g2 = 0.05,
f1 = 0.5, f2 = 0.001,
q2 = -2000;
var x = d3.scale.linear()
.domain([-width / 2, width / 2])
.range([0, width]),
y = d3.scale.linear()
.domain([-height / 2, height / 2])
.range([height, 0]);
var tick = (function() {
var phase = -1, stage1 = true;
function tick(e) {
viz.circle.each(viz.collide(e.alpha));
if(e.alpha < 0.02 || !(phase = ++phase % (force.nodes().length >1000 ? 4 : 2))) {
elapsedTime.mark(e.alpha);
viz.circle.attr({
cx: function(d) {
return d.x;
},
cy: function(d) {
return d.y;
}
});
}
if(stage1 && e.alpha < 0.07) {
console.log("stage2")
force.friction(f2)
.charge(q2)
.gravity(g2)
.start().alpha(e.alpha);
stage1 = false;
}
// force.alpha(e.alpha / 0.99 * 0.99)
}
tick.reset = function() {
stage1 = true;
};
return tick;
})(),
force = d3.layout.force()
.size([width, height])
.gravity(g)
.charge(0)
.friction(f1)
.on("tick", tick)
.on("start", function() {
elapsedTime.start(1000);
tick.reset();
console.log("force start")
});
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.append("g"),
bubble = Bubble(svg);
nodeCount
.property("value", n0)
.on("change", function() {
viz = update(force, this.value, padding);
this.blur();
});
elapsedTime.selection.style({
width: (width
- parseFloat(window.getComputedStyle(d3.select("#inputs").node()).getPropertyValue("width"))
- parseFloat(window.getComputedStyle(d3.select("#inputs").node()).getPropertyValue("margin-left")))
+ "px"
});
var viz = update(force, n0, padding);
function Collide(nodes, padding) {
// Resolve collisions between nodes.
var maxRadius = d3.max(nodes, function(d) {
return d.radius
});
return function collide(alpha) {
var quadtree = d3.geom.quadtree(nodes), hit = false;
return function c(d) {
var r = d.radius + maxRadius + padding,
nx1 = d.x - r,
nx2 = d.x + r,
ny1 = d.y - r,
ny2 = d.y + r;
quadtree.visit(function v(quad, x1, y1, x2, y2) {
var possible = !(x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1);
if(quad.point && (quad.point !== d) && possible) {
var x = d.x - quad.point.x,
y = d.y - quad.point.y,
l = (Math.sqrt(x * x + y * y)),
r = (d.radius + quad.point.radius + padding),
mq = Math.pow(quad.point.radius, 3),
m = Math.pow(d.radius, 3);
if(hit = (l < r)) {
if(l == 0) {
for(var j = 3; l == 0; j--) {
x = (Math.random() - 0.5);
y = (Math.random() - 0.5);
l = Math.sqrt(x * x + y * y);
}
d.x += x/2;
d.y += y/2;
quad.point.x += x/2;
quad.point.y += y/2;
}
//move the nodes away from each other along the radial (normal) vector
//taking relative size into consideration, the sign is already established
//in calculating x and y
l = (r - l) / l * (1 + alpha);
// if the nodes are in the wrong radial order for there size, swap radius ordinate
var rel = m / mq, bigger = rel > 1,
rad = d.r / quad.point.r, farther = rad > 1;
if(bigger && farther || !bigger && !farther) {
var d_r = d.r;
d.r = quad.point.r;
quad.point.r = d_r;
d_r = d.pr;
d.pr = quad.point.pr;
quad.point.pr = d_r;
}
// move nodes apart but preserve the velocity of the biggest one
// and accelerate the smaller one
d.x += (x *= l);
d.y += (y *= l);
d.px += x * bigger || -alpha;
d.py += y * bigger || -alpha;
quad.point.x -= x;
quad.point.y -= y;
quad.point.px -= x * !bigger || -alpha;
quad.point.py -= y * !bigger || -alpha;
}
}
return !possible;
});
};
}
}
function initNodes(force, n, padding, custom) {
var rMax = Math.pow(n0 / n, 0.5) * maxRadius;
force.stop()
.nodes(d3.range(n).map(function() {
var layer = Math.floor(Math.random() * m),
u = Math.random(),
v = -Math.log(u);
return {
radius: Math.pow(v,.8) * rMax,
color : Math.floor(u * c),
x : x(0),
y : y(0),
get v() {
var d = this;
return {
x: x.invert(d.x - d.px || d.x || 0),
y: y.invert(d.y - d.py || d.y || 0)
}
},
get polar() {
var xx = x.invert(this.x), yy = y.invert(this.y);
return [Math.sqrt(xx * xx + yy * yy), Math.atan2(yy, xx)]
},
set polar(p) {
var r = p[0], theta = p[1];
return [this.x = x(r * Math.cos(theta)), this.y = y(r
* Math.sin(theta))]
},
get r() {
var xx = x.invert(this.x), yy = y.invert(this.y);
return Math.sqrt(xx * xx + yy * yy);
},
get theta() {
var xx = x.invert(this.x), yy = y.invert(this.y);
return Math.atan2(yy, xx)
},
set r(_) {
var theta = this.theta;
return [this.x = x(_ * Math.cos(theta)), this.y = y(_
* Math.sin(theta))]
},
set theta(_) {
var r = this.r;
return [this.x = x(r * Math.cos(_)), this.y = y(r * Math.sin(_))]
},
get pr() {
var xx = x.invert(this.px), yy = y.invert(this.py);
return Math.sqrt(xx * xx + yy * yy);
},
get ptheta() {
var xx = x.invert(this.px), yy = y.invert(this.py);
return Math.atan2(yy, xx)
},
set pr(_) {
var theta = this.ptheta;
return [this.px = x(_ * Math.cos(theta)), this.py = y(_
* Math.sin(theta))]
},
set ptheta(_) {
var r = this.pr;
return [this.px = x(r * Math.cos(_)), this.py = y(r
* Math.sin(_))]
},
};
}))
.gravity(custom.g || Math.pow(n0 / n, 1.2) * g)
.friction(custom.f || f1)
.charge(0);
// window.setTimeout(function(){
force.start()
// }, 20)
return Collide(force.nodes(), padding);
}
function update(force, n, padding, custom) {
elapsedTime.start(1000);
return {
collide: initNodes(force, n, padding, custom || {}),
circle : (function() {
var update = svg.selectAll("circle")
.data(force.nodes());
update.enter().append("circle");
update.exit().remove();
update.attr("r", function(d) {
return d.radius;
})
.call(bubble.call)
.call(force.drag);
return update;
})()
};
}
function Bubble(svg) {
var colors = d3.range(20).map(d3.scale.category10()).map(function(d) {
return filters.sphere(svg, d, 1)
});
return {
call: function(selection) {
selection.style("fill", function(d) {
return colors[d.color]
})
},
map : function(d, i, data) {
d.fill = colors[~~(Math.random() * 20)];
},
fill: function(d) {
return d.fill
}
}
};
function myName(args) {
return /function\s+(\w*)\(/.exec(args.callee)[1];
}
})()
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment