Understanding and Implementing a Force based graph layout algorithm
- by zcourts
I'm trying to implement a force base graph layout algorithm, based on http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
My first attempt didn't work so I looked at
http://blog.ivank.net/force-based-graph-drawing-in-javascript.html
and
https://github.com/dhotson/springy
I changed my implementation based on what I thought I understood from those two but I haven't managed to get it right and I'm hoping someone can help? JavaScript isn't my strong point so be gentle... If you're wondering why write my own. In reality I have no real reason to write my own I'm just trying to understand how the algorithm is implemented. Especially in my first link, that demo is brilliant.
This is what I've come up with
//support function.bind - https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Function/bind#Compatibility
if (!Function.prototype.bind) {
Function.prototype.bind = function (oThis) {
if (typeof this !== "function") {
// closest thing possible to the ECMAScript 5 internal IsCallable function
throw new TypeError("Function.prototype.bind - what is trying to be bound is not callable");
}
var aArgs = Array.prototype.slice.call(arguments, 1),
fToBind = this,
fNOP = function () {},
fBound = function () {
return fToBind.apply(this instanceof fNOP
? this
: oThis || window,
aArgs.concat(Array.prototype.slice.call(arguments)));
};
fNOP.prototype = this.prototype;
fBound.prototype = new fNOP();
return fBound;
};
}
(function() {
var lastTime = 0;
var vendors = ['ms', 'moz', 'webkit', 'o'];
for(var x = 0; x < vendors.length && !window.requestAnimationFrame; ++x) {
window.requestAnimationFrame = window[vendors[x]+'RequestAnimationFrame'];
window.cancelAnimationFrame =
window[vendors[x]+'CancelAnimationFrame'] || window[vendors[x]+'CancelRequestAnimationFrame'];
}
if (!window.requestAnimationFrame)
window.requestAnimationFrame = function(callback, element) {
var currTime = new Date().getTime();
var timeToCall = Math.max(0, 16 - (currTime - lastTime));
var id = window.setTimeout(function() {
callback(currTime + timeToCall);
},
timeToCall);
lastTime = currTime + timeToCall;
return id;
};
if (!window.cancelAnimationFrame)
window.cancelAnimationFrame = function(id) {
clearTimeout(id);
};
}());
function Graph(o){
this.options=o;
this.vertices={};
this.edges={};//form {vertexID:{edgeID:edge}}
}
/**
*Adds an edge to the graph. If the verticies in this edge are not already in the
*graph then they are added
*/
Graph.prototype.addEdge=function(e){
//if vertex1 and vertex2 doesn't exist in this.vertices add them
if(typeof(this.vertices[e.vertex1])==='undefined')
this.vertices[e.vertex1]=new Vertex(e.vertex1);
if(typeof(this.vertices[e.vertex2])==='undefined')
this.vertices[e.vertex2]=new Vertex(e.vertex2);
//add the edge
if(typeof(this.edges[e.vertex1])==='undefined')
this.edges[e.vertex1]={};
this.edges[e.vertex1][e.id]=e;
}
/**
* Add a vertex to the graph. If a vertex with the same ID already exists then
* the existing vertex's .data property is replaced with the @param v.data
*/
Graph.prototype.addVertex=function(v){
if(typeof(this.vertices[v.id])==='undefined')
this.vertices[v.id]=v;
else
this.vertices[v.id].data=v.data;
}
function Vertex(id,data){
this.id=id;
this.data=data?data:{};
//initialize to data.[x|y|z] or generate random number for each
this.x = this.data.x?this.data.x:-100 + Math.random()*200;
this.y = this.data.y?this.data.y:-100 + Math.random()*200;
this.z = this.data.y?this.data.y:-100 + Math.random()*200;
//set initial velocity to 0
this.velocity = new Point(0, 0, 0);
this.mass=this.data.mass?this.data.mass:Math.random();
this.force=new Point(0,0,0);
}
function Edge(vertex1ID,vertex2ID){
vertex1ID=vertex1ID?vertex1ID:Math.random()
vertex2ID=vertex2ID?vertex2ID:Math.random()
this.id=vertex1ID+"->"+vertex2ID;
this.vertex1=vertex1ID;
this.vertex2=vertex2ID;
}
function Point(x, y, z)
{
this.x = x;
this.y = y;
this.z = z;
}
Point.prototype.plus=function(p){
this.x +=p.x
this.y +=p.y
this.z +=p.z
}
function ForceLayout(o){
this.repulsion = o.repulsion?o.repulsion:200;
this.attraction = o.attraction?o.attraction:0.06;
this.damping = o.damping?o.damping:0.9;
this.graph = o.graph?o.graph:new Graph();
this.total_kinetic_energy =0;
this.animationID=-1;
}
ForceLayout.prototype.draw=function(){
//vertex velocities initialized to (0,0,0) when a vertex is created
//vertex positions initialized to random position when created
cc=0; do{
this.total_kinetic_energy =0;
//for each vertex
for(var i in this.graph.vertices){
var thisNode=this.graph.vertices[i];
// running sum of total force on this particular node
var netForce=new Point(0,0,0)
//for each other node
for(var j in this.graph.vertices){
if(thisNode!=this.graph.vertices[j]){
//net-force := net-force + Coulomb_repulsion( this_node, other_node )
netForce.plus(this.CoulombRepulsion( thisNode,this.graph.vertices[j]))
}
}
//for each spring connected to this node
for(var k in this.graph.edges[thisNode.id]){
//(this node, node its connected to)
//pass id of this node and the node its connected to so hookesattraction
//can update the force on both vertices and return that force to be
//added to the net force
this.HookesAttraction(thisNode.id,
this.graph.edges[thisNode.id][k].vertex2
)
}
// without damping, it moves forever
// this_node.velocity := (this_node.velocity + timestep * net-force) * damping
thisNode.velocity.x=(thisNode.velocity.x+thisNode.force.x)*this.damping;
thisNode.velocity.y=(thisNode.velocity.y+thisNode.force.y)*this.damping;
thisNode.velocity.z=(thisNode.velocity.z+thisNode.force.z)*this.damping;
//this_node.position := this_node.position + timestep * this_node.velocity
thisNode.x=thisNode.velocity.x;
thisNode.y=thisNode.velocity.y;
thisNode.z=thisNode.velocity.z;
//normalize x,y,z???
//total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2
this.total_kinetic_energy +=thisNode.mass*((thisNode.velocity.x+thisNode.velocity.y+thisNode.velocity.z)*
(thisNode.velocity.x+thisNode.velocity.y+thisNode.velocity.z))
}
cc+=1;
}while(this.total_kinetic_energy >0.5)
console.log(cc,this.total_kinetic_energy,this.graph)
this.cancelAnimation();
}
ForceLayout.prototype.HookesAttraction=function(v1ID,v2ID){
var a=this.graph.vertices[v1ID]
var b=this.graph.vertices[v2ID]
var force=new Point(this.attraction*(b.x - a.x),this.attraction*(b.y - a.y),this.attraction*(b.z - a.z))
// hook's attraction
a.force.x += force.x;
a.force.y += force.y;
a.force.z += force.z;
b.force.x += this.attraction*(a.x - b.x);
b.force.y += this.attraction*(a.y - b.y);
b.force.z += this.attraction*(a.z - b.z);
return force;
}
ForceLayout.prototype.CoulombRepulsion=function(vertex1,vertex2){
//http://en.wikipedia.org/wiki/Coulomb's_law
// distance squared = ((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2))
var distanceSquared =
(
(vertex1.x-vertex2.x)*(vertex1.x-vertex2.x)+
(vertex1.y-vertex2.y)*(vertex1.y-vertex2.y)+
(vertex1.z-vertex2.z)*(vertex1.z-vertex2.z)
);
if(distanceSquared==0) distanceSquared = 0.001;
var coul = this.repulsion / distanceSquared;
return new Point(coul * (vertex1.x-vertex2.x),coul * (vertex1.y-vertex2.y), coul * (vertex1.z-vertex2.z));
}
ForceLayout.prototype.animate=function(){
if(this.animating)
this.animationID=requestAnimationFrame(this.animate.bind(this));
this.draw();
}
ForceLayout.prototype.cancelAnimation=function(){
cancelAnimationFrame(this.animationID);
this.animating=false;
}
ForceLayout.prototype.redraw=function(){
this.animating=true;
this.animate();
}
$(document).ready(function(){
var g= new Graph();
for(var i=0;i<=100;i++){
var v1=new Vertex(Math.random(), {})
var v2=new Vertex(Math.random(), {})
var e1= new Edge(v1.id,v2.id);
g.addEdge(e1);
}
console.log(g);
var l=new ForceLayout({
graph:g
});
l.redraw();
});
