Posted By

jmah on 01/08/07


Tagged

node layout graphics graph spring


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

shachi
vali29
cartercole


Graph JavaScript framework, version 0.0.1


 / Published in: JavaScript
 

URL: http://www.ajaxian.com/archives/new-javascriptcanvas-graph-library

Mirror of library

  1. /* Graph JavaScript framework, version 0.0.1
  2.  * (c) 2006 Aslak Hellesoy <[email protected]>
  3.  * (c) 2006 Dave Hoover <[email protected]>
  4.  *
  5.  * Ported from Graph::Layouter::Spring in
  6.  * http://search.cpan.org/~pasky/Graph-Layderer-0.02/
  7.  * The algorithm is based on a spring-style layouter of a Java-based social
  8.  * network tracker PieSpy written by Paul Mutton E<lt>[email protected]<gt>.
  9.  *
  10.  * Graph is freely distributable under the terms of an MIT-style license.
  11.  * For details, see the Graph web site: http://dev.buildpatternd.com/trac
  12.  *
  13. /*--------------------------------------------------------------------------*/
  14.  
  15. var Graph = Class.create();
  16. Graph.prototype = {
  17. initialize: function() {
  18. this.nodeSet = {};
  19. this.nodes = [];
  20. this.edges = [];
  21. },
  22.  
  23. addNode: function(value) {
  24. if(typeof value == 'string') {
  25. // Create a new div
  26. var key = value;
  27. var element = document.createElement('div');
  28. element.innerHTML = value;
  29. // THIS DOESN'T WORK!! NEED AN OTHER CONTAINER.
  30. document.appendChild(element);
  31. } else {
  32. // Assuming it's a DOM node *with* and id.
  33. var key = value.id;
  34. var element = value;
  35. }
  36.  
  37. var node = this.nodeSet[key];
  38. if(node == undefined) {
  39. node = new Graph.Node(element);
  40. this.nodeSet[key] = node;
  41. this.nodes.push(node);
  42. }
  43. return node;
  44. },
  45.  
  46. // Uniqueness must be ensured by caller
  47. addEdge: function(source, target) {
  48. var s = this.addNode(source);
  49. var t = this.addNode(target);
  50. var edge = {source: s, target: t};
  51. this.edges.push(edge);
  52. }
  53. };
  54.  
  55. Graph.Node = Class.create();
  56. Graph.Node.prototype = {
  57. initialize: function(value) {
  58. this.value = value;
  59. }
  60. };
  61.  
  62. Graph.Renderer = {};
  63. Graph.Renderer.Basic = Class.create();
  64. Graph.Renderer.Basic.prototype = {
  65. initialize: function(element, graph) {
  66. this.element = element;
  67. this.graph = graph;
  68.  
  69. this.ctx = element.getContext("2d");
  70. this.radius = 20;
  71. this.arrowAngle = Math.PI/10;
  72.  
  73. this.factorX = (element.width - 2 * this.radius) / (graph.layoutMaxX - graph.layoutMinX);
  74. this.factorY = (element.height - 2 * this.radius) / (graph.layoutMaxY - graph.layoutMinY);
  75. },
  76.  
  77. translate: function(point) {
  78. return [
  79. (point[0] - this.graph.layoutMinX) * this.factorX + this.radius,
  80. (point[1] - this.graph.layoutMinY) * this.factorY + this.radius
  81. ];
  82. },
  83.  
  84. rotate: function(point, length, angle) {
  85. var dx = length * Math.cos(angle);
  86. var dy = length * Math.sin(angle);
  87. return [point[0]+dx, point[1]+dy];
  88. },
  89.  
  90. draw: function() {
  91. for (var i = 0; i < this.graph.nodes.length; i++) {
  92. this.drawNode(this.graph.nodes[i]);
  93. }
  94. for (var i = 0; i < this.graph.edges.length; i++) {
  95. this.drawEdge(this.graph.edges[i]);
  96. }
  97. },
  98.  
  99. drawNode: function(node) {
  100. var point = this.translate([node.layoutPosX, node.layoutPosY]);
  101.  
  102. node.value.style.position = 'absolute';
  103. node.value.style.top = point[1] + 'px';
  104. node.value.style.left = point[0] + 'px';
  105.  
  106. this.ctx.strokeStyle = 'black'
  107. this.ctx.beginPath();
  108. this.ctx.arc(point[0], point[1], this.radius, 0, Math.PI*2, true);
  109. this.ctx.closePath();
  110. this.ctx.stroke();
  111. },
  112.  
  113. drawEdge: function(edge) {
  114. var source = this.translate([edge.source.layoutPosX, edge.source.layoutPosY]);
  115. var target = this.translate([edge.target.layoutPosX, edge.target.layoutPosY]);
  116.  
  117. var tan = (target[1] - source[1]) / (target[0] - source[0]);
  118. var theta = Math.atan(tan);
  119. if(source[0] <= target[0]) {theta = Math.PI+theta}
  120. source = this.rotate(source, -this.radius, theta);
  121. target = this.rotate(target, this.radius, theta);
  122.  
  123. // draw the edge
  124. this.ctx.strokeStyle = 'grey';
  125. this.ctx.fillStyle = 'grey';
  126. this.ctx.lineWidth = 1.0;
  127. this.ctx.beginPath();
  128. this.ctx.moveTo(source[0], source[1]);
  129. this.ctx.lineTo(target[0], target[1]);
  130. this.ctx.stroke();
  131.  
  132. this.drawArrowHead(20, this.arrowAngle, theta, source[0], source[1], target[0], target[1]);
  133. },
  134.  
  135. drawArrowHead: function(length, alpha, theta, startx, starty, endx, endy) {
  136. var top = this.rotate([endx, endy], length, theta + alpha);
  137. var bottom = this.rotate([endx, endy], length, theta - alpha);
  138. this.ctx.beginPath();
  139. this.ctx.moveTo(endx, endy);
  140. this.ctx.lineTo(top[0], top[1]);
  141. this.ctx.lineTo(bottom[0], bottom[1]);
  142. this.ctx.fill();
  143. }
  144. };
  145.  
  146. Graph.Layout = {};
  147. Graph.Layout.Spring = Class.create();
  148. Graph.Layout.Spring.prototype = {
  149. initialize: function(graph) {
  150. this.graph = graph;
  151. this.iterations = 500;
  152. this.maxRepulsiveForceDistance = 6;
  153. this.k = 2;
  154. this.c = 0.01;
  155. this.maxVertexMovement = 0.5;
  156. },
  157.  
  158. layout: function() {
  159. this.layoutPrepare();
  160. for (var i = 0; i < this.iterations; i++) {
  161. this.layoutIteration();
  162. }
  163. this.layoutCalcBounds();
  164. },
  165.  
  166. layoutPrepare: function() {
  167. for (var i = 0; i < this.graph.nodes.length; i++) {
  168. var node = this.graph.nodes[i];
  169. node.layoutPosX = 0;
  170. node.layoutPosY = 0;
  171. node.layoutForceX = 0;
  172. node.layoutForceY = 0;
  173. }
  174. },
  175.  
  176. layoutCalcBounds: function() {
  177. var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
  178.  
  179. for (var i = 0; i < this.graph.nodes.length; i++) {
  180. var x = this.graph.nodes[i].layoutPosX;
  181. var y = this.graph.nodes[i].layoutPosY;
  182.  
  183. if(x > maxx) maxx = x;
  184. if(x < minx) minx = x;
  185. if(y > maxy) maxy = y;
  186. if(y < miny) miny = y;
  187. }
  188.  
  189. this.graph.layoutMinX = minx;
  190. this.graph.layoutMaxX = maxx;
  191. this.graph.layoutMinY = miny;
  192. this.graph.layoutMaxY = maxy;
  193. },
  194.  
  195. layoutIteration: function() {
  196. // Forces on nodes due to node-node repulsions
  197. for (var i = 0; i < this.graph.nodes.length; i++) {
  198. var node1 = this.graph.nodes[i];
  199. for (var j = i + 1; j < this.graph.nodes.length; j++) {
  200. var node2 = this.graph.nodes[j];
  201. this.layoutRepulsive(node1, node2);
  202. }
  203. }
  204. // Forces on nodes due to edge attractions
  205. for (var i = 0; i < this.graph.edges.length; i++) {
  206. var edge = this.graph.edges[i];
  207. this.layoutAttractive(edge);
  208. }
  209.  
  210. // Move by the given force
  211. for (var i = 0; i < this.graph.nodes.length; i++) {
  212. var node = this.graph.nodes[i];
  213. var xmove = this.c * node.layoutForceX;
  214. var ymove = this.c * node.layoutForceY;
  215.  
  216. var max = this.maxVertexMovement;
  217. if(xmove > max) xmove = max;
  218. if(xmove < -max) xmove = -max;
  219. if(ymove > max) ymove = max;
  220. if(ymove < -max) ymove = -max;
  221.  
  222. node.layoutPosX += xmove;
  223. node.layoutPosY += ymove;
  224. node.layoutForceX = 0;
  225. node.layoutForceY = 0;
  226. }
  227. },
  228.  
  229. layoutRepulsive: function(node1, node2) {
  230. var dx = node2.layoutPosX - node1.layoutPosX;
  231. var dy = node2.layoutPosY - node1.layoutPosY;
  232. var d2 = dx * dx + dy * dy;
  233. if(d2 < 0.01) {
  234. dx = 0.1 * Math.random() + 0.1;
  235. dy = 0.1 * Math.random() + 0.1;
  236. var d2 = dx * dx + dy * dy;
  237. }
  238. var d = Math.sqrt(d2);
  239. if(d < this.maxRepulsiveForceDistance) {
  240. var repulsiveForce = this.k * this.k / d;
  241. node2.layoutForceX += repulsiveForce * dx / d;
  242. node2.layoutForceY += repulsiveForce * dy / d;
  243. node1.layoutForceX -= repulsiveForce * dx / d;
  244. node1.layoutForceY -= repulsiveForce * dy / d;
  245. }
  246. },
  247.  
  248. layoutAttractive: function(edge) {
  249. var node1 = edge.source;
  250. var node2 = edge.target;
  251.  
  252. var dx = node2.layoutPosX - node1.layoutPosX;
  253. var dy = node2.layoutPosY - node1.layoutPosY;
  254. var d2 = dx * dx + dy * dy;
  255. if(d2 < 0.01) {
  256. dx = 0.1 * Math.random() + 0.1;
  257. dy = 0.1 * Math.random() + 0.1;
  258. var d2 = dx * dx + dy * dy;
  259. }
  260. var d = Math.sqrt(d2);
  261. if(d > this.maxRepulsiveForceDistance) {
  262. d = this.maxRepulsiveForceDistance;
  263. d2 = d * d;
  264. }
  265. var attractiveForce = (d2 - this.k * this.k) / this.k;
  266. if(edge.weight == undefined || edge.weight < 1) edge.weight = 1;
  267. attractiveForce *= Math.log(edge.weight) * 0.5 + 1;
  268.  
  269. node2.layoutForceX -= attractiveForce * dx / d;
  270. node2.layoutForceY -= attractiveForce * dy / d;
  271. node1.layoutForceX += attractiveForce * dx / d;
  272. node1.layoutForceY += attractiveForce * dy / d;
  273. }
  274. };

Report this snippet  

You need to login to post a comment.