signaling_server/service/node_modules/dijkstrajs/test/dijkstra.test.js

   1 'use strict';
   2
   3 var expect = require('expect.js');
   4 var dijkstra = require('../dijkstra.js');
   5 var find_path = dijkstra.find_path;
   6
   7 describe('dijkstra.js', function () {
   8
   9     describe('.find_path()', function () {
  10
  11         it('should find the path between two points, all edges have weight 1', function () {
  12             // A B C
  13             // D E F
  14             // G H I
  15             var graph = {
  16                 a: {b: 10, d: 1},
  17                 b: {a: 1, c: 1, e: 1},
  18                 c: {b: 1, f: 1},
  19                 d: {a: 1, e: 1, g: 1},
  20                 e: {b: 1, d: 1, f: 1, h: 1},
  21                 f: {c: 1, e: 1, i: 1},
  22                 g: {d: 1, h: 1},
  23                 h: {e: 1, g: 1, i: 1},
  24                 i: {f: 1, h: 1}
  25             };
  26             var path = find_path(graph, 'a', 'i');
  27             expect(path).to.eql(['a', 'd', 'e', 'f', 'i']);
  28         });
  29
  30         it('should find the path between two points, weighted edges', function () {
  31             var graph = {
  32                 a: {b: 10, c: 100, d: 1},
  33                 b: {c: 10},
  34                 d: {b: 1, e: 1},
  35                 e: {f: 1},
  36                 f: {c: 1},
  37                 g: {b: 1}
  38             };
  39
  40             var path = find_path(graph, 'a', 'c');
  41             expect(path).to.eql(['a', 'd', 'e', 'f', 'c']);
  42             path = find_path(graph, 'd', 'b');
  43             expect(path).to.eql(['d', 'b']);
  44         });
  45
  46         it('should throw on unreachable destination', function () {
  47             var graph = {
  48                 a: {b: 10, c: 100, d: 1},
  49                 b: {c: 10},
  50                 d: {b: 1, e: 1},
  51                 e: {f: 1},
  52                 f: {c: 1},
  53                 g: {b: 1}
  54             };
  55
  56             expect(function () { find_path(graph, 'c', 'a'); }).to.throwException();
  57             expect(function () { find_path(graph, 'a', 'g'); }).to.throwException();
  58         });
  59
  60         it('should throw on non-existent destination', function () {
  61             var graph = {
  62                 a: {b: 10, c: 100, d: 1},
  63                 b: {c: 10},
  64                 d: {b: 1, e: 1},
  65                 e: {f: 1},
  66                 f: {c: 1},
  67                 g: {b: 1}
  68             };
  69
  70             expect(function () { find_path(graph, 'a', 'z'); }).to.throwException();
  71         });
  72     });
  73
  74     describe('.single_source_shortest_paths()', function () {
  75         it('should find all paths from a node', function () {
  76             var graph = {
  77                 a: {b: 10, c: 100, d: 1},
  78                 b: {c: 10},
  79                 d: {b: 1, e: 1},
  80                 e: {f: 1},
  81                 f: {c: 1},
  82                 g: {b: 1}
  83             };
  84
  85             // All paths from 'a'
  86             var paths = dijkstra.single_source_shortest_paths(graph, 'a');
  87             expect(paths).to.eql({
  88                 d: 'a',
  89                 b: 'd',
  90                 e: 'd',
  91                 f: 'e',
  92                 c: 'f'
  93             });
  94         });
  95     });
  96 });