forked from rcdexta/shopomap_canvas
-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.js
87 lines (74 loc) · 1.86 KB
/
graph.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
var Graph = function(){
this.nodes = [];
this.path = []
}
Graph.prototype = {
addNode: function(node){
this.nodes.push(node);
},
printNodes: function(){
console.log("[");
for(var i=0;i<this.nodes.length;i++){
console.log(this.nodes[i].toString());
}
console.log("]");
},
traverse: function(node, visited){
visited = visited || [];
visited.push(node);
for(var i=0;i<node.edges.length;i++){
var nextNode = node.edges[i];
if (visited.indexOf(nextNode) == -1){
console.log(node.toString() + " : " + nextNode.toString());
this.traverse(nextNode, visited);
}
}
},
nodeShortestPath: function(node, target, parents, visited){
visited = visited || [];
parents = parents || [];
visited.push(node);
if (node == target){
parents.push(node);
$.extend(this.path, parents);
return -1;
}
for(var i=0;i<node.edges.length;i++){
var nextNode = node.edges[i];
if (visited.indexOf(nextNode) == -1){
parents.push(node);
result = this.nodeShortestPath(nextNode, target, parents, visited);
if (result == -1) return;
parents.pop();
}
}
},
poIShortestPath: function(source, target){
var sourceNode = this.nearestNodeTo(source);
var targetNode = this.nearestNodeTo(target);
this.nodeShortestPath(sourceNode, targetNode);
this.path.shift();
this.path.unshift(source);
this.path.pop();
this.path.push(target);
},
printArray: function(arr){
var str = "";
for(var i=0;i<arr.length;i++){
str = str + arr[i].toString() + ",";
}
console.log("[" + str + "]");
},
nearestNodeTo: function(poi){
var minDistance = Number.POSITIVE_INFINITY;
var nearestNode;
for(var i=0;i<this.nodes.length;i++){
var distance = this.nodes[i].distanceFrom(poi);
if (distance < minDistance){
nearestNode = this.nodes[i];
minDistance = distance;
}
}
return nearestNode;
}
}