1 | const Queue = require('./PriorityQueue');
|
2 | const removeDeepFromMap = require('./removeDeepFromMap');
|
3 | const toDeepMap = require('./toDeepMap');
|
4 |
|
5 | /** Creates and manages a graph */
|
6 | class Graph {
|
7 |
|
8 | /**
|
9 | * Creates a new Graph, optionally initializing it a nodes graph representation.
|
10 | *
|
11 | * A graph representation is an object that has as keys the name of the point and as values
|
12 | * the points reacheable from that node, with the cost to get there:
|
13 | *
|
14 | * {
|
15 | * node (Number|String): {
|
16 | * neighbor (Number|String): cost (Number),
|
17 | * ...,
|
18 | * },
|
19 | * }
|
20 | *
|
21 | * @param {Object} [graph] - Initial graph definition
|
22 | * @example
|
23 | *
|
24 | * const route = new Graph();
|
25 | *
|
26 | * // Pre-populated graph
|
27 | * const route = new Graph({
|
28 | * A: { B: 1 },
|
29 | * B: { A: 1, C: 2, D: 4 },
|
30 | * });
|
31 | */
|
32 | constructor(graph) {
|
33 | this.graph = graph ? toDeepMap(graph) : new Map();
|
34 | }
|
35 |
|
36 | /**
|
37 | * Adds a node to the graph
|
38 | *
|
39 | * @param {string} name - Name of the node
|
40 | * @param {Object} neighbors - Neighbouring nodes and cost to reach them
|
41 | * @return {this}
|
42 | * @example
|
43 | *
|
44 | * const route = new Graph();
|
45 | *
|
46 | * route.addNode('A', { B: 1 });
|
47 | *
|
48 | * // It's possible to chain the calls
|
49 | * route
|
50 | * .addNode('B', { A: 1 })
|
51 | * .addNode('C', { A: 3 });
|
52 | */
|
53 | addNode(name, neighbors) {
|
54 | this.graph.set(name, toDeepMap(neighbors));
|
55 |
|
56 | return this;
|
57 | }
|
58 |
|
59 | /**
|
60 | * @deprecated since version 2.0, use `Graph#addNode` isntead
|
61 | */
|
62 | addVertex(name, neighbors) {
|
63 | return this.addNode(name, neighbors);
|
64 | }
|
65 |
|
66 | /**
|
67 | * Removes a node and all it's referencies from the graph
|
68 | *
|
69 | * @param {string|number} key - Key of the node to remove from the graph
|
70 | * @return {this}
|
71 | * @example
|
72 | *
|
73 | * const route = new Graph({
|
74 | * A: { B: 1, C: 5 },
|
75 | * B: { A: 3 },
|
76 | * C: { B: 2, A: 2 },
|
77 | * });
|
78 | *
|
79 | * route.removeNode('C');
|
80 | * // The graph now is:
|
81 | * // { A: { B: 1 }, B: { A: 3 } }
|
82 | */
|
83 | removeNode(key) {
|
84 | this.graph = removeDeepFromMap(this.graph, key);
|
85 |
|
86 | return this;
|
87 | }
|
88 |
|
89 | /**
|
90 | * Compute the shortest path between the specified nodes
|
91 | *
|
92 | * @param {string} start - Starting node
|
93 | * @param {string} goal - Node we want to reach
|
94 | * @param {object} [options] - Options
|
95 | *
|
96 | * @param {boolean} [options.trim] - Exclude the origin and destination nodes from the result
|
97 | * @param {boolean} [options.reverse] - Return the path in reversed order
|
98 | * @param {boolean} [options.cost] - Also return the cost of the path when set to true
|
99 | *
|
100 | * @return {array|object} Computed path between the nodes.
|
101 | *
|
102 | * When `option.cost` is set to true, the returned value will be an object with shape:
|
103 | * - `path` *(Array)*: Computed path between the nodes
|
104 | * - `cost` *(Number)*: Cost of the path
|
105 | *
|
106 | * @example
|
107 | *
|
108 | * const route = new Graph()
|
109 | *
|
110 | * route.addNode('A', { B: 1 })
|
111 | * route.addNode('B', { A: 1, C: 2, D: 4 })
|
112 | * route.addNode('C', { B: 2, D: 1 })
|
113 | * route.addNode('D', { C: 1, B: 4 })
|
114 | *
|
115 | * route.path('A', 'D') // => ['A', 'B', 'C', 'D']
|
116 | *
|
117 | * // trimmed
|
118 | * route.path('A', 'D', { trim: true }) // => [B', 'C']
|
119 | *
|
120 | * // reversed
|
121 | * route.path('A', 'D', { reverse: true }) // => ['D', 'C', 'B', 'A']
|
122 | *
|
123 | * // include the cost
|
124 | * route.path('A', 'D', { cost: true })
|
125 | * // => {
|
126 | * // path: [ 'A', 'B', 'C', 'D' ],
|
127 | * // cost: 4
|
128 | * // }
|
129 | */
|
130 | path(start, goal, options = {}) {
|
131 | // Don't run when we don't have nodes set
|
132 | if (!this.graph.size) {
|
133 | if (options.cost) return { path: null, cost: 0 };
|
134 |
|
135 | return null;
|
136 | }
|
137 |
|
138 | const explored = new Set();
|
139 | const frontier = new Queue();
|
140 | const previous = new Map();
|
141 |
|
142 | let path = [];
|
143 | let totalCost = 0;
|
144 |
|
145 | // Add the starting point to the frontier, it will be the first node visited
|
146 | frontier.set(start, 0);
|
147 |
|
148 | // Run until we have visited every node in the frontier
|
149 | while (!frontier.isEmpty()) {
|
150 | // Get the node in the frontier with the lowest cost (`priority`)
|
151 | const node = frontier.next();
|
152 |
|
153 | // When the node with the lowest cost in the frontier in our goal node,
|
154 | // we can compute the path and exit the loop
|
155 | if (node.key === goal) {
|
156 | // Set the total cost to the current value
|
157 | totalCost = node.priority;
|
158 |
|
159 | let nodeKey = node.key;
|
160 | while (previous.has(nodeKey)) {
|
161 | path.push(nodeKey);
|
162 | nodeKey = previous.get(nodeKey);
|
163 | }
|
164 |
|
165 | break;
|
166 | }
|
167 |
|
168 | // Add the current node to the explored set
|
169 | explored.add(node.key);
|
170 |
|
171 | // Loop all the neighboring nodes
|
172 | const neighbors = this.graph.get(node.key) || new Map();
|
173 | neighbors.forEach((nCost, nNode) => {
|
174 | // If we already explored the node, skip it
|
175 | if (explored.has(nNode)) return null;
|
176 |
|
177 | // If the neighboring node is not yet in the frontier, we add it with
|
178 | // the correct cost
|
179 | if (!frontier.has(nNode)) {
|
180 | previous.set(nNode, node.key);
|
181 | return frontier.set(nNode, node.priority + nCost);
|
182 | }
|
183 |
|
184 | const frontierPriority = frontier.get(nNode).priority;
|
185 | const nodeCost = node.priority + nCost;
|
186 |
|
187 | // Othewhise we only update the cost of this node in the frontier when
|
188 | // it's below what's currently set
|
189 | if (nodeCost < frontierPriority) {
|
190 | previous.set(nNode, node.key);
|
191 | return frontier.set(nNode, nodeCost);
|
192 | }
|
193 |
|
194 | return null;
|
195 | });
|
196 | }
|
197 |
|
198 | // Return null when no path can be found
|
199 | if (!path.length) {
|
200 | if (options.cost) return { path: null, cost: 0 };
|
201 |
|
202 | return null;
|
203 | }
|
204 |
|
205 | // From now on, keep in mind that `path` is populated in reverse order,
|
206 | // from destination to origin
|
207 |
|
208 | // Remove the first value (the goal node) if we want a trimmed result
|
209 | if (options.trim) {
|
210 | path.shift();
|
211 | } else {
|
212 | // Add the origin waypoint at the end of the array
|
213 | path = path.concat([start]);
|
214 | }
|
215 |
|
216 | // Reverse the path if we don't want it reversed, so the result will be
|
217 | // from `start` to `goal`
|
218 | if (!options.reverse) {
|
219 | path = path.reverse();
|
220 | }
|
221 |
|
222 | // Return an object if we also want the cost
|
223 | if (options.cost) {
|
224 | return {
|
225 | path,
|
226 | cost: totalCost,
|
227 | };
|
228 | }
|
229 |
|
230 | return path;
|
231 | }
|
232 |
|
233 | /**
|
234 | * @deprecated since version 2.0, use `Graph#path` isntead
|
235 | */
|
236 | shortestPath(...args) {
|
237 | return this.path(...args);
|
238 | }
|
239 |
|
240 | }
|
241 |
|
242 | module.exports = Graph;
|