| /* |
| * Various algorithms and data structures, licensed under the MIT-license. |
| * (c) 2010 by Johann Philipp Strathausen <strathausen@gmail.com> |
| * http://strathausen.eu |
| * |
| */ |
| |
| |
| |
| /* |
| Bellman-Ford |
| |
| Path-finding algorithm, finds the shortest paths from one node to all nodes. |
| |
| |
| Complexity |
| |
| O( |E| · |V| ), where E = edges and V = vertices (nodes) |
| |
| |
| Constraints |
| |
| Can run on graphs with negative edge weights as long as they do not have |
| any negative weight cycles. |
| |
| */ |
| function bellman_ford(g, source) { |
| |
| /* STEP 1: initialisation */ |
| for(var n in g.nodes) |
| g.nodes[n].distance = Infinity; |
| /* predecessors are implicitly null */ |
| source.distance = 0; |
| |
| step("Initially, all distances are infinite and all predecessors are null."); |
| |
| /* STEP 2: relax each edge (this is at the heart of Bellman-Ford) */ |
| /* repeat this for the number of nodes minus one */ |
| for(var i = 1; i < g.nodes.length; i++) |
| /* for each edge */ |
| for(var e in g.edges) { |
| var edge = g.edges[e]; |
| if(edge.source.distance + edge.weight < edge.target.distance) { |
| step("Relax edge between " + edge.source.id + " and " + edge.target.id + "."); |
| edge.target.distance = edge.source.distance + edge.weight; |
| edge.target.predecessor = edge.source; |
| } |
| //Added by Jake Stothard (Needs to be tested) |
| if(!edge.style.directed) { |
| if(edge.target.distance + edge.weight < edge.source.distance) { |
| g.snapShot("Relax edge between "+edge.target.id+" and "+edge.source.id+"."); |
| edge.source.distance = edge.target.distance + edge.weight; |
| edge.source.predecessor = edge.target; |
| } |
| } |
| } |
| step("Ready."); |
| |
| /* STEP 3: TODO Check for negative cycles */ |
| /* For now we assume here that the graph does not contain any negative |
| weights cycles. (this is left as an excercise to the reader[tm]) */ |
| } |
| |
| |
| |
| /* |
| Path-finding algorithm Dijkstra |
| |
| - worst-case running time is O((|E| + |V|) · log |V| ) thus better than |
| Bellman-Ford for sparse graphs (with less edges), but cannot handle |
| negative edge weights |
| */ |
| function dijkstra(g, source) { |
| |
| /* initially, all distances are infinite and all predecessors are null */ |
| for(var n in g.nodes) |
| g.nodes[n].distance = Infinity; |
| /* predecessors are implicitly null */ |
| |
| g.snapShot("Initially, all distances are infinite and all predecessors are null."); |
| |
| source.distance = 0; |
| /* set of unoptimized nodes, sorted by their distance (but a Fibonacci heap |
| would be better) */ |
| var q = new BinaryMinHeap(g.nodes, "distance"); |
| |
| /* pointer to the node in focus */ |
| var node; |
| |
| /* get the node with the smallest distance |
| as long as we have unoptimized nodes. q.min() can have O(log n). */ |
| while(q.min() != undefined) { |
| /* remove the latest */ |
| node = q.extractMin(); |
| node.optimized = true; |
| |
| /* no nodes accessible from this one, should not happen */ |
| if(node.distance == Infinity) |
| throw "Orphaned node!"; |
| |
| /* for each neighbour of node */ |
| for(e in node.edges) { |
| var other = (node == node.edges[e].target) ? node.edges[e].source : node.edges[e].target; |
| |
| if(other.optimized) |
| continue; |
| |
| /* look for an alternative route */ |
| var alt = node.distance + node.edges[e].weight; |
| |
| /* update distance and route if a better one has been found */ |
| if (alt < other.distance) { |
| |
| /* update distance of neighbour */ |
| other.distance = alt; |
| |
| /* update priority queue */ |
| q.heapify(); |
| |
| /* update path */ |
| other.predecessor = node; |
| g.snapShot("Enhancing node.") |
| } |
| } |
| } |
| } |
| |
| |
| /* All-Pairs-Shortest-Paths */ |
| /* Runs at worst in O(|V|³) and at best in Omega(|V|³) :-) |
| complexity Sigma(|V|²) */ |
| /* This implementation is not yet ready for general use, but works with the |
| Dracula graph library. */ |
| function floyd_warshall(g, source) { |
| |
| /* Step 1: initialising empty path matrix (second dimension is implicit) */ |
| var path = []; |
| var next = []; |
| var n = g.nodes.length; |
| |
| /* construct path matrix, initialize with Infinity */ |
| for(j in g.nodes) { |
| path[j] = []; |
| next[j] = []; |
| for(i in g.nodes) |
| path[j][i] = j == i ? 0 : Infinity; |
| } |
| |
| /* initialize path with edge weights */ |
| for(e in g.edges) |
| path[g.edges[e].source.id][g.edges[e].target.id] = g.edges[e].weight; |
| |
| /* Note: Usually, the initialisation is done by getting the edge weights |
| from a node matrix representation of the graph, not by iterating through |
| a list of edges as done here. */ |
| |
| /* Step 2: find best distances (the heart of Floyd-Warshall) */ |
| for(k in g.nodes){ |
| for(i in g.nodes) { |
| for(j in g.nodes) |
| if(path[i][j] > path[i][k] + path[k][j]) { |
| path[i][j] = path[i][k] + path[k][j]; |
| /* Step 2.b: remember the path */ |
| next[i][j] = k; |
| } |
| } |
| } |
| |
| /* Step 3: Path reconstruction, get shortest path */ |
| function getPath(i, j) { |
| if(path[i][j] == Infinity) |
| throw "There is no path."; |
| var intermediate = next[i][j]; |
| if(intermediate == undefined) |
| return null; |
| else |
| return getPath(i, intermediate) |
| .concat([intermediate]) |
| .concat(getPath(intermediate, j)); |
| } |
| |
| /* TODO use the knowledge, e.g. mark path in graph */ |
| } |
| |
| /* |
| Ford-Fulkerson |
| |
| Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed |
| graph from source to sink. |
| |
| |
| Complexity |
| |
| O(E * max(f)), max(f) being the maximum flow |
| |
| |
| Description |
| |
| As long as there is an open path through the residual graph, send the |
| minimum of the residual capacities on the path. |
| |
| |
| Constraints |
| |
| The algorithm works only if all weights are integers. Otherwise it is |
| possible that the Ford–Fulkerson algorithm will not converge to the maximum |
| value. |
| |
| |
| Input |
| |
| g - Graph object |
| s - Source ID |
| t - Target (sink) ID |
| |
| |
| Output |
| |
| Maximum flow from Source s to Target t |
| |
| */ |
| /* |
| Edmonds-Karp |
| |
| Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed |
| graph from source to sink. An implementation of the Ford-Fulkerson |
| algorithm. |
| |
| |
| Complexity |
| |
| O(|V|*|E|²) |
| |
| |
| Input |
| |
| g - Graph object (with node and edge lists, capacity is a property of edge) |
| s - source ID |
| t - sink ID |
| |
| */ |
| function edmonds_karp(g, s, t) { |
| |
| } |
| |
| /* |
| A simple binary min-heap serving as a priority queue |
| - takes an array as the input, with elements having a key property |
| - elements will look like this: |
| { |
| key: "... key property ...", |
| value: "... element content ..." |
| } |
| - provides insert(), min(), extractMin() and heapify() |
| - example usage (e.g. via the Firebug or Chromium console): |
| var x = {foo: 20, hui: "bla"}; |
| var a = new BinaryMinHeap([x,{foo:3},{foo:10},{foo:20},{foo:30},{foo:6},{foo:1},{foo:3}],"foo"); |
| console.log(a.extractMin()); |
| console.log(a.extractMin()); |
| x.foo = 0; // update key |
| a.heapify(); // call this always after having a key updated |
| console.log(a.extractMin()); |
| console.log(a.extractMin()); |
| - can also be used on a simple array, like [9,7,8,5] |
| */ |
| function BinaryMinHeap(array, key) { |
| |
| /* Binary tree stored in an array, no need for a complicated data structure */ |
| var tree = []; |
| |
| var key = key || 'key'; |
| |
| /* Calculate the index of the parent or a child */ |
| var parent = function(index) { return Math.floor((index - 1)/2); }; |
| var right = function(index) { return 2 * index + 2; }; |
| var left = function(index) { return 2 * index + 1; }; |
| |
| /* Helper function to swap elements with their parent |
| as long as the parent is bigger */ |
| function bubble_up(i) { |
| var p = parent(i); |
| while((p >= 0) && (tree[i][key] < tree[p][key])) { |
| /* swap with parent */ |
| tree[i] = tree.splice(p, 1, tree[i])[0]; |
| /* go up one level */ |
| i = p; |
| p = parent(i); |
| } |
| } |
| |
| /* Helper function to swap elements with the smaller of their children |
| as long as there is one */ |
| function bubble_down(i) { |
| var l = left(i); |
| var r = right(i); |
| |
| /* as long as there are smaller children */ |
| while(tree[l] && (tree[i][key] > tree[l][key]) || tree[r] && (tree[i][key] > tree[r][key])) { |
| |
| /* find smaller child */ |
| var child = tree[l] ? tree[r] ? tree[l][key] > tree[r][key] ? r : l : l : l; |
| |
| /* swap with smaller child with current element */ |
| tree[i] = tree.splice(child, 1, tree[i])[0]; |
| |
| /* go up one level */ |
| i = child; |
| l = left(i); |
| r = right(i); |
| } |
| } |
| |
| /* Insert a new element with respect to the heap property |
| 1. Insert the element at the end |
| 2. Bubble it up until it is smaller than its parent */ |
| this.insert = function(element) { |
| |
| /* make sure there's a key property */ |
| (element[key] == undefined) && (element = {key:element}); |
| |
| /* insert element at the end */ |
| tree.push(element); |
| |
| /* bubble up the element */ |
| bubble_up(tree.length - 1); |
| } |
| |
| /* Only show us the minimum */ |
| this.min = function() { |
| return tree.length == 1 ? undefined : tree[0]; |
| } |
| |
| /* Return and remove the minimum |
| 1. Take the root as the minimum that we are looking for |
| 2. Move the last element to the root (thereby deleting the root) |
| 3. Compare the new root with both of its children, swap it with the |
| smaller child and then check again from there (bubble down) |
| */ |
| this.extractMin = function() { |
| var result = this.min(); |
| |
| /* move the last element to the root or empty the tree completely */ |
| /* bubble down the new root if necessary */ |
| (tree.length == 1) && (tree = []) || (tree[0] = tree.pop()) && bubble_down(0); |
| |
| return result; |
| } |
| |
| /* currently unused, TODO implement */ |
| this.changeKey = function(index, key) { |
| throw "function not implemented"; |
| } |
| |
| this.heapify = function() { |
| for(var start = Math.floor((tree.length - 2) / 2); start >= 0; start--) { |
| bubble_down(start); |
| } |
| } |
| |
| /* insert the input elements one by one only when we don't have a key property (TODO can be done more elegant) */ |
| for(i in (array || [])) |
| this.insert(array[i]); |
| } |
| |
| |
| |
| /* |
| Quick Sort: |
| 1. Select some random value from the array, the median. |
| 2. Divide the array in three smaller arrays according to the elements |
| being less, equal or greater than the median. |
| 3. Recursively sort the array containg the elements less than the |
| median and the one containing elements greater than the median. |
| 4. Concatenate the three arrays (less, equal and greater). |
| 5. One or no element is always sorted. |
| TODO: This could be implemented more efficiently by using only one array object and several pointers. |
| */ |
| function quickSort(arr) { |
| /* recursion anchor: one element is always sorted */ |
| if(arr.length <= 1) return arr; |
| /* randomly selecting some value */ |
| var median = arr[Math.floor(Math.random() * arr.length)]; |
| var arr1 = [], arr2 = [], arr3 = []; |
| for(var i in arr) { |
| arr[i] < median && arr1.push(arr[i]); |
| arr[i] == median && arr2.push(arr[i]); |
| arr[i] > median && arr3.push(arr[i]); |
| } |
| /* recursive sorting and assembling final result */ |
| return quickSort(arr1).concat(arr2).concat(quickSort(arr3)); |
| } |
| |
| /* |
| Selection Sort: |
| 1. Select the minimum and remove it from the array |
| 2. Sort the rest recursively |
| 3. Return the minimum plus the sorted rest |
| 4. An array with only one element is already sorted |
| */ |
| function selectionSort(arr) { |
| /* recursion anchor: one element is always sorted */ |
| if(arr.length == 1) return arr; |
| var minimum = Infinity; |
| var index; |
| for(var i in arr) { |
| if(arr[i] < minimum) { |
| minimum = arr[i]; |
| index = i; /* remember the minimum index for later removal */ |
| } |
| } |
| /* remove the minimum */ |
| arr.splice(index, 1); |
| /* assemble result and sort recursively (could be easily done iteratively as well)*/ |
| return [minimum].concat(selectionSort(arr)); |
| } |
| |
| /* |
| Merge Sort: |
| 1. Cut the array in half |
| 2. Sort each of them recursively |
| 3. Merge the two sorted arrays |
| 4. An array with only one element is considered sorted |
| |
| */ |
| function mergeSort(arr) { |
| /* merges two sorted arrays into one sorted array */ |
| function merge(a, b) { |
| /* result set */ |
| var c = []; |
| /* as long as there are elements in the arrays to be merged */ |
| while(a.length > 0 || b.length > 0){ |
| /* are there elements to be merged, if yes, compare them and merge */ |
| 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; |
| /* always push the smaller one onto the result set */ |
| n != null && c.push(n); |
| } |
| return c; |
| } |
| /* this mergeSort implementation cuts the array in half, wich should be fine with randomized arrays, but introduces the risk of a worst-case scenario */ |
| median = Math.floor(arr.length / 2); |
| var part1 = arr.slice(0, median); /* for some reason it doesn't work if inserted directly in the return statement (tried so with firefox) */ |
| var part2 = arr.slice(median - arr.length); |
| return arr.length <= 1 ? arr : merge( |
| mergeSort(part1), /* first half */ |
| mergeSort(part2) /* second half */ |
| ); |
| } |
| |
| /* Balanced Red-Black-Tree */ |
| function RedBlackTree(arr) { |
| |
| } |
| |
| function BTree(arr) { |
| |
| } |
| |
| function NaryTree(n, arr) { |
| |
| } |
| |
| /** |
| * Knuth-Morris-Pratt string matching algorithm - finds a pattern in a text. |
| * FIXME: Doesn't work correctly yet. |
| */ |
| function kmp(p, t) { |
| |
| /** |
| * PREFIX, OVERLAP or FALIURE function for KMP. Computes how many iterations |
| * the algorithm can skip after a mismatch. |
| * |
| * @input p - pattern (string) |
| * @result array of skippable iterations |
| */ |
| function prefix(p) { |
| /* pi contains the computed skip marks */ |
| var pi = [0], k = 0; |
| for(q = 1; q < p.length; q++) { |
| while(k > 0 && (p.charAt(k) != p.charAt(q))) |
| k = pi[k-1]; |
| |
| (p.charAt(k) == p.charAt(q)) && k++; |
| |
| pi[q] = k; |
| } |
| return pi; |
| } |
| |
| /* The actual KMP algorithm starts here. */ |
| |
| var pi = prefix(p), q = 0, result = []; |
| |
| for(var i = 0; i < t.length; i++) { |
| /* jump forward as long as the character doesn't match */ |
| while((q > 0) && (p.charAt(q) != t.charAt(i))) |
| q = pi[q]; |
| |
| (p.charAt(q) == t.charAt(i)) && q++; |
| |
| (q == p.length) && result.push(i - p.length) && (q = pi[q]); |
| } |
| |
| return result; |
| } |
| |
| /* step for algorithm visualisation */ |
| function step(comment, funct) { |
| //wait for input |
| //display comment (before or after waiting) |
| // next.wait(); |
| /* execute callback function */ |
| funct(); |
| } |
| |
| /** |
| * Curry - Function currying |
| * Copyright (c) 2008 Ariel Flesler - aflesler(at)gmail(dot)com | http://flesler.blogspot.com |
| * Licensed under BSD (http://www.opensource.org/licenses/bsd-license.php) |
| * Date: 10/4/2008 |
| * |
| * @author Ariel Flesler |
| * @version 1.0.1 |
| */ |
| function curry( fn ){ |
| return function(){ |
| var args = curry.args(arguments), |
| master = arguments.callee, |
| self = this; |
| |
| return args.length >= fn.length ? fn.apply(self,args) : function(){ |
| return master.apply( self, args.concat(curry.args(arguments)) ); |
| }; |
| }; |
| }; |
| |
| curry.args = function( args ){ |
| return Array.prototype.slice.call(args); |
| }; |
| |
| Function.prototype.curry = function(){ |
| return curry(this); |
| }; |
| |
| /** |
| * Topological Sort |
| * |
| * Sort a directed graph based on incoming edges |
| * |
| * Coded by Jake Stothard |
| */ |
| function topological_sort(g) { |
| //Mark nodes as "deleted" instead of actually deleting them |
| //That way we don't have to copy g |
| |
| for(i in g.nodes) |
| g.nodes[i].deleted = false; |
| |
| var ret = topological_sort_helper(g); |
| |
| //Cleanup: Remove the deleted property |
| for(i in g.nodes) |
| delete g.nodes[i].deleted |
| |
| return ret; |
| } |
| function topological_sort_helper(g) { |
| //Find node with no incoming edges |
| var node; |
| for(i in g.nodes) { |
| if(g.nodes[i].deleted) |
| continue; //Bad style, meh |
| |
| var incoming = false; |
| for(j in g.nodes[i].edges) { |
| if(g.nodes[i].edges[j].target == g.nodes[i] |
| && g.nodes[i].edges[j].source.deleted == false) { |
| incoming = true; |
| break; |
| } |
| } |
| if(!incoming) { |
| node = g.nodes[i]; |
| break; |
| } |
| } |
| |
| // Either unsortable or done. Either way, GTFO |
| if(node == undefined) |
| return []; |
| |
| //"Delete" node from g |
| node.deleted = true; |
| |
| var tail = topological_sort_helper(g); |
| |
| tail.unshift(node); |
| |
| return tail; |
| } |