2 * Various algorithms and data structures, licensed under the MIT-license.
3 * (c) 2010 by Johann Philipp Strathausen <strathausen@gmail.com>
4 * http://strathausen.eu
13 Path-finding algorithm, finds the shortest paths from one node to all nodes.
18 O( |E| · |V| ), where E = edges and V = vertices (nodes)
23 Can run on graphs with negative edge weights as long as they do not have
24 any negative weight cycles.
27 function bellman_ford(g
, source
) {
29 /* STEP 1: initialisation */
31 g
.nodes
[n
].distance
= Infinity
;
32 /* predecessors are implicitly null */
35 step("Initially, all distances are infinite and all predecessors are null.");
37 /* STEP 2: relax each edge (this is at the heart of Bellman-Ford) */
38 /* repeat this for the number of nodes minus one */
39 for(var i
= 1; i
< g
.nodes
.length
; i
++)
41 for(var e
in g
.edges
) {
42 var edge
= g
.edges
[e
];
43 if(edge
.source
.distance
+ edge
.weight
< edge
.target
.distance
) {
44 step("Relax edge between " + edge
.source
.id
+ " and " + edge
.target
.id
+ ".");
45 edge
.target
.distance
= edge
.source
.distance
+ edge
.weight
;
46 edge
.target
.predecessor
= edge
.source
;
48 //Added by Jake Stothard (Needs to be tested)
49 if(!edge
.style
.directed
) {
50 if(edge
.target
.distance
+ edge
.weight
< edge
.source
.distance
) {
51 g
.snapShot("Relax edge between "+edge
.target
.id
+" and "+edge
.source
.id
+".");
52 edge
.source
.distance
= edge
.target
.distance
+ edge
.weight
;
53 edge
.source
.predecessor
= edge
.target
;
59 /* STEP 3: TODO Check for negative cycles */
60 /* For now we assume here that the graph does not contain any negative
61 weights cycles. (this is left as an excercise to the reader[tm]) */
67 Path-finding algorithm Dijkstra
69 - worst-case running time is O((|E| + |V|) · log |V| ) thus better than
70 Bellman-Ford for sparse graphs (with less edges), but cannot handle
73 function dijkstra(g
, source
) {
75 /* initially, all distances are infinite and all predecessors are null */
77 g
.nodes
[n
].distance
= Infinity
;
78 /* predecessors are implicitly null */
80 g
.snapShot("Initially, all distances are infinite and all predecessors are null.");
83 /* set of unoptimized nodes, sorted by their distance (but a Fibonacci heap
85 var q
= new BinaryMinHeap(g
.nodes
, "distance");
87 /* pointer to the node in focus */
90 /* get the node with the smallest distance
91 as long as we have unoptimized nodes. q.min() can have O(log n). */
92 while(q
.min() != undefined) {
93 /* remove the latest */
94 node
= q
.extractMin();
95 node
.optimized
= true;
97 /* no nodes accessible from this one, should not happen */
98 if(node
.distance
== Infinity
)
99 throw "Orphaned node!";
101 /* for each neighbour of node */
102 for(e
in node
.edges
) {
103 var other
= (node
== node
.edges
[e
].target
) ? node
.edges
[e
].source
: node
.edges
[e
].target
;
108 /* look for an alternative route */
109 var alt
= node
.distance
+ node
.edges
[e
].weight
;
111 /* update distance and route if a better one has been found */
112 if (alt
< other
.distance
) {
114 /* update distance of neighbour */
115 other
.distance
= alt
;
117 /* update priority queue */
121 other
.predecessor
= node
;
122 g
.snapShot("Enhancing node.")
129 /* All-Pairs-Shortest-Paths */
130 /* Runs at worst in O(|V|³) and at best in Omega(|V|³) :-)
131 complexity Sigma(|V|²) */
132 /* This implementation is not yet ready for general use, but works with the
133 Dracula graph library. */
134 function floyd_warshall(g
, source
) {
136 /* Step 1: initialising empty path matrix (second dimension is implicit) */
139 var n
= g
.nodes
.length
;
141 /* construct path matrix, initialize with Infinity */
146 path
[j
][i
] = j
== i
? 0 : Infinity
;
149 /* initialize path with edge weights */
151 path
[g
.edges
[e
].source
.id
][g
.edges
[e
].target
.id
] = g
.edges
[e
].weight
;
153 /* Note: Usually, the initialisation is done by getting the edge weights
154 from a node matrix representation of the graph, not by iterating through
155 a list of edges as done here. */
157 /* Step 2: find best distances (the heart of Floyd-Warshall) */
161 if(path
[i
][j
] > path
[i
][k
] + path
[k
][j
]) {
162 path
[i
][j
] = path
[i
][k
] + path
[k
][j
];
163 /* Step 2.b: remember the path */
169 /* Step 3: Path reconstruction, get shortest path */
170 function getPath(i
, j
) {
171 if(path
[i
][j
] == Infinity
)
172 throw "There is no path.";
173 var intermediate
= next
[i
][j
];
174 if(intermediate
== undefined)
177 return getPath(i
, intermediate
)
178 .concat([intermediate
])
179 .concat(getPath(intermediate
, j
));
182 /* TODO use the knowledge, e.g. mark path in graph */
188 Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed
189 graph from source to sink.
194 O(E * max(f)), max(f) being the maximum flow
199 As long as there is an open path through the residual graph, send the
200 minimum of the residual capacities on the path.
205 The algorithm works only if all weights are integers. Otherwise it is
206 possible that the Ford–Fulkerson algorithm will not converge to the maximum
219 Maximum flow from Source s to Target t
225 Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed
226 graph from source to sink. An implementation of the Ford-Fulkerson
237 g - Graph object (with node and edge lists, capacity is a property of edge)
242 function edmonds_karp(g
, s
, t
) {
247 A simple binary min-heap serving as a priority queue
248 - takes an array as the input, with elements having a key property
249 - elements will look like this:
251 key: "... key property ...",
252 value: "... element content ..."
254 - provides insert(), min(), extractMin() and heapify()
255 - example usage (e.g. via the Firebug or Chromium console):
256 var x = {foo: 20, hui: "bla"};
257 var a = new BinaryMinHeap([x,{foo:3},{foo:10},{foo:20},{foo:30},{foo:6},{foo:1},{foo:3}],"foo");
258 console.log(a.extractMin());
259 console.log(a.extractMin());
260 x.foo = 0; // update key
261 a.heapify(); // call this always after having a key updated
262 console.log(a.extractMin());
263 console.log(a.extractMin());
264 - can also be used on a simple array, like [9,7,8,5]
266 function BinaryMinHeap(array
, key
) {
268 /* Binary tree stored in an array, no need for a complicated data structure */
271 var key
= key
|| 'key';
273 /* Calculate the index of the parent or a child */
274 var parent = function(index
) { return Math
.floor((index
- 1)/2); };
275 var right = function(index
) { return 2 * index
+ 2; };
276 var left = function(index
) { return 2 * index
+ 1; };
278 /* Helper function to swap elements with their parent
279 as long as the parent is bigger */
280 function bubble_up(i
) {
282 while((p
>= 0) && (tree
[i
][key
] < tree
[p
][key
])) {
283 /* swap with parent */
284 tree
[i
] = tree
.splice(p
, 1, tree
[i
])[0];
285 /* go up one level */
291 /* Helper function to swap elements with the smaller of their children
292 as long as there is one */
293 function bubble_down(i
) {
297 /* as long as there are smaller children */
298 while(tree
[l
] && (tree
[i
][key
] > tree
[l
][key
]) || tree
[r
] && (tree
[i
][key
] > tree
[r
][key
])) {
300 /* find smaller child */
301 var child
= tree
[l
] ? tree
[r
] ? tree
[l
][key
] > tree
[r
][key
] ? r
: l
: l
: l
;
303 /* swap with smaller child with current element */
304 tree
[i
] = tree
.splice(child
, 1, tree
[i
])[0];
306 /* go up one level */
313 /* Insert a new element with respect to the heap property
314 1. Insert the element at the end
315 2. Bubble it up until it is smaller than its parent */
316 this.insert = function(element
) {
318 /* make sure there's a key property */
319 (element
[key
] == undefined) && (element
= {key
:element
});
321 /* insert element at the end */
324 /* bubble up the element */
325 bubble_up(tree
.length
- 1);
328 /* Only show us the minimum */
329 this.min = function() {
330 return tree
.length
== 1 ? undefined : tree
[0];
333 /* Return and remove the minimum
334 1. Take the root as the minimum that we are looking for
335 2. Move the last element to the root (thereby deleting the root)
336 3. Compare the new root with both of its children, swap it with the
337 smaller child and then check again from there (bubble down)
339 this.extractMin = function() {
340 var result
= this.min();
342 /* move the last element to the root or empty the tree completely */
343 /* bubble down the new root if necessary */
344 (tree
.length
== 1) && (tree
= []) || (tree
[0] = tree
.pop()) && bubble_down(0);
349 /* currently unused, TODO implement */
350 this.changeKey = function(index
, key
) {
351 throw "function not implemented";
354 this.heapify = function() {
355 for(var start
= Math
.floor((tree
.length
- 2) / 2); start
>= 0; start
--) {
360 /* insert the input elements one by one only when we don't have a key property (TODO can be done more elegant) */
361 for(i
in (array
|| []))
362 this.insert(array
[i
]);
369 1. Select some random value from the array, the median.
370 2. Divide the array in three smaller arrays according to the elements
371 being less, equal or greater than the median.
372 3. Recursively sort the array containg the elements less than the
373 median and the one containing elements greater than the median.
374 4. Concatenate the three arrays (less, equal and greater).
375 5. One or no element is always sorted.
376 TODO: This could be implemented more efficiently by using only one array object and several pointers.
378 function quickSort(arr
) {
379 /* recursion anchor: one element is always sorted */
380 if(arr
.length
<= 1) return arr
;
381 /* randomly selecting some value */
382 var median
= arr
[Math
.floor(Math
.random() * arr
.length
)];
383 var arr1
= [], arr2
= [], arr3
= [];
385 arr
[i
] < median
&& arr1
.push(arr
[i
]);
386 arr
[i
] == median
&& arr2
.push(arr
[i
]);
387 arr
[i
] > median
&& arr3
.push(arr
[i
]);
389 /* recursive sorting and assembling final result */
390 return quickSort(arr1
).concat(arr2
).concat(quickSort(arr3
));
395 1. Select the minimum and remove it from the array
396 2. Sort the rest recursively
397 3. Return the minimum plus the sorted rest
398 4. An array with only one element is already sorted
400 function selectionSort(arr
) {
401 /* recursion anchor: one element is always sorted */
402 if(arr
.length
== 1) return arr
;
403 var minimum
= Infinity
;
406 if(arr
[i
] < minimum
) {
408 index
= i
; /* remember the minimum index for later removal */
411 /* remove the minimum */
412 arr
.splice(index
, 1);
413 /* assemble result and sort recursively (could be easily done iteratively as well)*/
414 return [minimum
].concat(selectionSort(arr
));
419 1. Cut the array in half
420 2. Sort each of them recursively
421 3. Merge the two sorted arrays
422 4. An array with only one element is considered sorted
425 function mergeSort(arr
) {
426 /* merges two sorted arrays into one sorted array */
427 function merge(a
, b
) {
430 /* as long as there are elements in the arrays to be merged */
431 while(a
.length
> 0 || b
.length
> 0){
432 /* are there elements to be merged, if yes, compare them and merge */
433 var n
= a
.length
> 0 && b
.length
> 0 ? a
[0] < b
[0] ? a
.shift() : b
.shift() : b
.length
> 0 ? b
.shift() : a
.length
> 0 ? a
.shift() : null;
434 /* always push the smaller one onto the result set */
435 n
!= null && c
.push(n
);
439 /* this mergeSort implementation cuts the array in half, wich should be fine with randomized arrays, but introduces the risk of a worst-case scenario */
440 median
= Math
.floor(arr
.length
/ 2);
441 var part1
= arr
.slice(0, median
); /* for some reason it doesn't work if inserted directly in the return statement (tried so with firefox) */
442 var part2
= arr
.slice(median
- arr
.length
);
443 return arr
.length
<= 1 ? arr
: merge(
444 mergeSort(part1
), /* first half */
445 mergeSort(part2
) /* second half */
449 /* Balanced Red-Black-Tree */
450 function RedBlackTree(arr
) {
454 function BTree(arr
) {
458 function NaryTree(n
, arr
) {
463 * Knuth-Morris-Pratt string matching algorithm - finds a pattern in a text.
464 * FIXME: Doesn't work correctly yet.
469 * PREFIX, OVERLAP or FALIURE function for KMP. Computes how many iterations
470 * the algorithm can skip after a mismatch.
472 * @input p - pattern (string)
473 * @result array of skippable iterations
476 /* pi contains the computed skip marks */
478 for(q
= 1; q
< p
.length
; q
++) {
479 while(k
> 0 && (p
.charAt(k
) != p
.charAt(q
)))
482 (p
.charAt(k
) == p
.charAt(q
)) && k
++;
489 /* The actual KMP algorithm starts here. */
491 var pi
= prefix(p
), q
= 0, result
= [];
493 for(var i
= 0; i
< t
.length
; i
++) {
494 /* jump forward as long as the character doesn't match */
495 while((q
> 0) && (p
.charAt(q
) != t
.charAt(i
)))
498 (p
.charAt(q
) == t
.charAt(i
)) && q
++;
500 (q
== p
.length
) && result
.push(i
- p
.length
) && (q
= pi
[q
]);
506 /* step for algorithm visualisation */
507 function step(comment
, funct
) {
509 //display comment (before or after waiting)
511 /* execute callback function */
516 * Curry - Function currying
517 * Copyright (c) 2008 Ariel Flesler - aflesler(at)gmail(dot)com | http://flesler.blogspot.com
518 * Licensed under BSD (http://www.opensource.org/licenses/bsd-license.php)
521 * @author Ariel Flesler
524 function curry( fn
){
526 var args
= curry
.args(arguments
),
527 master
= arguments
.callee
,
530 return args
.length
>= fn
.length
? fn
.apply(self
,args
) : function(){
531 return master
.apply( self
, args
.concat(curry
.args(arguments
)) );
536 curry
.args = function( args
){
537 return Array
.prototype.slice
.call(args
);
540 Function
.prototype.curry = function(){
547 * Sort a directed graph based on incoming edges
549 * Coded by Jake Stothard
551 function topological_sort(g
) {
552 //Mark nodes as "deleted" instead of actually deleting them
553 //That way we don't have to copy g
556 g
.nodes
[i
].deleted
= false;
558 var ret
= topological_sort_helper(g
);
560 //Cleanup: Remove the deleted property
562 delete g
.nodes
[i
].deleted
566 function topological_sort_helper(g
) {
567 //Find node with no incoming edges
570 if(g
.nodes
[i
].deleted
)
571 continue; //Bad style, meh
573 var incoming
= false;
574 for(j
in g
.nodes
[i
].edges
) {
575 if(g
.nodes
[i
].edges
[j
].target
== g
.nodes
[i
]
576 && g
.nodes
[i
].edges
[j
].source
.deleted
== false) {
587 // Either unsortable or done. Either way, GTFO
588 if(node
== undefined)
591 //"Delete" node from g
594 var tail
= topological_sort_helper(g
);