D3 Examples - Union-Find Visualization

xxxxxxxxxx
 
<!-- Union-Find Visualization
 
Start with a bunch of nodes that are not connected.  Repeatedly,
select two rows at random, apply the union operation, and show the
resulting graph data structure after the operation.
-->
<body>
<script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script>
function union(node_a, node_b) {
  var root_a = get_root(node_a);
  var root_b = get_root(node_b);
  if(root_a.key <= root_b.key) {
    set_root(node_a, root_a);
    set_root(node_b, root_a);
  } else {
    set_root(node_a, root_b);
    set_root(node_b, root_b);
  }
}
 
function get_root(node) {
  while (node != node.root) {
    node = node.root;
  }
  return node;
}
 
function set_root(node, root) {
  while(node.root != root) {
    var next = node.root;
    node.root = root;
    node = next;
  }
}
 
var nodes = [];
 
var width = 960;
var height = 500;
 
var force = d3.layout.force()
  .friction(.7)
  .charge(-120)
  .linkDistance(30)
  .linkStrength(0.5)
  .size([width, height]);
 
var svg = d3.select("body").append("svg")
  .attr("width", width)
  .attr("height", height);
var lines = svg.append("g");
var circles = svg.append("g");
 
var union_a;
var union_b;
 
function reset() {
  nodes = [];
 
  for(var i = 0; i < 50; ++i) {
    var node = {};
    node.root = node;
    node.key = i;
    nodes.push(node);
  }
 
  force.nodes(nodes);
 
  var data = circles.selectAll("*").data(nodes);
  data.exit().remove();
  data.enter().append("circle")
    .attr("r", 8)
    .style("fill", function(d) { var val = 100 + 155*d.key/nodes.length;
                                 return d3.rgb(0, val, val); })
    .call(force.drag);
 
  display();
  d3.timer(reset, 80000);
  return true;
}
 
function display() {
  var links = [];
  for (var i = 0; i < nodes.length; ++i) {
    var node = nodes[i];
    if(node != node.root) {
      links.push({source:node, target:node.root});
    }
  }
 
  force.links(links);
 
  var data = lines.selectAll("*").data(links);
  data.exit().remove()
  data.enter().append("line")
    .style("stroke-width", 2)
    .style("stroke", d3.rgb(80,80,80));
 
  circles.selectAll("*")
    .style("stroke-width", function(d) { return d == union_a || d == union_b ? 3 : 1; })
    .style("stroke", function(d) { return d == union_a || d == union_b ? "red"
                                        : d == d.root ? "blue" : "none"; });
 
  force.start();
}
 
function choose() {
  var a = Math.floor(Math.random()*nodes.length);
  var b = Math.floor(Math.random()*(nodes.length-1));
  if (a <= b) ++b;
  union_a = nodes[a];
  union_b = nodes[b];
  display();
  d3.timer(animate, 800);
  return true;
}
 
function animate() {
  union(union_a, union_b);
  display();
  d3.timer(choose, 800);
  return true;
}
 
force.on("tick", function() {
  var link = lines.selectAll("*");
  var node = circles.selectAll("*");
  link.attr("x1", function(d) { return d.source.x; });
  link.attr("y1", function(d) { return d.source.y; });
  link.attr("x2", function(d) { return d.target.x; });
  link.attr("y2", function(d) { return d.target.y; });
  node.attr("cx", function(d) { return d.x; });
  node.attr("cy", function(d) { return d.y; });
});
 
reset();
choose();
</script>
    