https://althurayya.github.io/graph.js

1
2function init_graph(routes) {
3  var Graph = require('data-structures').Graph;
4  graph = new Graph();
5  var e, s, edge;
6
7  for (var i = 0; i < routes.length; i++) {
8    e = routes[i].properties.eToponym;
9    s = routes[i].properties.sToponym;
10    graph.addNode(e);
11    graph.getNode(e)._id = e;
12
13    graph.addNode(s);
14    graph.getNode(s)._id = s;
15
16    graph.addEdge(e, s);
17    edge = graph.getEdge(e, s);
18    edge._eid = e;
19    edge._sid = s;
20
21    edge._id = routes[i].properties.id;
22    edge.weight = routes[i].properties.Meter;
23  }
24  resetNodes(graph);
25
26}
27
28/* consider doing the routepoint thing in the definition of the graph. 
29 so if you run across a routepoint, all edges connecting to it equal 
30 weight of routepoint + current edge. maybe that will work? */ 
31
32
33function resetNodes(G) {
34  graph.forEachNode( function(node) {
35    node.visited = false; 
36  })
37}
38
39/* DIJSKSTRA IMPLEMENTATION ADAPTED FROM: https://github.com/mburst/dijkstras-algorithm */
40
41function PriorityQueue () {
42  this._nodes = [];
43
44  this.enqueue = function (priority, key) {
45    this._nodes.push({key: key, priority: priority });
46    this.sort();
47  }
48  this.dequeue = function () {
49    return this._nodes.shift().key;
50  }
51  this.sort = function () {
52    this._nodes.sort(function (a, b) {
53      return a.priority - b.priority;
54    });
55  }
56  this.isEmpty = function () {
57    return !this._nodes.length;
58  }
59}
60
61function findPaths(s, t, withinADay) {
62  var shortest = shortestPath(s, t, withinADay);
63  /* second: get rid of longest edge weight */ 
64  var max = longestEdge(shortest); 
65  max.weight = INFINITY; 
66  //var secondShortest = shortestPath(s, t); 
67  /* get rid of all edge weights over x weight*/
68  return shortest; 
69}
70
71function secondShortest(s, t, path) {
72  var max = longestEdge(path); 
73  max.weight = 1/0; 
74  var second = shortestPath(s, t, false); // not within a day.
75  return second;
76}
77
78function longestEdge(path) {
79  var max = 0; 
80  var edge; 
81  for(var i = 0; i < path.length - 1; i++) {
82    edge = graph.getEdge(path[i], path[i+1]); 
83    if (edge && edge.weight > max) {
84      max = edge; 
85    }
86  }
87  return max; 
88}
89
90
91/* THOUGHT for through center. What if instead of through 'centers' I say through 'X?' 
92 * As in, I want to go TO fustat and pass through makka. What's the fastest way to do so? 
93 * That's pretty easy to implement. Would it be worthwhile? 
94 * And if I want to do "major centers", I could have to have a list of the major centers, 
95 * then ask if it's a preference or a guarantee. Find the closest major center to the existing
96 * shortest path, then do pass through "X" on that center. 
97 */ 
98
99//var distances = {}; // eek global 
100
101function shortestPath(s, t, searchType) {
102  var INFINITY = 1/0;
103  var nodes = new PriorityQueue(),
104          distances = {},
105          previous = {},
106          path = [],
107          smallest, neighbor, alt;
108  // init start to 0, all else to infinity  
109  graph.forEachNode( function (node) {
110    if (node._id == s._id) {
111      distances[node._id] = 0
112      nodes.enqueue(0, node._id);
113    } else {
114      distances[node._id] = INFINITY; 
115     // nodes.enqueue(INFINITY, node._id);
116    } 
117    previous[node._id] = null; 
118  });
119
120  while(!nodes.isEmpty()) {
121    smallest = nodes.dequeue();
122    /* create return path */ 
123    if (searchType != 'n') {
124      if(smallest == t._id) {
125        path;
126        while(previous[smallest]) {
127          path.push(smallest);     
128          smallest = previous[smallest];
129        }
130        break;
131      }
132    }
133
134    var edges = graph.getAllEdgesOf(smallest);
135    for(var i = 0; i < edges.length; i++) {
136      neighbor = edges[i];
137      if (searchType == 'd' && neighbor.weight > WITHIN_A_DAY) {
138        continue;  // within a day is tagged and the neighbor's weight is greater than a Day. 
139      } else {
140          alt = distances[smallest] + neighbor.weight; 
141          if (neighbor._sid == smallest) {
142            if (alt < distances[neighbor._eid]) {
143              distances[neighbor._eid] = alt;
144              previous[neighbor._eid] = smallest;
145              nodes.enqueue(alt, neighbor._eid);
146            }
147          } else {
148            if (alt < distances[neighbor._sid]) {
149              distances[neighbor._sid] = alt;
150              previous[neighbor._sid] = smallest;
151              nodes.enqueue(alt, neighbor._sid)
152            }
153          } 
154      }
155    }
156  }
157  return searchType == 'n' ? distances : path.concat(s._id).reverse(); 
158} 
159
160
161function getNetwork(distances, multiplier) {
162  var network = d3.map(); //d3.map()? 
163  var zones = d3.map(); 
164
165  //init 
166  for (var i = 1; i < NUM_ZONES; i++) {
167    zones.set(DAY * multiplier * i, 'Zone ' + i);
168  }
169  zones.set(Infinity, 'Zone ' + NUM_ZONES); 
170
171  //init

172  zones.values().forEach(function(z) {
173    network.set(z, new Array());
174  }); 
175
176  jQuery.each(distances, function(id, meters) {
177    zone = placeDistanceInZone(meters, zones); 
178    network.get(zone).push(id); 
179  })
180
181  return network; 
182}
183
184// set adds in numerical order. then we get the index 
185// of the added meter to determine which zone it belongs to. (i - 1)
186function placeDistanceInZone(meters, zones) {
187  var values = zones.keys().map(function(z) { return parseInt(z)}); // turn into ints
188  values.pop() // Infinity doesn't parse to int. 
189  if (meters == Infinity) {
190    return 'Zone ' + NUM_ZONES;
191  } else {
192    values.push(meters);
193    values.sort(function(a, b) {
194      return a - b; 
195    });
196
197    var index = values.indexOf(meters); 
198    index = (index == values.length - 1) ? index - 1 : (index + 1);   
199    return zones.get(values[index]);
200  }
201}
202
203function lengthInMeters(path) {
204  var m = 0;
205  path.forEach(function(p) {
206    m += p.properties.Meter;
207  })
208  return m;
209}