1 |
|
2 |
|
3 | import assert from 'assert';
|
4 | import sinon from 'sinon';
|
5 |
|
6 | import Graph from '../src/Graph';
|
7 |
|
8 | describe('Graph', () => {
|
9 | it('constructor should initialize an empty graph', () => {
|
10 | let graph = new Graph();
|
11 | assert.deepEqual(graph.nodes, new Map());
|
12 | assert.deepEqual(graph.getAllEdges(), []);
|
13 | });
|
14 |
|
15 | it('addNode should add a node to the graph', () => {
|
16 | let graph = new Graph();
|
17 | let node = {id: 'a', value: 'a'};
|
18 | graph.addNode(node);
|
19 | assert.equal(graph.nodes.get(node.id), node);
|
20 | });
|
21 |
|
22 | it("errors when removeNode is called with a node that doesn't belong", () => {
|
23 | let graph = new Graph();
|
24 | assert.throws(() => {
|
25 | graph.removeNode({id: 'dne', value: null});
|
26 | }, /Does not have node/);
|
27 | });
|
28 |
|
29 | it('errors when traversing a graph with no root', () => {
|
30 | let graph = new Graph();
|
31 |
|
32 | assert.throws(() => {
|
33 | graph.traverse(() => {});
|
34 | }, /A start node is required to traverse/);
|
35 | });
|
36 |
|
37 | it("errors when traversing a graph with a startNode that doesn't belong", () => {
|
38 | let graph = new Graph();
|
39 |
|
40 | assert.throws(() => {
|
41 | graph.traverse(() => {}, {id: 'dne', value: null});
|
42 | }, /Does not have node/);
|
43 | });
|
44 |
|
45 | it("errors if replaceNodesConnectedTo is called with a node that doesn't belong", () => {
|
46 | let graph = new Graph();
|
47 | assert.throws(() => {
|
48 | graph.replaceNodesConnectedTo({id: 'dne', value: null}, []);
|
49 | }, /Does not have node/);
|
50 | });
|
51 |
|
52 | it("errors when adding an edge to a node that doesn't exist", () => {
|
53 | let graph = new Graph();
|
54 | graph.addNode({id: 'foo', value: null});
|
55 | assert.throws(() => {
|
56 | graph.addEdge('foo', 'dne');
|
57 | }, /"to" node 'dne' not found/);
|
58 | });
|
59 |
|
60 | it("errors when adding an edge from a node that doesn't exist", () => {
|
61 | let graph = new Graph();
|
62 | graph.addNode({id: 'foo', value: null});
|
63 | assert.throws(() => {
|
64 | graph.addEdge('dne', 'foo');
|
65 | }, /"from" node 'dne' not found/);
|
66 | });
|
67 |
|
68 | it('hasNode should return a boolean based on whether the node exists in the graph', () => {
|
69 | let graph = new Graph();
|
70 | let node = {id: 'a', value: 'a'};
|
71 | graph.addNode(node);
|
72 | assert(graph.hasNode(node.id));
|
73 | assert(!graph.hasNode('b'));
|
74 | });
|
75 |
|
76 | it('addEdge should add an edge to the graph', () => {
|
77 | let graph = new Graph();
|
78 | graph.addNode({id: 'a', value: null});
|
79 | graph.addNode({id: 'b', value: null});
|
80 | graph.addEdge('a', 'b');
|
81 | assert(graph.hasEdge('a', 'b'));
|
82 | });
|
83 |
|
84 | it('isOrphanedNode should return true or false if the node is orphaned or not', () => {
|
85 | let graph = new Graph();
|
86 | let nodeA = {id: 'a', value: 'a'};
|
87 | let nodeB = {id: 'b', value: 'b'};
|
88 | let nodeC = {id: 'c', value: 'c'};
|
89 | graph.addNode(nodeA);
|
90 | graph.addNode(nodeB);
|
91 | graph.addNode(nodeC);
|
92 | graph.addEdge('a', 'b');
|
93 | graph.addEdge('a', 'c', 'edgetype');
|
94 | assert(graph.isOrphanedNode(nodeA));
|
95 | assert(!graph.isOrphanedNode(nodeB));
|
96 | assert(!graph.isOrphanedNode(nodeC));
|
97 | });
|
98 |
|
99 | it('removeEdge should prune the graph at that edge', () => {
|
100 |
|
101 |
|
102 |
|
103 |
|
104 |
|
105 | let graph = new Graph();
|
106 | graph.addNode({id: 'a', value: 'a'});
|
107 | graph.addNode({id: 'b', value: 'b'});
|
108 | graph.addNode({id: 'c', value: 'c'});
|
109 | graph.addNode({id: 'd', value: 'd'});
|
110 | graph.addEdge('a', 'b');
|
111 | graph.addEdge('a', 'd');
|
112 | graph.addEdge('b', 'c');
|
113 | graph.addEdge('b', 'd');
|
114 |
|
115 | graph.removeEdge('a', 'b');
|
116 | assert(graph.nodes.has('a'));
|
117 | assert(graph.nodes.has('d'));
|
118 | assert(!graph.nodes.has('b'));
|
119 | assert(!graph.nodes.has('c'));
|
120 | assert.deepEqual(graph.getAllEdges(), [{from: 'a', to: 'd', type: null}]);
|
121 | });
|
122 |
|
123 | it('removing a node recursively deletes orphaned nodes', () => {
|
124 |
|
125 |
|
126 |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 |
|
139 |
|
140 |
|
141 | let graph = new Graph();
|
142 | graph.addNode({id: 'a', value: 'a'});
|
143 | graph.addNode({id: 'b', value: 'b'});
|
144 | graph.addNode({id: 'c', value: 'c'});
|
145 | graph.addNode({id: 'd', value: 'd'});
|
146 | graph.addNode({id: 'e', value: 'e'});
|
147 | graph.addNode({id: 'f', value: 'f'});
|
148 | graph.addNode({id: 'g', value: 'g'});
|
149 |
|
150 | graph.addEdge('a', 'b');
|
151 | graph.addEdge('a', 'c');
|
152 | graph.addEdge('b', 'd');
|
153 | graph.addEdge('b', 'e');
|
154 | graph.addEdge('c', 'f');
|
155 | graph.addEdge('d', 'g');
|
156 |
|
157 | graph.removeById('b');
|
158 |
|
159 | assert.deepEqual(
|
160 | [...graph.nodes.values()].map(node => node.id),
|
161 | ['a', 'c', 'f'],
|
162 | );
|
163 | assert.deepEqual(graph.getAllEdges(), [
|
164 | {from: 'a', to: 'c', type: null},
|
165 | {from: 'c', to: 'f', type: null},
|
166 | ]);
|
167 | });
|
168 |
|
169 | it('removing a node recursively deletes orphaned nodes if there is no path to the root', () => {
|
170 |
|
171 |
|
172 |
|
173 |
|
174 |
|
175 |
|
176 |
|
177 |
|
178 |
|
179 |
|
180 |
|
181 |
|
182 |
|
183 |
|
184 |
|
185 |
|
186 |
|
187 | let graph = new Graph();
|
188 | graph.setRootNode({id: 'a', value: 'a'});
|
189 | graph.addNode({id: 'b', value: 'b'});
|
190 | graph.addNode({id: 'c', value: 'c'});
|
191 | graph.addNode({id: 'd', value: 'd'});
|
192 | graph.addNode({id: 'e', value: 'e'});
|
193 | graph.addNode({id: 'f', value: 'f'});
|
194 | graph.addNode({id: 'g', value: 'g'});
|
195 |
|
196 | graph.addEdge('a', 'b');
|
197 | graph.addEdge('a', 'c');
|
198 | graph.addEdge('b', 'd');
|
199 | graph.addEdge('g', 'd');
|
200 | graph.addEdge('b', 'e');
|
201 | graph.addEdge('c', 'f');
|
202 | graph.addEdge('d', 'g');
|
203 |
|
204 | graph.removeById('b');
|
205 |
|
206 | assert.deepEqual(
|
207 | [...graph.nodes.values()].map(node => node.id),
|
208 | ['a', 'c', 'f'],
|
209 | );
|
210 | assert.deepEqual(graph.getAllEdges(), [
|
211 | {from: 'a', to: 'c', type: null},
|
212 | {from: 'c', to: 'f', type: null},
|
213 | ]);
|
214 | });
|
215 |
|
216 | it('removing an edge to a node that cycles does not remove it if there is a path to the root', () => {
|
217 |
|
218 |
|
219 |
|
220 |
|
221 |
|
222 |
|
223 |
|
224 | let graph = new Graph();
|
225 | graph.setRootNode({id: 'a', value: 'a'});
|
226 | graph.addNode({id: 'b', value: 'b'});
|
227 | graph.addNode({id: 'c', value: 'c'});
|
228 | graph.addNode({id: 'd', value: 'd'});
|
229 | graph.addNode({id: 'e', value: 'e'});
|
230 |
|
231 | graph.addEdge('a', 'b');
|
232 | graph.addEdge('b', 'c');
|
233 | graph.addEdge('b', 'd');
|
234 | graph.addEdge('c', 'e');
|
235 | graph.addEdge('d', 'e');
|
236 | graph.addEdge('e', 'b');
|
237 |
|
238 | const getNodeIds = () => [...graph.nodes.values()].map(node => node.id);
|
239 | let nodesBefore = getNodeIds();
|
240 |
|
241 | graph.removeEdge('c', 'e');
|
242 |
|
243 | assert.deepEqual(nodesBefore, getNodeIds());
|
244 | assert.deepEqual(graph.getAllEdges(), [
|
245 | {from: 'a', to: 'b', type: null},
|
246 | {from: 'b', to: 'c', type: null},
|
247 | {from: 'b', to: 'd', type: null},
|
248 | {from: 'd', to: 'e', type: null},
|
249 | {from: 'e', to: 'b', type: null},
|
250 | ]);
|
251 | });
|
252 |
|
253 | it('removing a node with only one inbound edge does not cause it to be removed as an orphan', () => {
|
254 | let graph = new Graph();
|
255 |
|
256 | graph.setRootNode({id: 'a', value: 'a'});
|
257 | graph.addNode({id: 'b', value: 'b'});
|
258 | graph.addEdge('a', 'b');
|
259 |
|
260 | let spy = sinon.spy(graph, 'removeNode');
|
261 | try {
|
262 | graph.removeById('b');
|
263 |
|
264 | assert(spy.calledOnceWithExactly({id: 'b', value: 'b'}));
|
265 | } finally {
|
266 | spy.restore();
|
267 | }
|
268 | });
|
269 |
|
270 | it("replaceNodesConnectedTo should update a node's downstream nodes", () => {
|
271 | let graph = new Graph();
|
272 | let nodeA = graph.addNode({id: 'a', value: 'a'});
|
273 | let nodeB = graph.addNode({id: 'b', value: 'b'});
|
274 | graph.addNode({id: 'c', value: 'c'});
|
275 | graph.addEdge('a', 'b');
|
276 | graph.addEdge('a', 'c');
|
277 |
|
278 | let nodeD = {id: 'd', value: 'd'};
|
279 | graph.replaceNodesConnectedTo(nodeA, [nodeB, nodeD]);
|
280 |
|
281 | assert(graph.nodes.has('a'));
|
282 | assert(graph.nodes.has('b'));
|
283 | assert(!graph.nodes.has('c'));
|
284 | assert(graph.nodes.has('d'));
|
285 | assert.deepEqual(graph.getAllEdges(), [
|
286 | {from: 'a', to: 'b', type: null},
|
287 | {from: 'a', to: 'd', type: null},
|
288 | ]);
|
289 | });
|
290 |
|
291 | it('traverses along edge types if a filter is given', () => {
|
292 | let graph = new Graph();
|
293 | graph.addNode({id: 'a', value: 'a'});
|
294 | graph.addNode({id: 'b', value: 'b'});
|
295 | graph.addNode({id: 'c', value: 'c'});
|
296 | graph.addNode({id: 'd', value: 'd'});
|
297 |
|
298 | graph.addEdge('a', 'b', 'edgetype');
|
299 | graph.addEdge('a', 'd');
|
300 | graph.addEdge('b', 'c');
|
301 | graph.addEdge('b', 'd', 'edgetype');
|
302 |
|
303 | graph.rootNodeId = 'a';
|
304 |
|
305 | let visited = [];
|
306 | graph.traverse(
|
307 | node => {
|
308 | visited.push(node.id);
|
309 | },
|
310 | null,
|
311 | 'edgetype',
|
312 | );
|
313 | assert.deepEqual(visited, ['a', 'b', 'd']);
|
314 | });
|
315 | });
|