diff options
Diffstat (limited to 'addons/web_process/static/lib/dracula/dracula_algorithms.js')
| -rw-r--r-- | addons/web_process/static/lib/dracula/dracula_algorithms.js | 599 |
1 files changed, 0 insertions, 599 deletions
diff --git a/addons/web_process/static/lib/dracula/dracula_algorithms.js b/addons/web_process/static/lib/dracula/dracula_algorithms.js deleted file mode 100644 index 0fbb0857fc8..00000000000 --- a/addons/web_process/static/lib/dracula/dracula_algorithms.js +++ /dev/null @@ -1,599 +0,0 @@ -/* - * 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; -} |