D3 Examples - self sorting nodes in d3 fdg II

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 r³, and the rebounds calculated according to relative "mass".

force.alpha(a/0.99*(1 - x))

d3 features used

xxxxxxxxxx
 
<!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://cdn.jsdelivr.net/gh/repo/cool-blue/d3-lib/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>
​
​
    