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
|| 400;
144 this.height
= height
|| 400;
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) && this.set.toFront();
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);