content/blog/graphs/graphs.js (view raw)
1// -------------------------------------------------------------------------- //
2// Constants
3var INTERPOLATION = 0.6;
4
5var BOX_HEIGHT = 0.15; // %, from and to which drop the items
6var BOX_HOVER = [255, 0, 0];
7var BOX_NORMAL = [255, 200, 200];
8
9var NODE_NORMAL = '#000';
10var NODE_TEXT = '#fff';
11var NODE_FONT = 'px Georgia';
12
13var FRAME_DURATION = 25; // ms
14
15// -------------------------------------------------------------------------- //
16// Retrieve used HTML elements
17canvas = document.getElementById('canvas');
18matrixTable = document.getElementById('matrixTable');
19matrixOrder = document.getElementById('matrixOrder');
20matrixAccum = document.getElementById('matrixAccum');
21matrixTableWrapper = document.getElementById('matrixTableWrapper');
22
23// -------------------------------------------------------------------------- //
24// Variables
25var orderShown, accumShown;
26c = canvas.getContext('2d');
27
28// Box color, from which and to which nodes should be dragged
29var boxColor = BOX_NORMAL.slice();
30
31// Available nodes and their connection matrix- these should be kept in sync
32var nodes = [];
33var connMatrix = Array.matrix(0, 0, 0);
34
35// Which node was the first we right clicked to create a new connection?
36var startConn = null;
37
38// Are we dragging any node yet?
39var anyDragging = false;
40
41// Highlight mode [row, col, color] for the matrix representing the graph
42var highlight = [-1, -1, '#fff'];
43
44function updateOrder() {
45 orderShown = Number(matrixOrder.value);
46 accumShown = matrixAccum.checked;
47 calcShowConnMatrix();
48}
49updateOrder();
50
51// -------------------------------------------------------------------------- //
52// Declare a prototype (Node) to render the selectable elements
53function Node(x, y, r, id) {
54 this.x = x;
55 this.y = y;
56 this.r = r;
57 this.id = id;
58 this.color = null;
59 this.dragging = false;
60
61 this.draw = function() {
62 if (this.dragging) {
63 c.fillStyle = NODE_NORMAL;
64 this.x = lerp(this.x, canvas.mouseX, INTERPOLATION);
65 this.y = lerp(this.y, canvas.mouseY, INTERPOLATION);
66 } else {
67 c.fillStyle = this.color;
68 }
69 c.circle(this.x, this.y, this.r);
70
71 c.fillStyle = NODE_TEXT;
72 c.font = ''+r+NODE_FONT;
73 // Arbitrary but nice
74 var x = this.x - r * 0.3;
75 var y = this.y + r * 0.3;
76
77 c.fillText(""+this.id, x, y);
78 }
79
80 this.resetColor = function() {
81 this.color = '#777';
82 }
83 this.resetColor();
84
85 this.inBounds = function(x, y) {
86 return Math.abs(this.x - x) < this.r &&
87 Math.abs(this.y - y) < this.r;
88 }
89}
90
91// -------------------------------------------------------------------------- //
92// Node handling
93function addNode(x, y) {
94 nodes.push(new Node(x, y, 20, nodes.length + 1));
95 limitOrder(nodes.length);
96
97 var newMatrix = Array.matrix(nodes.length, nodes.length, 0);
98 matrixCpy(connMatrix, newMatrix);
99 setConnMatrix(newMatrix);
100}
101
102function deleteNode(at) {
103 nodes.splice(at, 1);
104 limitOrder(nodes.length);
105
106 // Re-set the nodes IDs
107 for (var i = 0; i != nodes.length; ++i) {
108 nodes[i].id = i+1;
109 }
110
111 // Pop the at'th row (connections from the node we deleted)
112 // and also the at'th column (connections to the node we deleted)
113 setConnMatrix(matrixPop(connMatrix, at, at));
114}
115
116function clearNodes() {
117 nodes.length = 0;
118 limitOrder(1);
119 resetConnections();
120}
121
122// -------------------------------------------------------------------------- //
123// Connection matrix handling
124function setConnMatrix(matrix) {
125 connMatrix = matrix;
126 makeNodesHighlightable(matrixTable, connMatrix);
127 calcShowConnMatrix();
128}
129
130function resetConnections() {
131 setConnMatrix(Array.matrix(nodes.length, nodes.length, 0));
132}
133
134// -------------------------------------------------------------------------- //
135// Matrix representation
136function calcShowConnMatrix() {
137 if (orderShown > 1) {
138 var multiplied = Array.matrix(nodes.length, nodes.length, 0);
139 matrixCpy(connMatrix, multiplied);
140
141 if (accumShown) {
142 var shown = Array.matrix(nodes.length, nodes.length, 0);
143 matrixCpy(connMatrix, shown);
144 }
145
146 for (var i = 1; i != orderShown; ++i) {
147 multiplied = matrixMul(connMatrix, multiplied);
148 if (accumShown) {
149 matrixAdd(multiplied, shown);
150 }
151 }
152 if (accumShown) {
153 matrixRepr(shown, matrixTable, highlight);
154 } else {
155 matrixRepr(multiplied, matrixTable, highlight);
156 }
157 } else {
158 matrixRepr(connMatrix, matrixTable, highlight);
159 }
160}
161
162// Makes a table "highlightable" (when the mouse hovers,
163// it will be redrawn) by using the specified matrix.
164function makeNodesHighlightable(table, matrix) {
165 table.matrix = matrix;
166 table.addEventListener('mousemove', function(e) {
167 if (!table.matrix && !table.matrix[0])
168 return;
169
170 // TODO I know, this shouldn't have to go here and I should make a
171 // better script to show the whole path and stuff... oh well.
172 if (orderShown > 1) {
173 if (highlight[0] != -1 || highlight[1] != -1) {
174 highlight[0] = highlight[1] = -1;
175 for (var i = 0; i != nodes.length; ++i)
176 nodes[i].resetColor();
177 calcShowConnMatrix();
178 }
179 return;
180 }
181
182 var rect = table.getBoundingClientRect();
183 var x = e.clientX - rect.left;
184 var y = e.clientY - rect.top;
185
186 var colWidth = rect.width / (table.matrix[0].length+1);
187 var col = Math.floor(x / colWidth)-1;
188
189 var rowHeight = rect.height / (table.matrix.length+1);
190 var row = Math.floor(y / rowHeight)-1;
191
192 if (row != highlight[0] || col != highlight[1]) {
193 highlight[0] = row;
194 highlight[1] = col;
195 if (row >= 0 && col >= 0) {
196 if (table.matrix[row][col]) {
197 // there is a connection so color them
198 nodes[row].color = '#77f';
199 nodes[col].color = '#7f7';
200 highlight[2] = '#afa';
201 } else {
202 // no connection so reset its colors
203 for (var i = 0; i != nodes.length; ++i)
204 nodes[i].resetColor();
205
206 highlight[2] = '#faa';
207 }
208 }
209 calcShowConnMatrix();
210 }
211
212 }, false);
213}
214
215// -------------------------------------------------------------------------- //
216// Canvas rendering
217function renderElements() {
218 c.clear();
219 if (canvas.mouseDown && canvas.mouseY < canvas.height * BOX_HEIGHT) {
220 boxColor = lerpArray(boxColor, BOX_HOVER, 0.2);
221 } else {
222 boxColor = lerpArray(boxColor, BOX_NORMAL, 0.2);
223 }
224 c.rect(0, 0, canvas.width, canvas.height * BOX_HEIGHT);
225 c.fillStyle = 'rgb(' +
226 Math.round(boxColor[0]) + ',' +
227 Math.round(boxColor[1]) + ',' +
228 Math.round(boxColor[2]) + ')';
229 c.fill();
230
231
232 if (nodes.length == 0)
233 return;
234
235 for (var i = 0; i != nodes.length; ++i)
236 nodes[i].draw();
237
238 c.strokeStyle = '#f00';
239
240 var ii = connMatrix.length;
241 var jj = connMatrix.length;
242
243 var x0, y0, x1, y1, cos, sin;
244 var rsq = Math.pow(nodes[0].r + 40, 2); // Radius SQuared + some margin
245 for (var i = 0; i != ii; ++i) {
246 for (var j = 0; j != jj; ++j) {
247 if (connMatrix[i][j]) {
248 // Non-zero item, this implies a connection between nodes.
249 // An element on the matrix connects row (i) -> column (j)
250 x0 = nodes[i].x;
251 y0 = nodes[i].y;
252 x1 = nodes[j].x;
253 y1 = nodes[j].y;
254
255 // Interpolate a bit to exit the radius unless we're too close
256 if (Math.pow(y1 - y0, 2) + Math.pow(x1 - x0, 2) > rsq) {
257 var angle = Math.atan2(y1 - y0, x1 - x0);
258 cos = Math.cos(angle) * nodes[0].r;
259 sin = Math.sin(angle) * nodes[0].r;
260 x0 += cos;
261 y0 += sin;
262 x1 -= cos;
263 y1 -= sin;
264 }
265 c.arrow(x0, y0, x1, y1);
266 }
267 }
268 }
269
270 if (startConn != null) {
271 c.arrow(nodes[startConn].x, nodes[startConn].y,
272 canvas.mouseX, canvas.mouseY);
273 }
274}
275
276function renderLoop() {
277 renderElements();
278 setTimeout(renderLoop, FRAME_DURATION);
279}
280
281// -------------------------------------------------------------------------- //
282// HTML interaction
283
284// To limit the maximum orden which can be specified on the HTML and
285// also clamp the currently shown order to the limit if it's exceeded
286function limitOrder(value) {
287 matrixOrder.max = value;
288 if (orderShown > value) {
289 orderShown = value;
290 matrixOrder.value = '' + value;
291 }
292}
293
294canvas.addEventListener('mousedown', function(e) {
295 if (e.button == 0) {
296 if (canvas.mouseY < canvas.height * BOX_HEIGHT) {
297 // Add node
298 addNode(canvas.mouseX, 0);
299 nodes[nodes.length - 1].dragging = true;
300 anyDragging = true;
301 } else {
302 // Drag nodes
303 for (var i = nodes.length; i--;) {
304 if (nodes[i].inBounds(canvas.mouseX, canvas.mouseY)) {
305 nodes[i].dragging = true;
306 anyDragging = true;
307 break;
308 }
309 }
310 }
311 canvas.style.cursor = anyDragging ? "crosshair" : "default";
312
313 } else if (e.button == 2) {
314 // Right button, select two nodes to join
315 if (startConn == null) {
316 for (var i = nodes.length; i--;) {
317 if (nodes[i].inBounds(canvas.mouseX, canvas.mouseY)) {
318 startConn = i;
319 break;
320 }
321 }
322 }
323 } else if (e.button == 1) {
324 // Middle click, clear the connections from and to a given node
325 for (var i = nodes.length; i--;) {
326 if (nodes[i].inBounds(canvas.mouseX, canvas.mouseY)) {
327 for (var j = 0; j != nodes.length; ++j)
328 connMatrix[i][j] = 0;
329 break;
330 }
331 }
332 }
333
334 canvas.mouseDown = e.button == 0 ? 'L' : 'R';
335}, false);
336
337canvas.addEventListener('mouseup', function(e) {
338 canvas.mouseDown = '';
339
340 if (anyDragging) {
341 anyDragging = false;
342 for (var i = nodes.length; i--; ) {
343 if (nodes[i].dragging) {
344 if (canvas.mouseY < canvas.height * BOX_HEIGHT) {
345 deleteNode(i);
346 } else {
347 nodes[i].dragging = false;
348 }
349 }
350 }
351 } else if (startConn != null) {
352 for (var i = nodes.length; i--;) {
353 if (nodes[i].inBounds(canvas.mouseX, canvas.mouseY)) {
354 // Node row connected to node column
355 if (i != startConn)
356 connMatrix[startConn][i] = 1;
357 break;
358 }
359 }
360 startConn = null;
361 }
362
363 calcShowConnMatrix();
364}, false);
365
366canvas.addEventListener('mousemove', function(e) {
367 var rect = canvas.getBoundingClientRect();
368 canvas.mouseX = e.clientX - rect.left;
369 canvas.mouseY = e.clientY - rect.top;
370
371}, false);
372
373// -------------------------------------------------------------------------- //
374// Represent the example we walked through
375function lilNoise() {
376 return (Math.random() - 0.5) * canvas.width * 0.05;
377}
378
379function getNoiseX(relative) {
380 return canvas.width * relative + lilNoise();
381}
382
383function getNoiseY(relative) {
384 return canvas.height * relative + lilNoise();
385}
386
387addNode(getNoiseX(0.2), getNoiseY(0.5));
388addNode(getNoiseX(0.5), getNoiseY(0.3));
389addNode(getNoiseX(0.8), getNoiseY(0.5));
390addNode(getNoiseX(0.7), getNoiseY(0.7));
391addNode(getNoiseX(0.3), getNoiseY(0.7));
392
393setConnMatrix([
394 [0, 1, 0, 0, 0],
395 [1, 0, 0, 0, 1],
396 [0, 0, 0, 1, 0],
397 [0, 1, 1, 0, 0],
398 [1, 0, 0, 1, 0]
399]);
400
401calcShowConnMatrix();
402
403
404// Let's go!
405renderLoop();