Layered gravity with weak side constraints, mass and wind-up

readme.md

Force Directed Graph with Custom Gravity

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, the strength of the side constraint and the windup factor for un-mixing to be adjusted live. The current alpha value for the layout is displayed along with instantaneous and averaged tick time and the average frame rate of the layout. Changing the number of nodes re-starts the layout.
• Custom gravity (layers)
  The nodes have a cy member which is its target y value, the gravity function, which is called from the force.on("tick"...) callback has behaviour to move the nodes toward their cy position on each tick.
• Collisions between nodes Based on this example but enhanced to simulate mass, so that bigger nodes have higher inertia in collisions and momentum is roughly conserved.
  The mass is calculated assuming the nodes are spheres, using r³, and the relative rebounds calculated according to relative "mass".
• Bounding box constraints and boundary collisions
  This behaviour is also included in the gravity function and uses basic geometry to reflect the incident velocity in the plane of the boundary. It does this by manipulating the d.px and d.py values of the nodes. It is possible, however, for nodes to penetrate the boundaries due to limitations in the temporal resolution of the layout.
• Recovering escaped nodes
  If a node escapes the boundaries of the bounding box, the velocity is still reflected in the plane of the penetrated boundary. If the escaped node has no velocity (p.q.x/y == p.q.px/py) then the node is moved back toward the boundary. After it is fully recovered, the velocity of the node will be naturally determined by the distance it was last moved by the recovery behaviour.
• Quantisation of screen position
  It is possible for nodes with different values to be stationary due to quantisation of d.x and d.px by the rendering process. This means that decisions in the code based on position may not reflect the rendered state properly. This is fixed by adding a getter to each data point that returns a rounded version of d.x/y and d.px/y: d.q.x/y and d.q.px/y. The quantised versions are used for the decision making in the boundary collisions and recovery behaviour.
• Guaranteed un-mixing of nodes
  It's possible for nodes to be blocked from reaching they're cy positions by other, more massive nodes in adjacent layers, in order to overcome this, a frustration factor is applied to the isolated nodes which has the effect of increasing they're effective mass with each tick that they are outside they're designated band. The increase in mass factor per tick is the windup which defaults to 0.01. This is adjustable via an input in the metrics panel. Nodes with an anxiety greater than one are highlighted with a white stroke and as soon as they make it to they're layer they're anxiety is switched back to 1.
• Weak constraints
  The strength of the boundary constraints, in terms of the rate of recovery of escaped nodes, is regulated by implementing the amount by which the nodes are moved back as a uniformly distributed random variable. This is done using Math.random(). This is controlled, for side constraints, via the constraint input in the metrics panel. The value of the constraint is the probability that nodes escaped to the sides will be moved back toward the bounding box.
• Extended cooling time
  The cooling time for the force layout is determined by the evolution of its alpha value. This is set to 0.1 when the layout is started and is normally reduced by 1% each tick until it reaches 0.005, at which point the layout will stop updating. It is possible to manipulate the cooling rate so that it cools at x% by dividing the current alpha value by the standard factor of 0.99 and multiplying it by (1 - x%) at the end of the tick callback:

  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

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
  /*margin: 200px 500px 100px 500px;*/
}
#inputs {
  display: inline-block;
  margin: 0 0 0 100px;
  border: none;
  padding: 0 0 0 1em;
  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;
}
  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: "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"}),
        constraint = inputs.append("label")
          .attr("for", "sideConstraint")
          .text("constraint: ")
          .append("input")
            .attr({id: "sideConstraint", class: "numIn", type: "number", min:"0", max: "1", step: "0.05", inputmode: "numeric"});
        windUp = inputs.append("label")
          .attr("for", "windUp")
          .text("windUp: ")
          .append("input")
            .attr({id: "windUp", class: "numIn", type: "number", min:"0", max: "1", step: "0.01", inputmode: "numeric"});

    var elapsedTime = ElapsedTime("#metrics", {
        border: 0, margin: 0, "box-sizing": "border-box",
        padding: "0 0 0 6px", 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"
        }),

        width = 960 - 200,
        height = 500 - elapsedTime.selection.node().clientHeight,
        padding = 0, // separation between nodes
        maxRadius = 6;

    var n = 2000, // total number of nodes
        m = 10; // number of distinct layers

    var color = d3.scale.category10()
        .domain(d3.range(m));

    var y = d3.scale.ordinal()
        .domain(d3.range(m))
        .rangePoints([height, 0], 1),
        w = d3.scale.ordinal()
        .domain(d3.range(m))
        .rangeBands([height, 0]),
        wRange = w.range();

    var force = d3.layout.force()
        .size([width, height])
        .gravity(0)
        .charge(0)
        .friction(0.7)
        .on("tick", tick)
        .on("start", function () {
          elapsedTime.start(1000);
        });

    var svg = d3.select("body").append("svg")
        .attr("width", width)
        .attr("height", height)
        .append("g"),
      bubble = Bubble(svg);
    svg.selectAll("wells").data(wRange).enter().append("rect")
      .attr({width: width, height: w.rangeBand(), y: function(d){return d}})
    var viz = update(force, n, padding);

    nodeCount
      .property("value", n)
      .on("change", function() {
        viz = update(force, this.value, padding);
        this.blur();
      });
    constraint
      .property("value", 0.05)
      .value = function () { return 1 - this.property("value")};
    windUp
      .property("value", 0.01)
      .value = function () { return +this.property("value")};

    elapsedTime.selection.style({
      width: (width - parseFloat(window.getComputedStyle(d3.select("#inputs").node()).getPropertyValue("width"))) + "px"
    });
    console.log("getBoundingClientRect\t" + d3.select("#inputs").node().getBoundingClientRect().width
          + "getComputedStyle\t" + parseFloat(window.getComputedStyle(d3.select("#inputs").node()).getPropertyValue("width")))

    function tick(e) {
      var a = e.alpha;
      elapsedTime.mark(a);
      viz.circle
          .each(gravity(a))
          .each(viz.collide(1.9))
          .attr({
            cx    : function (d) {
              return d.x;
            },
            cy    : function (d) {
              return d.y;
            }
          })
        .style("stroke", function (d) {
          return d.frustration() > 1 ? "white" : "black";
        }
        );
      force.alpha(a/0.99*0.999)
    }

   // Move nodes toward cluster focus.
    function gravity(alpha) {
      return function(d) {
        //reflect off the edges of the container
        var r = d.radius, c = constraint.value();
        if (d.x - r <= 0 && d.q.px >= d.q.x) boundary(d, "x", [0, width], c);
        if (d.x + r >= width && d.q.px <= d.q.x) boundary(d, "x", [width, 0], c);
        if (d.y - r <= 0 && d.q.py >= d.q.y) boundary(d, "x", [width, 0], 0);
        if (d.y + r >= height && d.q.py <= d.q.y) boundary(d, "x", [width, 0], 0);
        //find the layers
        d.y += (d.cy - d.y) * d.frustration() * alpha;
      };
      function boundary(p, y, b, c) {
        if(p.q[y] === p.q["p"+y]) {
          p[y] += (c === 0) || (Math.random() > c) ? ((b[0] < b[1]) ? 1 : -1) :0;
        }else {
          p["p" + y] = 2 * p[y] - p["p" + y];
        }
      }
    }

    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);
        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(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,
                m = Math.pow(quad.point.radius, 3),
                mq = Math.pow(d.radius, 3),
                mT = m + mq;
              if (l < r) {
                //move the nodes away from each other along the radial (normal) vector
                //taking relative mass into consideration, the sign is already established
                //in calculating x and y and the nodes are modelled as spheres for calculating mass
                l = (r - l) / l * alpha;
                d.x += (x *= l) * m/mT;
                d.y += (y *= l) * m/mT;
                quad.point.x -= x * mq/mT;
                quad.point.y -= y * mq/mT;
              }
            }
            return !possible;
          });
        };
      }
    }
    function initNodes(force, n, padding) {
      force.nodes(d3.range(n).map(function() {
        var layer = Math.floor(Math.random() * m),
        //      v = (layer + 1) / m * -Math.log(Math.random());
          v = -Math.log(Math.random());
        return {
          radius: Math.sqrt(v) * maxRadius,
          color : layer,
          cy    : y(layer),
          get v() {
            var d = this;
            return {x: d.x - d.px || d.x || 0, y: d.y - d.py || d.y || 0}
          },
          frustration: (function () {
            //if they can't get home, they get angry, but, as soon as they're home, they're fine
            var anger = 1;
            return function () {
              var d = this, anxious = (Math.abs(d.cy - d.y) > w.rangeBand()/2);
              return anger = anxious ? anger + windUp.value() : 1;
            }
          })()
        };
      }));
//      var collide = Collide(force.nodes(), padding);
      force.start();
      force.nodes().forEach(function(d) {
        d.q = {};
        Object.keys(d).forEach(function(p){
          if(!isNaN(d[p])) Object.defineProperty(d.q, p, {
            get: function () {return Math.round(d[p])}
          });
        })
      });
      return Collide(force.nodes(), padding);
    }
    function update(force, n, padding) {
      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}
      }
    };

  </script>
</body>

thumbnail.png