Clustering a Force layout with a Quadtree

#Clustering a Force layout with a quadtree#

This is an example of how to use a Quadtree to cluster the nodes that are close to each other in a Force Layout.

With the slider you can select how deep you want to explore the quadtree, and it creates cluster-nodes representing the points that are not going to be displayed.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.node {
  stroke: #fff;
  stroke-width: 1.5px;
}

.link {
  stroke: #999;
  stroke-opacity: .3;
}

</style>
<script src="https://d3js.org/d3.v3.min.js"></script>
<body>
	<label for='slider_cluster'>Cluster</label>
	<input id='slider_cluster' type='range' min='1' max='5' value='8'/><br/>
</body>
<script>

var width = 960,
    height = 500;

var color = d3.scale.category20();

var force = d3.layout.force()
    .charge(-120)
    .linkDistance(30)
    .size([width, height]);

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
    
var _shouldCluster = false,
	_currentNode   = null,
	_howDeep       = 2,
	_nthCluster    = 0;
var pruneNodes= function(original_nodes){
	var nodes =[],q; 
	
	//when the clustering is disable return all the proteins
	if (!_shouldCluster)
		return original_nodes;
		
	//get the current quadtree
	q = d3.geom.quadtree(original_nodes);
	q.depth = 0; // root
	q.quadrant="0";
	
	//Tag all the proteins to be hidden
	original_nodes.forEach(function(o, i) { o.toshow=false; });

//To use in quadtree.visit, to select what to show.
	var what2show = function(node, x1, y1, x2, y2){
		//determine the depth of the children 
		for (var i=0; i<4; i++) {
			if (node.nodes[i]){
				node.nodes[i].depth = node.depth+1;
			}
		}
		if (node.leaf && node.point!=null) {
			node.point.toshow = true; //tag the node to show if has reach a leaf
		}else{
			node.cluster=null;
			//takes the decision of going deeper into the tree
			if (!shouldGoDeeper(node)){// && node.cluster==null){
				//in case it is determined to stop at this node, it creates a new cluster in that node.
				node.cluster= {
					id: "Cluster_"+_nthCluster,
					name: "cluster "+ (_nthCluster++),
					nodes:[],
					isCluster: true,
					px: x1,
					py: y1,
					size: 1,
					weight: 1,
					x: x1,
					y: y1,
					fixed:true,
					group:15
				};
				nodes.push(node.cluster);
				return true;
			}
		}
		return false;
	};

//To use in quadtree.visit, to find the cluster that a protein belongs to.
	var addCurrentNodeToCluster = function(node, x1, y1, x2, y2){
		if (_currentNode==null)
			return true;
		if (x1<=_currentNode.x && _currentNode.x<=x2 && y1<=_currentNode.y && _currentNode.y<=y2){
			if (node.cluster != null){
				node.cluster.nodes.push(_currentNode);
				_currentNode.cluster=node.cluster;
				return true;
			}
			if (node.leaf)
				return true;
			return false;
		}
		return true;
	};
	
	//goes trhought the tree marking what to show and creating clusters.
	q.visit(what2show);
	
	//Goes through all the proteins to include the ones to show in the nodes array() or to find its cluster 
	original_nodes.forEach(function(o, i) {
		if (o.toshow){
			nodes.push(o);
		}else{
			_currentNode=o;
			_currentNode.cluster=null;
			q.visit(addCurrentNodeToCluster);
			calculateCentroid(_currentNode.cluster);
			_currentNode=null;
		}
	});

return nodes;
};

var shouldGoDeeper = function(node){
	return _howDeep > node.depth;
};

}
	});
	return links;
};
var response=null;
d3.json("miserables.json", function(error, graph) {
  response=graph;
  update();
  force.on("tick", function() {
    svg.selectAll(".link").attr("x1", function(d) { return d.source.x; })
        .attr("y1", function(d) { return d.source.y; })
        .attr("x2", function(d) { return d.target.x; })
        .attr("y2", function(d) { return d.target.y; });

svg.selectAll(".node").attr("cx", function(d) { return d.x; })
        .attr("cy", function(d) { return d.y; });
  });

});

var update=function(){
  var data_nodes = pruneNodes(response.nodes),
      data_links = pruneLinks(response.links);
  force
      .nodes(data_nodes)
      .links(data_links)
      .start();

var links = svg.selectAll(".link")
      .data(data_links);
  var link =links
    .enter().append("line")
      .attr("class", "link")
      .style("stroke-width", function(d) { return Math.sqrt(d.value); });

links.exit().remove();

var nodes = svg.selectAll(".node")
      .data(data_nodes);
  var node = nodes
    .enter().append("circle")
      .attr("class", "node")
      
      .call(force.drag);
        
  nodes.attr("r", function(d) {
							return 5* Math.sqrt((d.isCluster)?d.nodes.length:1);
						})
.style("fill", function(d) { return color(d.group); });

node.append("title")
      .text(function(d) { return d.name; });
  
  nodes.exit().remove();

};
  d3.select("input[type=range]").on("change", function() {
    _shouldCluster=true;
    _howDeep=+this.value;
    update();
  });
</script>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js