device_home/node_modules/dijkstrajs/dijkstra.js

   1 'use strict';
   2
   3 /******************************************************************************
   4  * Created 2008-08-19.
   5  *
   6  * Dijkstra path-finding functions. Adapted from the Dijkstar Python project.
   7  *
   8  * Copyright (C) 2008
   9  *   Wyatt Baldwin <self@wyattbaldwin.com>
  10  *   All rights reserved
  11  *
  12  * Licensed under the MIT license.
  13  *
  14  *   http://www.opensource.org/licenses/mit-license.php
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23  *****************************************************************************/
  24 var dijkstra = {
  25   single_source_shortest_paths: function(graph, s, d) {
  26     // Predecessor map for each node that has been encountered.
  27     // node ID => predecessor node ID
  28     var predecessors = {};
  29
  30     // Costs of shortest paths from s to all nodes encountered.
  31     // node ID => cost
  32     var costs = {};
  33     costs[s] = 0;
  34
  35     // Costs of shortest paths from s to all nodes encountered; differs from
  36     // `costs` in that it provides easy access to the node that currently has
  37     // the known shortest path from s.
  38     // XXX: Do we actually need both `costs` and `open`?
  39     var open = dijkstra.PriorityQueue.make();
  40     open.push(s, 0);
  41
  42     var closest,
  43         u, v,
  44         cost_of_s_to_u,
  45         adjacent_nodes,
  46         cost_of_e,
  47         cost_of_s_to_u_plus_cost_of_e,
  48         cost_of_s_to_v,
  49         first_visit;
  50     while (!open.empty()) {
  51       // In the nodes remaining in graph that have a known cost from s,
  52       // find the node, u, that currently has the shortest path from s.
  53       closest = open.pop();
  54       u = closest.value;
  55       cost_of_s_to_u = closest.cost;
  56
  57       // Get nodes adjacent to u...
  58       adjacent_nodes = graph[u] || {};
  59
  60       // ...and explore the edges that connect u to those nodes, updating
  61       // the cost of the shortest paths to any or all of those nodes as
  62       // necessary. v is the node across the current edge from u.
  63       for (v in adjacent_nodes) {
  64         if (adjacent_nodes.hasOwnProperty(v)) {
  65           // Get the cost of the edge running from u to v.
  66           cost_of_e = adjacent_nodes[v];
  67
  68           // Cost of s to u plus the cost of u to v across e--this is *a*
  69           // cost from s to v that may or may not be less than the current
  70           // known cost to v.
  71           cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;
  72
  73           // If we haven't visited v yet OR if the current known cost from s to
  74           // v is greater than the new cost we just found (cost of s to u plus
  75           // cost of u to v across e), update v's cost in the cost list and
  76           // update v's predecessor in the predecessor list (it's now u).
  77           cost_of_s_to_v = costs[v];
  78           first_visit = (typeof costs[v] === 'undefined');
  79           if (first_visit || cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {
  80             costs[v] = cost_of_s_to_u_plus_cost_of_e;
  81             open.push(v, cost_of_s_to_u_plus_cost_of_e);
  82             predecessors[v] = u;
  83           }
  84         }
  85       }
  86     }
  87
  88     if (typeof d !== 'undefined' && typeof costs[d] === 'undefined') {
  89       var msg = ['Could not find a path from ', s, ' to ', d, '.'].join('');
  90       throw new Error(msg);
  91     }
  92
  93     return predecessors;
  94   },
  95
  96   extract_shortest_path_from_predecessor_list: function(predecessors, d) {
  97     var nodes = [];
  98     var u = d;
  99     var predecessor;
 100     while (u) {
 101       nodes.push(u);
 102       predecessor = predecessors[u];
 103       u = predecessors[u];
 104     }
 105     nodes.reverse();
 106     return nodes;
 107   },
 108
 109   find_path: function(graph, s, d) {
 110     var predecessors = dijkstra.single_source_shortest_paths(graph, s, d);
 111     return dijkstra.extract_shortest_path_from_predecessor_list(
 112       predecessors, d);
 113   },
 114
 115   /**
 116    * A very naive priority queue implementation.
 117    */
 118   PriorityQueue: {
 119     make: function (opts) {
 120       var T = dijkstra.PriorityQueue,
 121           t = {},
 122           key;
 123       opts = opts || {};
 124       for (key in T) {
 125         if (T.hasOwnProperty(key)) {
 126           t[key] = T[key];
 127         }
 128       }
 129       t.queue = [];
 130       t.sorter = opts.sorter || T.default_sorter;
 131       return t;
 132     },
 133
 134     default_sorter: function (a, b) {
 135       return a.cost - b.cost;
 136     },
 137
 138     /**
 139      * Add a new item to the queue and ensure the highest priority element
 140      * is at the front of the queue.
 141      */
 142     push: function (value, cost) {
 143       var item = {value: value, cost: cost};
 144       this.queue.push(item);
 145       this.queue.sort(this.sorter);
 146     },
 147
 148     /**
 149      * Return the highest priority element in the queue.
 150      */
 151     pop: function () {
 152       return this.queue.shift();
 153     },
 154
 155     empty: function () {
 156       return this.queue.length === 0;
 157     }
 158   }
 159 };
 160
 161
 162 // node.js module exports
 163 if (typeof module !== 'undefined') {
 164   module.exports = dijkstra;
 165 }