2
* Dracula Graph Layout and Drawing Framework 0.0.3alpha
3
* (c) 2010 Philipp Strathausen <strathausen@gmail.com>, http://strathausen.eu
4
* Contributions by Jake Stothard <stothardj@gmail.com>.
6
* based on the Graph JavaScript framework, version 0.0.1
7
* (c) 2006 Aslak Hellesoy <aslak.hellesoy@gmail.com>
8
* (c) 2006 Dave Hoover <dave.hoover@gmail.com>
10
* Ported from Graph::Layouter::Spring in
11
* http://search.cpan.org/~pasky/Graph-Layderer-0.02/
12
* The algorithm is based on a spring-style layouter of a Java-based social
13
* network tracker PieSpy written by Paul Mutton <paul@jibble.org>.
15
* This code is freely distributable under the MIT license. Commercial use is
16
* hereby granted without any cost or restriction.
20
* Graph Dracula JavaScript Framework:
21
* http://graphdracula.net
23
/*--------------------------------------------------------------------------*/
28
var AbstractEdge = function() {
30
AbstractEdge.prototype = {
32
this.connection.fg.hide();
33
this.connection.bg && this.bg.connection.hide();
36
var EdgeFactory = function() {
37
this.template = new AbstractEdge();
38
this.template.style = new Object();
39
this.template.style.directed = false;
40
this.template.weight = 1;
42
EdgeFactory.prototype = {
43
build: function(source, target) {
44
var e = jQuery.extend(true, {}, this.template);
54
var Graph = function() {
57
this.snapshots = []; // previous graph states TODO to be implemented
58
this.edgeFactory = new EdgeFactory();
63
* @id the node's ID (string or number)
64
* @content (optional, dictionary) can contain any information that is
65
* being interpreted by the layout algorithm or the graph
68
addNode: function(id, content) {
69
/* testing if node is already existing in the graph */
70
if(this.nodes[id] == undefined) {
71
this.nodes[id] = new Graph.Node(id, content);
73
return this.nodes[id];
76
addEdge: function(source, target, style) {
77
var s = this.addNode(source);
78
var t = this.addNode(target);
79
var edge = this.edgeFactory.build(s, t);
80
jQuery.extend(edge.style,style);
82
this.edges.push(edge);
83
// NOTE: Even directed edges are added to both nodes.
87
/* TODO to be implemented
88
* Preserve a copy of the graph state (nodes, positions, ...)
89
* @comment a comment describing the state
91
snapShot: function(comment) {
93
var graph = new Graph();
94
graph.nodes = jQuery.extend(true, {}, this.nodes);
95
graph.edges = jQuery.extend(true, {}, this.edges);
96
this.snapshots.push({comment: comment, graph: graph});
99
removeNode: function(id) {
100
delete this.nodes[id];
101
for(var i = 0; i < this.edges.length; i++) {
102
if (this.edges[i].source.id == id || this.edges[i].target.id == id) {
103
this.edges.splice(i, 1);
113
Graph.Node = function(id, node){
117
node.hide = function() {
119
this.shape && this.shape.hide(); /* FIXME this is representation specific code and should be elsewhere */
121
(this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].hide && this.edges[i].hide();
123
node.show = function() {
125
this.shape && this.shape.show();
127
(this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].show && this.edges[i].show();
131
Graph.Node.prototype = {
135
* Renderer base class
140
* Renderer implementation using RaphaelJS
142
Graph.Renderer.Raphael = function(element, graph, width, height) {
143
this.width = width || 800;
144
this.height = height || 800;
146
this.r = Raphael(element, this.width, this.height);
147
this.radius = 40; /* max dimension of a node */
149
this.mouse_in = false;
151
/* TODO default node rendering function */
152
if(!this.graph.render) {
153
this.graph.render = function() {
162
this.dragger = function (e) {
165
selfRef.isDrag = this;
166
this.set && this.set.animate({"fill-opacity": .1}, 200);
167
e.preventDefault && e.preventDefault();
170
var d = document.getElementById(element);
171
d.onmousemove = function (e) {
172
e = e || window.event;
173
if (selfRef.isDrag) {
174
var bBox = selfRef.isDrag.set.getBBox();
175
// TODO round the coordinates here (eg. for proper image representation)
176
var newX = e.clientX - selfRef.isDrag.dx + (bBox.x + bBox.width / 2);
177
var newY = e.clientY - selfRef.isDrag.dy + (bBox.y + bBox.height / 2);
178
/* prevent shapes from being dragged out of the canvas */
179
var clientX = e.clientX - (newX < 20 ? newX - 20 : newX > selfRef.width - 20 ? newX - selfRef.width + 20 : 0);
180
var clientY = e.clientY - (newY < 20 ? newY - 20 : newY > selfRef.height - 20 ? newY - selfRef.height + 20 : 0);
181
selfRef.isDrag.set.translate(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
182
// console.log(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
183
for (var i in selfRef.graph.edges) {
184
selfRef.graph.edges[i].connection && selfRef.graph.edges[i].connection.draw();
186
//selfRef.r.safari();
187
selfRef.isDrag.dx = clientX;
188
selfRef.isDrag.dy = clientY;
191
d.onmouseup = function () {
192
selfRef.isDrag && selfRef.isDrag.set.animate({"fill-opacity": .6}, 500);
193
selfRef.isDrag = false;
197
Graph.Renderer.Raphael.prototype = {
198
translate: function(point) {
200
(point[0] - this.graph.layoutMinX) * this.factorX + this.radius,
201
(point[1] - this.graph.layoutMinY) * this.factorY + this.radius
205
rotate: function(point, length, angle) {
206
var dx = length * Math.cos(angle);
207
var dy = length * Math.sin(angle);
208
return [point[0]+dx, point[1]+dy];
212
this.factorX = (this.width - 2 * this.radius) / (this.graph.layoutMaxX - this.graph.layoutMinX);
213
this.factorY = (this.height - 2 * this.radius) / (this.graph.layoutMaxY - this.graph.layoutMinY);
214
for (i in this.graph.nodes) {
215
this.drawNode(this.graph.nodes[i]);
217
for (var i = 0; i < this.graph.edges.length; i++) {
218
this.drawEdge(this.graph.edges[i]);
222
drawNode: function(node) {
223
var point = this.translate([node.layoutPosX, node.layoutPosY]);
226
/* if node has already been drawn, move the nodes */
228
var oBBox = node.shape.getBBox();
229
var opoint = { x: oBBox.x + oBBox.width / 2, y: oBBox.y + oBBox.height / 2};
230
node.shape.translate(Math.round(point[0] - opoint.x), Math.round(point[1] - opoint.y));
233
}/* else, draw new nodes */
237
/* if a node renderer function is provided by the user, then use it
238
or the default render function instead */
240
node.render = function(r, node) {
241
/* the default node drawing */
242
var color = Raphael.getColor();
243
var ellipse = r.ellipse(0, 0, 30, 20).attr({fill: color, stroke: color, "stroke-width": 2});
244
/* set DOM node ID */
245
ellipse.node.id = node.label || node.id;
248
push(r.text(0, 30, node.label || node.id));
252
/* or check for an ajax representation of the nodes */
254
// TODO ajax representation evaluation
257
shape = node.render(this.r, node).hide();
259
shape.attr({"fill-opacity": .6});
260
/* re-reference to the node an element belongs to, needed for dragging all elements of a node */
261
shape.items.forEach(function(item){ item.set = shape; item.node.style.cursor = "move"; });
262
shape.mousedown(this.dragger);
264
var box = shape.getBBox();
265
shape.translate(Math.round(point[0]-(box.x+box.width/2)),Math.round(point[1]-(box.y+box.height/2)))
266
//console.log(box,point);
267
node.hidden || shape.show();
270
drawEdge: function(edge) {
271
/* if this edge already exists the other way around and is undirected */
274
if(edge.source.hidden || edge.target.hidden) {
275
edge.connection && edge.connection.fg.hide() | edge.connection.bg && edge.connection.bg.hide();
278
/* if edge already has been drawn, only refresh the edge */
279
if(!edge.connection) {
280
edge.style && edge.style.callback && edge.style.callback(edge); // TODO move this somewhere else
281
edge.connection = this.r.connection(edge.source.shape, edge.target.shape, edge.style);
284
//FIXME showing doesn't work well
285
edge.connection.fg.show();
286
edge.connection.bg && edge.connection.bg.show();
287
edge.connection.draw();
291
Graph.Layout.Spring = function(graph) {
293
this.iterations = 500;
294
this.maxRepulsiveForceDistance = 6;
297
this.maxVertexMovement = 0.5;
300
Graph.Layout.Spring.prototype = {
302
this.layoutPrepare();
303
for (var i = 0; i < this.iterations; i++) {
304
this.layoutIteration();
306
this.layoutCalcBounds();
309
layoutPrepare: function() {
310
for (i in this.graph.nodes) {
311
var node = this.graph.nodes[i];
314
node.layoutForceX = 0;
315
node.layoutForceY = 0;
320
layoutCalcBounds: function() {
321
var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
323
for (i in this.graph.nodes) {
324
var x = this.graph.nodes[i].layoutPosX;
325
var y = this.graph.nodes[i].layoutPosY;
327
if(x > maxx) maxx = x;
328
if(x < minx) minx = x;
329
if(y > maxy) maxy = y;
330
if(y < miny) miny = y;
333
this.graph.layoutMinX = minx;
334
this.graph.layoutMaxX = maxx;
335
this.graph.layoutMinY = miny;
336
this.graph.layoutMaxY = maxy;
339
layoutIteration: function() {
340
// Forces on nodes due to node-node repulsions
342
var prev = new Array();
343
for(var c in this.graph.nodes) {
344
var node1 = this.graph.nodes[c];
345
for (var d in prev) {
346
var node2 = this.graph.nodes[prev[d]];
347
this.layoutRepulsive(node1, node2);
353
// Forces on nodes due to edge attractions
354
for (var i = 0; i < this.graph.edges.length; i++) {
355
var edge = this.graph.edges[i];
356
this.layoutAttractive(edge);
359
// Move by the given force
360
for (i in this.graph.nodes) {
361
var node = this.graph.nodes[i];
362
var xmove = this.c * node.layoutForceX;
363
var ymove = this.c * node.layoutForceY;
365
var max = this.maxVertexMovement;
366
if(xmove > max) xmove = max;
367
if(xmove < -max) xmove = -max;
368
if(ymove > max) ymove = max;
369
if(ymove < -max) ymove = -max;
371
node.layoutPosX += xmove;
372
node.layoutPosY += ymove;
373
node.layoutForceX = 0;
374
node.layoutForceY = 0;
378
layoutRepulsive: function(node1, node2) {
379
if (typeof node1 == 'undefined' || typeof node2 == 'undefined')
381
var dx = node2.layoutPosX - node1.layoutPosX;
382
var dy = node2.layoutPosY - node1.layoutPosY;
383
var d2 = dx * dx + dy * dy;
385
dx = 0.1 * Math.random() + 0.1;
386
dy = 0.1 * Math.random() + 0.1;
387
var d2 = dx * dx + dy * dy;
389
var d = Math.sqrt(d2);
390
if(d < this.maxRepulsiveForceDistance) {
391
var repulsiveForce = this.k * this.k / d;
392
node2.layoutForceX += repulsiveForce * dx / d;
393
node2.layoutForceY += repulsiveForce * dy / d;
394
node1.layoutForceX -= repulsiveForce * dx / d;
395
node1.layoutForceY -= repulsiveForce * dy / d;
399
layoutAttractive: function(edge) {
400
var node1 = edge.source;
401
var node2 = edge.target;
403
var dx = node2.layoutPosX - node1.layoutPosX;
404
var dy = node2.layoutPosY - node1.layoutPosY;
405
var d2 = dx * dx + dy * dy;
407
dx = 0.1 * Math.random() + 0.1;
408
dy = 0.1 * Math.random() + 0.1;
409
var d2 = dx * dx + dy * dy;
411
var d = Math.sqrt(d2);
412
if(d > this.maxRepulsiveForceDistance) {
413
d = this.maxRepulsiveForceDistance;
416
var attractiveForce = (d2 - this.k * this.k) / this.k;
417
if(edge.attraction == undefined) edge.attraction = 1;
418
attractiveForce *= Math.log(edge.attraction) * 0.5 + 1;
420
node2.layoutForceX -= attractiveForce * dx / d;
421
node2.layoutForceY -= attractiveForce * dy / d;
422
node1.layoutForceX += attractiveForce * dx / d;
423
node1.layoutForceY += attractiveForce * dy / d;
427
Graph.Layout.Ordered = function(graph, order) {
432
Graph.Layout.Ordered.prototype = {
434
this.layoutPrepare();
435
this.layoutCalcBounds();
438
layoutPrepare: function(order) {
439
for (i in this.graph.nodes) {
440
var node = this.graph.nodes[i];
445
for (i in this.order) {
446
var node = this.order[i];
447
node.layoutPosX = counter;
448
node.layoutPosY = Math.random();
453
layoutCalcBounds: function() {
454
var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
456
for (i in this.graph.nodes) {
457
var x = this.graph.nodes[i].layoutPosX;
458
var y = this.graph.nodes[i].layoutPosY;
460
if(x > maxx) maxx = x;
461
if(x < minx) minx = x;
462
if(y > maxy) maxy = y;
463
if(y < miny) miny = y;
466
this.graph.layoutMinX = minx;
467
this.graph.layoutMaxX = maxx;
469
this.graph.layoutMinY = miny;
470
this.graph.layoutMaxY = maxy;
475
* usefull JavaScript extensions,
478
function log(a) {console.log&&console.log(a);}
481
* Raphael Tooltip Plugin
482
* - attaches an element as a tooltip to another element
484
* Usage example, adding a rectangle as a tooltip to a circle:
486
* paper.circle(100,100,10).tooltip(paper.rect(0,0,20,30));
488
* If you want to use more shapes, you'll have to put them into a set.
491
Raphael.el.tooltip = function (tp) {
493
this.tp.o = {x: 0, y: 0};
497
this.mousemove(function(event){
498
this.tp.translate(event.clientX -
499
this.tp.o.x,event.clientY - this.tp.o.y);
500
this.tp.o = {x: event.clientX, y: event.clientY};
502
this.tp.show().toFront();
512
if (!Array.prototype.forEach)
514
Array.prototype.forEach = function(fun /*, thisp*/)
516
var len = this.length;
517
if (typeof fun != "function")
518
throw new TypeError();
520
var thisp = arguments[1];
521
for (var i = 0; i < len; i++)
524
fun.call(thisp, this[i], i, this);