D3 Examples - self sorting nodes in d3 fdg IV

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.

Controlling shape
If the nodes are all created on [0,0], then a circular shape results but it tends to be asymmetrical, with most of the smaller nodes thrown to one side. This is due to extreme sensitivity to the distance from the center of the gravity field.

By creating the nodes on two points (randomly biased between the two) not only is the shape controlled but the efficiency of the sorting is markedly improved.

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

d3 features used

xxxxxxxxxx
 
<!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: inline-block;
        overflow: visible;
        border: none;
        background: black;
        margin: 0 0 0 100px;
    }
​
    text {
        text-anchor: middle;
    }
​
    .axis path, .axis line {
        fill: none;
        stroke: orange;
    }
​
</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-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   = 7;
​
        elapsedTime.consoleOn = false;
​
        var n0 = 500,
            m  = 1,
            c  = 10,
            g  = 0.005, g2 = 0.04,
            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) {
                    updateHist(viz.circle);
                    viz.circle.each(viz.collide(e.alpha));
                    if(e.alpha < 0.02 || !(phase = ++phase % (force.nodes().length >2000 ? 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) {
                        elapsedTime.timestamp("stage2")
                        force.friction(f2)
                            .charge(q2)
                            .gravity(g2)
                            .start().alpha(e.alpha);
                        stage1 = false;
                    }
                    force.alpha(e.alpha / 0.99 * 0.999)
                }
​
                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();
                    elapsedTime.timestamp("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 hh = height/2, hw = 50,
            hist  = d3.select("body").append("div")
                .attr("id", "speed")
                .style({"display": "inline-block", "vertical-align": "top"})
                .attr("transform", "translate(0," + -height *.1 + ")")
                .append("svg")
                .attr("width", hw)
                .attr("height", hh)
                .style({"margin": 0})
                .append("g"),
            histX = hist.append("g")
                .attr("class", "x axis")
                .style({fill: "orange", "text-size": "6px"});
​
​
        function updateHist(objects){
            var x = d3.scale.linear()
                    .domain([
                        0,
                        d3.max(objects.data(), function(o) {
                            return Math.sqrt(o.v.x * o.v.x + o.v.y + o.v.y)
                        })
                    ])
                    .range([0,hh-10]),
                s = speeds(objects.data()),
                xAxis = d3.svg.axis()
                    .scale(x)
                    .orient("left"),
                y = d3.scale.linear()
                    .domain([0,d3.max(s, function(d){return d.y})])
                    .range([0,hw]),
                bars = hist.selectAll(".bar").data(s);
​
            histX.call(xAxis);
​
            bars.enter().append("rect")
                    .attr("class", "bar")
                    .style({fill: "orange"});
​
            bars.exit().remove();
​
            bars.attr("height", function(d) {
                return x(d.dx)
            })
                .attr("width", function(d) {
                    return y(d.y)
                })
                .attr("y", function(d){
                    return x(d.x)
                });
​
            function speeds(data){
                var bins = d3.scale.ordinal()
                    .domain(d3.range(100))
                    .rangeBands(x.domain())
                    .range();
                console.log(x.domain());
                return d3.layout.histogram()
                    .bins(bins)
                    .value(function(d){
                        return Math.sqrt(d.v.x*d.v.x + d.v.y*d.v.y)
                    })(data)
            }
        }
​
        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.25) * 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((Math.random() - 0.5)* width/4),
                    x     : x(0),//x((Math.random() > 0.5)? width/4:-width/4),
                    y     : y((Math.random() > 0.5)? height/4:-height/4),
                    get v() {
                        var d = this;
                        return {
                            x: x.invert(d.x) - x.invert(d.px) || 0,
                            y: y.invert(d.y) - y.invert(d.py) || 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>
​
​
    