dracula_algorithms.js

/*
 * 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;
}