Skip to content

Instantly share code, notes, and snippets.

@cool-Blue

cool-Blue/2015-08-31_22-26-49.png

Last active August 31, 2015 18:59
Show Gist options
  • Save cool-Blue/7afd8ab920fd01779e01 to your computer and use it in GitHub Desktop.
Save cool-Blue/7afd8ab920fd01779e01 to your computer and use it in GitHub Desktop.
Download ZIP
self sorting nodes in d3 fdg II
Raw
readme.md

Force Directed Graph with self sorting nodes - Position swapping

Features

  • 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, their velocities are preserved. This is done by also changing the previous points (p.px and p.py). The mass is calculated assuming the nodes are spheres, using r3, and the rebounds calculated according to relative "mass".
  force.alpha(a/0.99*(1 - x))

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;*/
}
#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 {
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-1.0.js"></script>
<script>
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 = 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 'alpha:' + 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(" >4,.1f")(1 / aveLap) + " fps"
+ '\ttime:' + d3.format(" >4,.1f")(this.t()) + " sec"
}),
width = 960 - 200,
height = 500 - elapsedTime.selection.node().clientHeight,
padding = 1, // separation between nodes
maxRadius = 7;
var n = 500, // total number of nodes
m = 1, // number of distinct layers
c = 10,
g = 0.01, g2 = 0.05,
f1 = 0.01, f2 = 0.001,
q2 = -4000;
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 % 6)) {
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(.01)
.charge(0)
.friction(.01)
.on("tick", tick)
.on("start", function() {
elapsedTime.start(1000);
tick.reset();
force
.gravity(g)
.charge(0)
.friction(f1)
});
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.append("g"),
bubble = Bubble(svg);
var viz = update(force, n, padding);
nodeCount
.property("value", n)
.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"
});
function Collide(nodes, padding) {
// Resolve collisions between nodes.
var maxRadius = d3.max(nodes, function(d) {
return d.q.radius
});
return function collide(alpha) {
var quadtree = d3.geom.quadtree(nodes);
return function(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;
if(l < r) {
for(; Math.abs(l) == 0;) {
x = Math.round(Math.random() * r);
y = Math.round(Math.random() * r);
l = Math.sqrt(x * x + y * y);
}
;
//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 = d.radius / quad.point.radius, 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 their velocity
d.x += (x *= l);
d.y += (y *= l);
d.px += x;
d.py += y;
quad.point.x -= x;
quad.point.y -= y;
quad.point.px -= x;
quad.point.py -= y;
}
}
return !possible;
});
};
}
}
function initNodes(force, n, padding) {
var rMax = Math.pow(500 / n * 50, 0.5);
force.stop()
force.nodes(d3.range(n).map(function() {
var layer = Math.floor(Math.random() * m),
u = Math.random(),
v = -Math.log(u);
return {
radius: Math.sqrt(v) * 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(_))]
},
};
}));
force.nodes().forEach(function(d) {
d.q = {};
Object.keys(d).forEach(function(p) {
if(!isNaN(d[p])) Object.defineProperty(d.q, p, {
get: function q() {
var dq = Math.round(d[p]);
if(isNaN(dq)) console.log([myName(arguments), d[p]].join(": "));
return dq
}
});
})
});
force.start();
return Collide(force.nodes(), padding);
}
function update(force, n, padding) {
elapsedTime.start(1000);
return {
collide: initNodes(force, n, padding),
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;
})
// .style("fill", function (d) {
// return d.color;
// })
.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