1 | "use strict";
|
2 | Object.defineProperty(exports, "__esModule", { value: true });
|
3 | exports.Graph = void 0;
|
4 |
|
5 |
|
6 | const constant = require("lodash.constant");
|
7 | const each = require("lodash.foreach");
|
8 | const _filter = require("lodash.foreach");
|
9 | const isEmpty = require("lodash.isempty");
|
10 | const isFunction = require("lodash.isfunction");
|
11 | const isUndefined = require("lodash.isundefined");
|
12 | const reduce = require("lodash.reduce");
|
13 | const union = require("lodash.union");
|
14 | const values = require("lodash.values");
|
15 | const DEFAULT_EDGE_NAME = '\x00';
|
16 | const GRAPH_NODE = '\x00';
|
17 | const EDGE_KEY_DELIM = '\x01';
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 | class Graph {
|
28 | constructor(opts) {
|
29 | var _a, _b, _c;
|
30 |
|
31 | this._nodeCount = 0;
|
32 |
|
33 | this._edgeCount = 0;
|
34 | this._isDirected = (_a = opts === null || opts === void 0 ? void 0 : opts.directed) !== null && _a !== void 0 ? _a : true;
|
35 | this._isMultigraph = (_b = opts === null || opts === void 0 ? void 0 : opts.multigraph) !== null && _b !== void 0 ? _b : false;
|
36 | this._isCompound = (_c = opts === null || opts === void 0 ? void 0 : opts.compound) !== null && _c !== void 0 ? _c : false;
|
37 |
|
38 | this._label = undefined;
|
39 |
|
40 | this._defaultNodeLabelFn = constant(undefined);
|
41 |
|
42 | this._defaultEdgeLabelFn = constant(undefined);
|
43 |
|
44 | this._nodes = {};
|
45 | if (this._isCompound) {
|
46 |
|
47 | this._parent = {};
|
48 |
|
49 | this._children = {};
|
50 | this._children[GRAPH_NODE] = {};
|
51 | }
|
52 |
|
53 | this._in = {};
|
54 |
|
55 | this._preds = {};
|
56 |
|
57 | this._out = {};
|
58 |
|
59 | this._sucs = {};
|
60 |
|
61 | this._edgeObjs = {};
|
62 |
|
63 | this._edgeLabels = {};
|
64 | }
|
65 |
|
66 | isDirected() {
|
67 | return this._isDirected;
|
68 | }
|
69 | isMultigraph() {
|
70 | return this._isMultigraph;
|
71 | }
|
72 | isCompound() {
|
73 | return this._isCompound;
|
74 | }
|
75 | setGraph(label) {
|
76 | this._label = label;
|
77 | return this;
|
78 | }
|
79 | graph() {
|
80 | return this._label;
|
81 | }
|
82 |
|
83 | setDefaultNodeLabel(newDefault) {
|
84 | if (!isFunction(newDefault)) {
|
85 | newDefault = constant(newDefault);
|
86 | }
|
87 | this._defaultNodeLabelFn = newDefault;
|
88 | return this;
|
89 | }
|
90 | nodeCount() {
|
91 | return this._nodeCount;
|
92 | }
|
93 | nodes() {
|
94 | return Object.keys(this._nodes);
|
95 | }
|
96 | sources() {
|
97 | const self = this;
|
98 | return _filter(this.nodes(), function (v) {
|
99 | return isEmpty(self._in[v]);
|
100 | });
|
101 | }
|
102 | sinks() {
|
103 | const self = this;
|
104 | return _filter(this.nodes(), function (v) {
|
105 | return isEmpty(self._out[v]);
|
106 | });
|
107 | }
|
108 | setNodes(vs, value) {
|
109 | const args = arguments;
|
110 | const self = this;
|
111 | each(vs, function (v) {
|
112 | if (args.length > 1) {
|
113 | self.setNode(v, value);
|
114 | }
|
115 | else {
|
116 | self.setNode(v);
|
117 | }
|
118 | });
|
119 | return this;
|
120 | }
|
121 | setNode(v, value) {
|
122 | if (v in this._nodes) {
|
123 | if (arguments.length > 1) {
|
124 | this._nodes[v] = value;
|
125 | }
|
126 | return this;
|
127 | }
|
128 | this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v);
|
129 | if (this._isCompound) {
|
130 | this._parent[v] = GRAPH_NODE;
|
131 | this._children[v] = {};
|
132 | this._children[GRAPH_NODE][v] = true;
|
133 | }
|
134 | this._in[v] = {};
|
135 | this._preds[v] = {};
|
136 | this._out[v] = {};
|
137 | this._sucs[v] = {};
|
138 | ++this._nodeCount;
|
139 | return this;
|
140 | }
|
141 | node(v) {
|
142 | return this._nodes[v];
|
143 | }
|
144 | hasNode(v) {
|
145 | return v in this._nodes;
|
146 | }
|
147 | removeNode(v) {
|
148 | const self = this;
|
149 | if (v in this._nodes) {
|
150 | const removeEdge = function (e) {
|
151 | self.removeEdge(self._edgeObjs[e]);
|
152 | };
|
153 | delete this._nodes[v];
|
154 | if (this._isCompound) {
|
155 | this._removeFromParentsChildList(v);
|
156 | delete this._parent[v];
|
157 | each(this.children(v), function (child) {
|
158 | self.setParent(child);
|
159 | });
|
160 | delete this._children[v];
|
161 | }
|
162 | each(Object.keys(this._in[v]), removeEdge);
|
163 | delete this._in[v];
|
164 | delete this._preds[v];
|
165 | each(Object.keys(this._out[v]), removeEdge);
|
166 | delete this._out[v];
|
167 | delete this._sucs[v];
|
168 | --this._nodeCount;
|
169 | }
|
170 | return this;
|
171 | }
|
172 | setParent(v, parent) {
|
173 | if (!this._isCompound) {
|
174 | throw new Error('Cannot set parent in a non-compound graph');
|
175 | }
|
176 | if (isUndefined(parent)) {
|
177 | parent = GRAPH_NODE;
|
178 | }
|
179 | else {
|
180 |
|
181 | parent += '';
|
182 | for (let ancestor = parent; !isUndefined(ancestor); ancestor = this.parent(ancestor)) {
|
183 | if (ancestor === v) {
|
184 | throw new Error('Setting ' +
|
185 | parent +
|
186 | ' as parent of ' +
|
187 | v +
|
188 | ' would create a cycle');
|
189 | }
|
190 | }
|
191 | this.setNode(parent);
|
192 | }
|
193 | this.setNode(v);
|
194 | this._removeFromParentsChildList(v);
|
195 | this._parent[v] = parent;
|
196 | this._children[parent][v] = true;
|
197 | return this;
|
198 | }
|
199 | _removeFromParentsChildList(v) {
|
200 | delete this._children[this._parent[v]][v];
|
201 | }
|
202 | parent(v) {
|
203 | if (this._isCompound) {
|
204 | const parent = this._parent[v];
|
205 | if (parent !== GRAPH_NODE) {
|
206 | return parent;
|
207 | }
|
208 | }
|
209 | }
|
210 | children(v) {
|
211 | if (isUndefined(v)) {
|
212 | v = GRAPH_NODE;
|
213 | }
|
214 | if (this._isCompound) {
|
215 | const children = this._children[v];
|
216 | if (children) {
|
217 | return Object.keys(children);
|
218 | }
|
219 | }
|
220 | else if (v === GRAPH_NODE) {
|
221 | return this.nodes();
|
222 | }
|
223 | else if (this.hasNode(v)) {
|
224 | return [];
|
225 | }
|
226 | }
|
227 | predecessors(v) {
|
228 | const predsV = this._preds[v];
|
229 | if (predsV) {
|
230 | return Object.keys(predsV);
|
231 | }
|
232 | }
|
233 | successors(v) {
|
234 | const sucsV = this._sucs[v];
|
235 | if (sucsV) {
|
236 | return Object.keys(sucsV);
|
237 | }
|
238 | }
|
239 | neighbors(v) {
|
240 | const preds = this.predecessors(v);
|
241 | if (preds) {
|
242 | return union(preds, this.successors(v));
|
243 | }
|
244 | }
|
245 | isLeaf(v) {
|
246 | let neighbors;
|
247 | if (this.isDirected()) {
|
248 | neighbors = this.successors(v);
|
249 | }
|
250 | else {
|
251 | neighbors = this.neighbors(v);
|
252 | }
|
253 | return neighbors.length === 0;
|
254 | }
|
255 | filterNodes(filter) {
|
256 | const copy = new Graph({
|
257 | directed: this._isDirected,
|
258 | multigraph: this._isMultigraph,
|
259 | compound: this._isCompound,
|
260 | });
|
261 | copy.setGraph(this.graph());
|
262 | const self = this;
|
263 | each(this._nodes, function (value, v) {
|
264 | if (filter(v)) {
|
265 | copy.setNode(v, value);
|
266 | }
|
267 | });
|
268 | each(this._edgeObjs, function (e) {
|
269 | if (copy.hasNode(e.v) && copy.hasNode(e.w)) {
|
270 | copy.setEdge(e, self.edge(e));
|
271 | }
|
272 | });
|
273 | const parents = {};
|
274 | function findParent(v) {
|
275 | const parent = self.parent(v);
|
276 | if (parent === undefined || copy.hasNode(parent)) {
|
277 | parents[v] = parent;
|
278 | return parent;
|
279 | }
|
280 | else if (parent in parents) {
|
281 | return parents[parent];
|
282 | }
|
283 | else {
|
284 | return findParent(parent);
|
285 | }
|
286 | }
|
287 | if (this._isCompound) {
|
288 | each(copy.nodes(), function (v) {
|
289 | copy.setParent(v, findParent(v));
|
290 | });
|
291 | }
|
292 | return copy;
|
293 | }
|
294 |
|
295 | setDefaultEdgeLabel(newDefault) {
|
296 | if (!isFunction(newDefault)) {
|
297 | newDefault = constant(newDefault);
|
298 | }
|
299 | this._defaultEdgeLabelFn = newDefault;
|
300 | return this;
|
301 | }
|
302 | edgeCount() {
|
303 | return this._edgeCount;
|
304 | }
|
305 | edges() {
|
306 | return values(this._edgeObjs);
|
307 | }
|
308 | setPath(vs, value) {
|
309 | const self = this;
|
310 | const args = arguments;
|
311 | reduce(vs, function (v, w) {
|
312 | if (args.length > 1) {
|
313 | self.setEdge(v, w, value);
|
314 | }
|
315 | else {
|
316 | self.setEdge(v, w);
|
317 | }
|
318 | return w;
|
319 | });
|
320 | return this;
|
321 | }
|
322 |
|
323 | setEdge(...args) {
|
324 | let v, w, name, value;
|
325 | let valueSpecified = false;
|
326 | const arg0 = arguments[0];
|
327 | if (typeof arg0 === 'object' && arg0 !== null && 'v' in arg0) {
|
328 | v = arg0.v;
|
329 | w = arg0.w;
|
330 | name = arg0.name;
|
331 | if (arguments.length === 2) {
|
332 | value = arguments[1];
|
333 | valueSpecified = true;
|
334 | }
|
335 | }
|
336 | else {
|
337 | v = arg0;
|
338 | w = arguments[1];
|
339 | name = arguments[3];
|
340 | if (arguments.length > 2) {
|
341 | value = arguments[2];
|
342 | valueSpecified = true;
|
343 | }
|
344 | }
|
345 | v = '' + v;
|
346 | w = '' + w;
|
347 | if (!isUndefined(name)) {
|
348 | name = '' + name;
|
349 | }
|
350 | const e = edgeArgsToId(this._isDirected, v, w, name);
|
351 | if (e in this._edgeLabels) {
|
352 | if (valueSpecified) {
|
353 | this._edgeLabels[e] = value;
|
354 | }
|
355 | return this;
|
356 | }
|
357 | if (!isUndefined(name) && !this._isMultigraph) {
|
358 | throw new Error('Cannot set a named edge when isMultigraph = false');
|
359 | }
|
360 |
|
361 |
|
362 | this.setNode(v);
|
363 | this.setNode(w);
|
364 | this._edgeLabels[e] = valueSpecified
|
365 | ? value
|
366 | : this._defaultEdgeLabelFn(v, w, name);
|
367 | const edgeObj = edgeArgsToObj(this._isDirected, v, w, name);
|
368 |
|
369 | v = edgeObj.v;
|
370 | w = edgeObj.w;
|
371 | Object.freeze(edgeObj);
|
372 | this._edgeObjs[e] = edgeObj;
|
373 | incrementOrInitEntry(this._preds[w], v);
|
374 | incrementOrInitEntry(this._sucs[v], w);
|
375 | this._in[w][e] = edgeObj;
|
376 | this._out[v][e] = edgeObj;
|
377 | this._edgeCount++;
|
378 | return this;
|
379 | }
|
380 | edge(v, w, name) {
|
381 | const e = arguments.length === 1
|
382 | ? edgeObjToId(this._isDirected, arguments[0])
|
383 | : edgeArgsToId(this._isDirected, v, w, name);
|
384 | return this._edgeLabels[e];
|
385 | }
|
386 | hasEdge(v, w, name) {
|
387 | const e = arguments.length === 1
|
388 | ? edgeObjToId(this._isDirected, arguments[0])
|
389 | : edgeArgsToId(this._isDirected, v, w, name);
|
390 | return e in this._edgeLabels;
|
391 | }
|
392 | removeEdge(v, w, name) {
|
393 | const e = arguments.length === 1
|
394 | ? edgeObjToId(this._isDirected, arguments[0])
|
395 | : edgeArgsToId(this._isDirected, v, w, name);
|
396 | const edge = this._edgeObjs[e];
|
397 | if (edge) {
|
398 | v = edge.v;
|
399 | w = edge.w;
|
400 | delete this._edgeLabels[e];
|
401 | delete this._edgeObjs[e];
|
402 | decrementOrRemoveEntry(this._preds[w], v);
|
403 | decrementOrRemoveEntry(this._sucs[v], w);
|
404 | delete this._in[w][e];
|
405 | delete this._out[v][e];
|
406 | this._edgeCount--;
|
407 | }
|
408 | return this;
|
409 | }
|
410 | inEdges(v, u) {
|
411 | const inV = this._in[v];
|
412 | if (inV) {
|
413 | const edges = values(inV);
|
414 | if (!u) {
|
415 | return edges;
|
416 | }
|
417 | return _filter(edges, function (edge) {
|
418 | return edge.v === u;
|
419 | });
|
420 | }
|
421 | }
|
422 | outEdges(v, w) {
|
423 | const outV = this._out[v];
|
424 | if (outV) {
|
425 | const edges = values(outV);
|
426 | if (!w) {
|
427 | return edges;
|
428 | }
|
429 | return _filter(edges, function (edge) {
|
430 | return edge.w === w;
|
431 | });
|
432 | }
|
433 | }
|
434 | nodeEdges(v, w) {
|
435 | const inEdges = this.inEdges(v, w);
|
436 | if (inEdges) {
|
437 | return inEdges.concat(this.outEdges(v, w));
|
438 | }
|
439 | }
|
440 | }
|
441 | exports.Graph = Graph;
|
442 | function incrementOrInitEntry(map, k) {
|
443 | if (map[k]) {
|
444 | map[k]++;
|
445 | }
|
446 | else {
|
447 | map[k] = 1;
|
448 | }
|
449 | }
|
450 | function decrementOrRemoveEntry(map, k) {
|
451 | if (!--map[k]) {
|
452 | delete map[k];
|
453 | }
|
454 | }
|
455 | function edgeArgsToId(isDirected, v_, w_, name) {
|
456 | let v = '' + v_;
|
457 | let w = '' + w_;
|
458 | if (!isDirected && v > w) {
|
459 | const tmp = v;
|
460 | v = w;
|
461 | w = tmp;
|
462 | }
|
463 | return (v +
|
464 | EDGE_KEY_DELIM +
|
465 | w +
|
466 | EDGE_KEY_DELIM +
|
467 | (isUndefined(name) ? DEFAULT_EDGE_NAME : name));
|
468 | }
|
469 | function edgeArgsToObj(isDirected, v_, w_, name) {
|
470 | let v = '' + v_;
|
471 | let w = '' + w_;
|
472 | if (!isDirected && v > w) {
|
473 | const tmp = v;
|
474 | v = w;
|
475 | w = tmp;
|
476 | }
|
477 | const edgeObj = { v: v, w: w };
|
478 | if (name) {
|
479 | edgeObj.name = name;
|
480 | }
|
481 | return edgeObj;
|
482 | }
|
483 | function edgeObjToId(isDirected, edgeObj) {
|
484 | return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name);
|
485 | }
|
486 |
|
\ | No newline at end of file |