1 | (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
|
2 | (function (global){
|
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 | global.graphlib = require('./index');
|
34 |
|
35 | }).call(this,typeof global !== "undefined" ? global : typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {})
|
36 | },{"./index":2}],2:[function(require,module,exports){
|
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 | var lib = require("./lib");
|
68 |
|
69 | module.exports = {
|
70 | Graph: lib.Graph,
|
71 | json: require("./lib/json"),
|
72 | alg: require("./lib/alg"),
|
73 | version: lib.version
|
74 | };
|
75 |
|
76 | },{"./lib":18,"./lib/alg":9,"./lib/json":19}],3:[function(require,module,exports){
|
77 | var _ = require("../lodash");
|
78 |
|
79 | module.exports = components;
|
80 |
|
81 | function components(g) {
|
82 | var visited = {},
|
83 | cmpts = [],
|
84 | cmpt;
|
85 |
|
86 | function dfs(v) {
|
87 | if (_.has(visited, v)) return;
|
88 | visited[v] = true;
|
89 | cmpt.push(v);
|
90 | _.each(g.successors(v), dfs);
|
91 | _.each(g.predecessors(v), dfs);
|
92 | }
|
93 |
|
94 | _.each(g.nodes(), function(v) {
|
95 | cmpt = [];
|
96 | dfs(v);
|
97 | if (cmpt.length) {
|
98 | cmpts.push(cmpt);
|
99 | }
|
100 | });
|
101 |
|
102 | return cmpts;
|
103 | }
|
104 |
|
105 | },{"../lodash":20}],4:[function(require,module,exports){
|
106 | var _ = require("../lodash");
|
107 |
|
108 | module.exports = dfs;
|
109 |
|
110 |
|
111 |
|
112 |
|
113 |
|
114 |
|
115 |
|
116 |
|
117 | function dfs(g, vs, order) {
|
118 | if (!_.isArray(vs)) {
|
119 | vs = [vs];
|
120 | }
|
121 |
|
122 | var acc = [],
|
123 | visited = {};
|
124 | _.each(vs, function(v) {
|
125 | if (!g.hasNode(v)) {
|
126 | throw new Error("Graph does not have node: " + v);
|
127 | }
|
128 |
|
129 | doDfs(g, v, order === "post", visited, acc);
|
130 | });
|
131 | return acc;
|
132 | }
|
133 |
|
134 | function doDfs(g, v, postorder, visited, acc) {
|
135 | if (!_.has(visited, v)) {
|
136 | visited[v] = true;
|
137 |
|
138 | if (!postorder) { acc.push(v); }
|
139 | _.each(g.neighbors(v), function(w) {
|
140 | doDfs(g, w, postorder, visited, acc);
|
141 | });
|
142 | if (postorder) { acc.push(v); }
|
143 | }
|
144 | }
|
145 |
|
146 | },{"../lodash":20}],5:[function(require,module,exports){
|
147 | var dijkstra = require("./dijkstra"),
|
148 | _ = require("../lodash");
|
149 |
|
150 | module.exports = dijkstraAll;
|
151 |
|
152 | function dijkstraAll(g, weightFunc, edgeFunc) {
|
153 | return _.transform(g.nodes(), function(acc, v) {
|
154 | acc[v] = dijkstra(g, v, weightFunc, edgeFunc);
|
155 | }, {});
|
156 | }
|
157 |
|
158 | },{"../lodash":20,"./dijkstra":6}],6:[function(require,module,exports){
|
159 | var _ = require("../lodash"),
|
160 | PriorityQueue = require("../data/priority-queue");
|
161 |
|
162 | module.exports = dijkstra;
|
163 |
|
164 | var DEFAULT_WEIGHT_FUNC = _.constant(1);
|
165 |
|
166 | function dijkstra(g, source, weightFn, edgeFn) {
|
167 | return runDijkstra(g, String(source),
|
168 | weightFn || DEFAULT_WEIGHT_FUNC,
|
169 | edgeFn || function(v) { return g.outEdges(v); });
|
170 | }
|
171 |
|
172 | function runDijkstra(g, source, weightFn, edgeFn) {
|
173 | var results = {},
|
174 | pq = new PriorityQueue(),
|
175 | v, vEntry;
|
176 |
|
177 | var updateNeighbors = function(edge) {
|
178 | var w = edge.v !== v ? edge.v : edge.w,
|
179 | wEntry = results[w],
|
180 | weight = weightFn(edge),
|
181 | distance = vEntry.distance + weight;
|
182 |
|
183 | if (weight < 0) {
|
184 | throw new Error("dijkstra does not allow negative edge weights. " +
|
185 | "Bad edge: " + edge + " Weight: " + weight);
|
186 | }
|
187 |
|
188 | if (distance < wEntry.distance) {
|
189 | wEntry.distance = distance;
|
190 | wEntry.predecessor = v;
|
191 | pq.decrease(w, distance);
|
192 | }
|
193 | };
|
194 |
|
195 | g.nodes().forEach(function(v) {
|
196 | var distance = v === source ? 0 : Number.POSITIVE_INFINITY;
|
197 | results[v] = { distance: distance };
|
198 | pq.add(v, distance);
|
199 | });
|
200 |
|
201 | while (pq.size() > 0) {
|
202 | v = pq.removeMin();
|
203 | vEntry = results[v];
|
204 | if (vEntry.distance === Number.POSITIVE_INFINITY) {
|
205 | break;
|
206 | }
|
207 |
|
208 | edgeFn(v).forEach(updateNeighbors);
|
209 | }
|
210 |
|
211 | return results;
|
212 | }
|
213 |
|
214 | },{"../data/priority-queue":16,"../lodash":20}],7:[function(require,module,exports){
|
215 | var _ = require("../lodash"),
|
216 | tarjan = require("./tarjan");
|
217 |
|
218 | module.exports = findCycles;
|
219 |
|
220 | function findCycles(g) {
|
221 | return _.filter(tarjan(g), function(cmpt) { return cmpt.length > 1; });
|
222 | }
|
223 |
|
224 | },{"../lodash":20,"./tarjan":14}],8:[function(require,module,exports){
|
225 | var _ = require("../lodash");
|
226 |
|
227 | module.exports = floydWarshall;
|
228 |
|
229 | var DEFAULT_WEIGHT_FUNC = _.constant(1);
|
230 |
|
231 | function floydWarshall(g, weightFn, edgeFn) {
|
232 | return runFloydWarshall(g,
|
233 | weightFn || DEFAULT_WEIGHT_FUNC,
|
234 | edgeFn || function(v) { return g.outEdges(v); });
|
235 | }
|
236 |
|
237 | function runFloydWarshall(g, weightFn, edgeFn) {
|
238 | var results = {},
|
239 | nodes = g.nodes();
|
240 |
|
241 | nodes.forEach(function(v) {
|
242 | results[v] = {};
|
243 | results[v][v] = { distance: 0 };
|
244 | nodes.forEach(function(w) {
|
245 | if (v !== w) {
|
246 | results[v][w] = { distance: Number.POSITIVE_INFINITY };
|
247 | }
|
248 | });
|
249 | edgeFn(v).forEach(function(edge) {
|
250 | var w = edge.v === v ? edge.w : edge.v,
|
251 | d = weightFn(edge);
|
252 | results[v][w] = { distance: d, predecessor: v };
|
253 | });
|
254 | });
|
255 |
|
256 | nodes.forEach(function(k) {
|
257 | var rowK = results[k];
|
258 | nodes.forEach(function(i) {
|
259 | var rowI = results[i];
|
260 | nodes.forEach(function(j) {
|
261 | var ik = rowI[k];
|
262 | var kj = rowK[j];
|
263 | var ij = rowI[j];
|
264 | var altDistance = ik.distance + kj.distance;
|
265 | if (altDistance < ij.distance) {
|
266 | ij.distance = altDistance;
|
267 | ij.predecessor = kj.predecessor;
|
268 | }
|
269 | });
|
270 | });
|
271 | });
|
272 |
|
273 | return results;
|
274 | }
|
275 |
|
276 | },{"../lodash":20}],9:[function(require,module,exports){
|
277 | module.exports = {
|
278 | components: require("./components"),
|
279 | dijkstra: require("./dijkstra"),
|
280 | dijkstraAll: require("./dijkstra-all"),
|
281 | findCycles: require("./find-cycles"),
|
282 | floydWarshall: require("./floyd-warshall"),
|
283 | isAcyclic: require("./is-acyclic"),
|
284 | postorder: require("./postorder"),
|
285 | preorder: require("./preorder"),
|
286 | prim: require("./prim"),
|
287 | tarjan: require("./tarjan"),
|
288 | topsort: require("./topsort")
|
289 | };
|
290 |
|
291 | },{"./components":3,"./dijkstra":6,"./dijkstra-all":5,"./find-cycles":7,"./floyd-warshall":8,"./is-acyclic":10,"./postorder":11,"./preorder":12,"./prim":13,"./tarjan":14,"./topsort":15}],10:[function(require,module,exports){
|
292 | var topsort = require("./topsort");
|
293 |
|
294 | module.exports = isAcyclic;
|
295 |
|
296 | function isAcyclic(g) {
|
297 | try {
|
298 | topsort(g);
|
299 | } catch (e) {
|
300 | if (e instanceof topsort.CycleException) {
|
301 | return false;
|
302 | }
|
303 | throw e;
|
304 | }
|
305 | return true;
|
306 | }
|
307 |
|
308 | },{"./topsort":15}],11:[function(require,module,exports){
|
309 | var dfs = require("./dfs");
|
310 |
|
311 | module.exports = postorder;
|
312 |
|
313 | function postorder(g, vs) {
|
314 | return dfs(g, vs, "post");
|
315 | }
|
316 |
|
317 | },{"./dfs":4}],12:[function(require,module,exports){
|
318 | var dfs = require("./dfs");
|
319 |
|
320 | module.exports = preorder;
|
321 |
|
322 | function preorder(g, vs) {
|
323 | return dfs(g, vs, "pre");
|
324 | }
|
325 |
|
326 | },{"./dfs":4}],13:[function(require,module,exports){
|
327 | var _ = require("../lodash"),
|
328 | Graph = require("../graph"),
|
329 | PriorityQueue = require("../data/priority-queue");
|
330 |
|
331 | module.exports = prim;
|
332 |
|
333 | function prim(g, weightFunc) {
|
334 | var result = new Graph(),
|
335 | parents = {},
|
336 | pq = new PriorityQueue(),
|
337 | v;
|
338 |
|
339 | function updateNeighbors(edge) {
|
340 | var w = edge.v === v ? edge.w : edge.v,
|
341 | pri = pq.priority(w);
|
342 | if (pri !== undefined) {
|
343 | var edgeWeight = weightFunc(edge);
|
344 | if (edgeWeight < pri) {
|
345 | parents[w] = v;
|
346 | pq.decrease(w, edgeWeight);
|
347 | }
|
348 | }
|
349 | }
|
350 |
|
351 | if (g.nodeCount() === 0) {
|
352 | return result;
|
353 | }
|
354 |
|
355 | _.each(g.nodes(), function(v) {
|
356 | pq.add(v, Number.POSITIVE_INFINITY);
|
357 | result.setNode(v);
|
358 | });
|
359 |
|
360 |
|
361 | pq.decrease(g.nodes()[0], 0);
|
362 |
|
363 | var init = false;
|
364 | while (pq.size() > 0) {
|
365 | v = pq.removeMin();
|
366 | if (_.has(parents, v)) {
|
367 | result.setEdge(v, parents[v]);
|
368 | } else if (init) {
|
369 | throw new Error("Input graph is not connected: " + g);
|
370 | } else {
|
371 | init = true;
|
372 | }
|
373 |
|
374 | g.nodeEdges(v).forEach(updateNeighbors);
|
375 | }
|
376 |
|
377 | return result;
|
378 | }
|
379 |
|
380 | },{"../data/priority-queue":16,"../graph":17,"../lodash":20}],14:[function(require,module,exports){
|
381 | var _ = require("../lodash");
|
382 |
|
383 | module.exports = tarjan;
|
384 |
|
385 | function tarjan(g) {
|
386 | var index = 0,
|
387 | stack = [],
|
388 | visited = {},
|
389 | results = [];
|
390 |
|
391 | function dfs(v) {
|
392 | var entry = visited[v] = {
|
393 | onStack: true,
|
394 | lowlink: index,
|
395 | index: index++
|
396 | };
|
397 | stack.push(v);
|
398 |
|
399 | g.successors(v).forEach(function(w) {
|
400 | if (!_.has(visited, w)) {
|
401 | dfs(w);
|
402 | entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink);
|
403 | } else if (visited[w].onStack) {
|
404 | entry.lowlink = Math.min(entry.lowlink, visited[w].index);
|
405 | }
|
406 | });
|
407 |
|
408 | if (entry.lowlink === entry.index) {
|
409 | var cmpt = [],
|
410 | w;
|
411 | do {
|
412 | w = stack.pop();
|
413 | visited[w].onStack = false;
|
414 | cmpt.push(w);
|
415 | } while (v !== w);
|
416 | results.push(cmpt);
|
417 | }
|
418 | }
|
419 |
|
420 | g.nodes().forEach(function(v) {
|
421 | if (!_.has(visited, v)) {
|
422 | dfs(v);
|
423 | }
|
424 | });
|
425 |
|
426 | return results;
|
427 | }
|
428 |
|
429 | },{"../lodash":20}],15:[function(require,module,exports){
|
430 | var _ = require("../lodash");
|
431 |
|
432 | module.exports = topsort;
|
433 | topsort.CycleException = CycleException;
|
434 |
|
435 | function topsort(g) {
|
436 | var visited = {},
|
437 | stack = {},
|
438 | results = [];
|
439 |
|
440 | function visit(node) {
|
441 | if (_.has(stack, node)) {
|
442 | throw new CycleException();
|
443 | }
|
444 |
|
445 | if (!_.has(visited, node)) {
|
446 | stack[node] = true;
|
447 | visited[node] = true;
|
448 | _.each(g.predecessors(node), visit);
|
449 | delete stack[node];
|
450 | results.push(node);
|
451 | }
|
452 | }
|
453 |
|
454 | _.each(g.sinks(), visit);
|
455 |
|
456 | if (_.size(visited) !== g.nodeCount()) {
|
457 | throw new CycleException();
|
458 | }
|
459 |
|
460 | return results;
|
461 | }
|
462 |
|
463 | function CycleException() {}
|
464 |
|
465 | },{"../lodash":20}],16:[function(require,module,exports){
|
466 | var _ = require("../lodash");
|
467 |
|
468 | module.exports = PriorityQueue;
|
469 |
|
470 |
|
471 |
|
472 |
|
473 |
|
474 |
|
475 |
|
476 |
|
477 | function PriorityQueue() {
|
478 | this._arr = [];
|
479 | this._keyIndices = {};
|
480 | }
|
481 |
|
482 |
|
483 |
|
484 |
|
485 | PriorityQueue.prototype.size = function() {
|
486 | return this._arr.length;
|
487 | };
|
488 |
|
489 |
|
490 |
|
491 |
|
492 | PriorityQueue.prototype.keys = function() {
|
493 | return this._arr.map(function(x) { return x.key; });
|
494 | };
|
495 |
|
496 |
|
497 |
|
498 |
|
499 | PriorityQueue.prototype.has = function(key) {
|
500 | return _.has(this._keyIndices, key);
|
501 | };
|
502 |
|
503 |
|
504 |
|
505 |
|
506 |
|
507 |
|
508 |
|
509 | PriorityQueue.prototype.priority = function(key) {
|
510 | var index = this._keyIndices[key];
|
511 | if (index !== undefined) {
|
512 | return this._arr[index].priority;
|
513 | }
|
514 | };
|
515 |
|
516 |
|
517 |
|
518 |
|
519 |
|
520 | PriorityQueue.prototype.min = function() {
|
521 | if (this.size() === 0) {
|
522 | throw new Error("Queue underflow");
|
523 | }
|
524 | return this._arr[0].key;
|
525 | };
|
526 |
|
527 |
|
528 |
|
529 |
|
530 |
|
531 |
|
532 |
|
533 |
|
534 |
|
535 | PriorityQueue.prototype.add = function(key, priority) {
|
536 | var keyIndices = this._keyIndices;
|
537 | key = String(key);
|
538 | if (!_.has(keyIndices, key)) {
|
539 | var arr = this._arr;
|
540 | var index = arr.length;
|
541 | keyIndices[key] = index;
|
542 | arr.push({key: key, priority: priority});
|
543 | this._decrease(index);
|
544 | return true;
|
545 | }
|
546 | return false;
|
547 | };
|
548 |
|
549 |
|
550 |
|
551 |
|
552 | PriorityQueue.prototype.removeMin = function() {
|
553 | this._swap(0, this._arr.length - 1);
|
554 | var min = this._arr.pop();
|
555 | delete this._keyIndices[min.key];
|
556 | this._heapify(0);
|
557 | return min.key;
|
558 | };
|
559 |
|
560 |
|
561 |
|
562 |
|
563 |
|
564 |
|
565 |
|
566 |
|
567 | PriorityQueue.prototype.decrease = function(key, priority) {
|
568 | var index = this._keyIndices[key];
|
569 | if (priority > this._arr[index].priority) {
|
570 | throw new Error("New priority is greater than current priority. " +
|
571 | "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
|
572 | }
|
573 | this._arr[index].priority = priority;
|
574 | this._decrease(index);
|
575 | };
|
576 |
|
577 | PriorityQueue.prototype._heapify = function(i) {
|
578 | var arr = this._arr;
|
579 | var l = 2 * i,
|
580 | r = l + 1,
|
581 | largest = i;
|
582 | if (l < arr.length) {
|
583 | largest = arr[l].priority < arr[largest].priority ? l : largest;
|
584 | if (r < arr.length) {
|
585 | largest = arr[r].priority < arr[largest].priority ? r : largest;
|
586 | }
|
587 | if (largest !== i) {
|
588 | this._swap(i, largest);
|
589 | this._heapify(largest);
|
590 | }
|
591 | }
|
592 | };
|
593 |
|
594 | PriorityQueue.prototype._decrease = function(index) {
|
595 | var arr = this._arr;
|
596 | var priority = arr[index].priority;
|
597 | var parent;
|
598 | while (index !== 0) {
|
599 | parent = index >> 1;
|
600 | if (arr[parent].priority < priority) {
|
601 | break;
|
602 | }
|
603 | this._swap(index, parent);
|
604 | index = parent;
|
605 | }
|
606 | };
|
607 |
|
608 | PriorityQueue.prototype._swap = function(i, j) {
|
609 | var arr = this._arr;
|
610 | var keyIndices = this._keyIndices;
|
611 | var origArrI = arr[i];
|
612 | var origArrJ = arr[j];
|
613 | arr[i] = origArrJ;
|
614 | arr[j] = origArrI;
|
615 | keyIndices[origArrJ.key] = i;
|
616 | keyIndices[origArrI.key] = j;
|
617 | };
|
618 |
|
619 | },{"../lodash":20}],17:[function(require,module,exports){
|
620 | "use strict";
|
621 |
|
622 | var _ = require("./lodash");
|
623 |
|
624 | module.exports = Graph;
|
625 |
|
626 | var DEFAULT_EDGE_NAME = "\x00",
|
627 | GRAPH_NODE = "\x00",
|
628 | EDGE_KEY_DELIM = "\x01";
|
629 |
|
630 |
|
631 |
|
632 |
|
633 |
|
634 |
|
635 |
|
636 |
|
637 |
|
638 |
|
639 |
|
640 | function Graph(opts) {
|
641 | this._isDirected = _.has(opts, "directed") ? opts.directed : true;
|
642 | this._isMultigraph = _.has(opts, "multigraph") ? opts.multigraph : false;
|
643 | this._isCompound = _.has(opts, "compound") ? opts.compound : false;
|
644 |
|
645 |
|
646 | this._label = undefined;
|
647 |
|
648 |
|
649 | this._defaultNodeLabelFn = _.constant(undefined);
|
650 |
|
651 |
|
652 | this._defaultEdgeLabelFn = _.constant(undefined);
|
653 |
|
654 |
|
655 | this._nodes = {};
|
656 |
|
657 | if (this._isCompound) {
|
658 |
|
659 | this._parent = {};
|
660 |
|
661 |
|
662 | this._children = {};
|
663 | this._children[GRAPH_NODE] = {};
|
664 | }
|
665 |
|
666 |
|
667 | this._in = {};
|
668 |
|
669 |
|
670 | this._preds = {};
|
671 |
|
672 |
|
673 | this._out = {};
|
674 |
|
675 |
|
676 | this._sucs = {};
|
677 |
|
678 |
|
679 | this._edgeObjs = {};
|
680 |
|
681 |
|
682 | this._edgeLabels = {};
|
683 | }
|
684 |
|
685 |
|
686 | Graph.prototype._nodeCount = 0;
|
687 |
|
688 |
|
689 | Graph.prototype._edgeCount = 0;
|
690 |
|
691 |
|
692 |
|
693 |
|
694 | Graph.prototype.isDirected = function() {
|
695 | return this._isDirected;
|
696 | };
|
697 |
|
698 | Graph.prototype.isMultigraph = function() {
|
699 | return this._isMultigraph;
|
700 | };
|
701 |
|
702 | Graph.prototype.isCompound = function() {
|
703 | return this._isCompound;
|
704 | };
|
705 |
|
706 | Graph.prototype.setGraph = function(label) {
|
707 | this._label = label;
|
708 | return this;
|
709 | };
|
710 |
|
711 | Graph.prototype.graph = function() {
|
712 | return this._label;
|
713 | };
|
714 |
|
715 |
|
716 |
|
717 |
|
718 | Graph.prototype.setDefaultNodeLabel = function(newDefault) {
|
719 | if (!_.isFunction(newDefault)) {
|
720 | newDefault = _.constant(newDefault);
|
721 | }
|
722 | this._defaultNodeLabelFn = newDefault;
|
723 | return this;
|
724 | };
|
725 |
|
726 | Graph.prototype.nodeCount = function() {
|
727 | return this._nodeCount;
|
728 | };
|
729 |
|
730 | Graph.prototype.nodes = function() {
|
731 | return _.keys(this._nodes);
|
732 | };
|
733 |
|
734 | Graph.prototype.sources = function() {
|
735 | return _.filter(this.nodes(), function(v) {
|
736 | return _.isEmpty(this._in[v]);
|
737 | }, this);
|
738 | };
|
739 |
|
740 | Graph.prototype.sinks = function() {
|
741 | return _.filter(this.nodes(), function(v) {
|
742 | return _.isEmpty(this._out[v]);
|
743 | }, this);
|
744 | };
|
745 |
|
746 | Graph.prototype.setNodes = function(vs, value) {
|
747 | var args = arguments;
|
748 | _.each(vs, function(v) {
|
749 | if (args.length > 1) {
|
750 | this.setNode(v, value);
|
751 | } else {
|
752 | this.setNode(v);
|
753 | }
|
754 | }, this);
|
755 | return this;
|
756 | };
|
757 |
|
758 | Graph.prototype.setNode = function(v, value) {
|
759 | if (_.has(this._nodes, v)) {
|
760 | if (arguments.length > 1) {
|
761 | this._nodes[v] = value;
|
762 | }
|
763 | return this;
|
764 | }
|
765 |
|
766 | this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v);
|
767 | if (this._isCompound) {
|
768 | this._parent[v] = GRAPH_NODE;
|
769 | this._children[v] = {};
|
770 | this._children[GRAPH_NODE][v] = true;
|
771 | }
|
772 | this._in[v] = {};
|
773 | this._preds[v] = {};
|
774 | this._out[v] = {};
|
775 | this._sucs[v] = {};
|
776 | ++this._nodeCount;
|
777 | return this;
|
778 | };
|
779 |
|
780 | Graph.prototype.node = function(v) {
|
781 | return this._nodes[v];
|
782 | };
|
783 |
|
784 | Graph.prototype.hasNode = function(v) {
|
785 | return _.has(this._nodes, v);
|
786 | };
|
787 |
|
788 | Graph.prototype.removeNode = function(v) {
|
789 | var self = this;
|
790 | if (_.has(this._nodes, v)) {
|
791 | var removeEdge = function(e) { self.removeEdge(self._edgeObjs[e]); };
|
792 | delete this._nodes[v];
|
793 | if (this._isCompound) {
|
794 | this._removeFromParentsChildList(v);
|
795 | delete this._parent[v];
|
796 | _.each(this.children(v), function(child) {
|
797 | this.setParent(child);
|
798 | }, this);
|
799 | delete this._children[v];
|
800 | }
|
801 | _.each(_.keys(this._in[v]), removeEdge);
|
802 | delete this._in[v];
|
803 | delete this._preds[v];
|
804 | _.each(_.keys(this._out[v]), removeEdge);
|
805 | delete this._out[v];
|
806 | delete this._sucs[v];
|
807 | --this._nodeCount;
|
808 | }
|
809 | return this;
|
810 | };
|
811 |
|
812 | Graph.prototype.setParent = function(v, parent) {
|
813 | if (!this._isCompound) {
|
814 | throw new Error("Cannot set parent in a non-compound graph");
|
815 | }
|
816 |
|
817 | if (_.isUndefined(parent)) {
|
818 | parent = GRAPH_NODE;
|
819 | } else {
|
820 |
|
821 | parent += "";
|
822 | for (var ancestor = parent;
|
823 | !_.isUndefined(ancestor);
|
824 | ancestor = this.parent(ancestor)) {
|
825 | if (ancestor === v) {
|
826 | throw new Error("Setting " + parent+ " as parent of " + v +
|
827 | " would create create a cycle");
|
828 | }
|
829 | }
|
830 |
|
831 | this.setNode(parent);
|
832 | }
|
833 |
|
834 | this.setNode(v);
|
835 | this._removeFromParentsChildList(v);
|
836 | this._parent[v] = parent;
|
837 | this._children[parent][v] = true;
|
838 | return this;
|
839 | };
|
840 |
|
841 | Graph.prototype._removeFromParentsChildList = function(v) {
|
842 | delete this._children[this._parent[v]][v];
|
843 | };
|
844 |
|
845 | Graph.prototype.parent = function(v) {
|
846 | if (this._isCompound) {
|
847 | var parent = this._parent[v];
|
848 | if (parent !== GRAPH_NODE) {
|
849 | return parent;
|
850 | }
|
851 | }
|
852 | };
|
853 |
|
854 | Graph.prototype.children = function(v) {
|
855 | if (_.isUndefined(v)) {
|
856 | v = GRAPH_NODE;
|
857 | }
|
858 |
|
859 | if (this._isCompound) {
|
860 | var children = this._children[v];
|
861 | if (children) {
|
862 | return _.keys(children);
|
863 | }
|
864 | } else if (v === GRAPH_NODE) {
|
865 | return this.nodes();
|
866 | } else if (this.hasNode(v)) {
|
867 | return [];
|
868 | }
|
869 | };
|
870 |
|
871 | Graph.prototype.predecessors = function(v) {
|
872 | var predsV = this._preds[v];
|
873 | if (predsV) {
|
874 | return _.keys(predsV);
|
875 | }
|
876 | };
|
877 |
|
878 | Graph.prototype.successors = function(v) {
|
879 | var sucsV = this._sucs[v];
|
880 | if (sucsV) {
|
881 | return _.keys(sucsV);
|
882 | }
|
883 | };
|
884 |
|
885 | Graph.prototype.neighbors = function(v) {
|
886 | var preds = this.predecessors(v);
|
887 | if (preds) {
|
888 | return _.union(preds, this.successors(v));
|
889 | }
|
890 | };
|
891 |
|
892 |
|
893 |
|
894 | Graph.prototype.setDefaultEdgeLabel = function(newDefault) {
|
895 | if (!_.isFunction(newDefault)) {
|
896 | newDefault = _.constant(newDefault);
|
897 | }
|
898 | this._defaultEdgeLabelFn = newDefault;
|
899 | return this;
|
900 | };
|
901 |
|
902 | Graph.prototype.edgeCount = function() {
|
903 | return this._edgeCount;
|
904 | };
|
905 |
|
906 | Graph.prototype.edges = function() {
|
907 | return _.values(this._edgeObjs);
|
908 | };
|
909 |
|
910 | Graph.prototype.setPath = function(vs, value) {
|
911 | var self = this,
|
912 | args = arguments;
|
913 | _.reduce(vs, function(v, w) {
|
914 | if (args.length > 1) {
|
915 | self.setEdge(v, w, value);
|
916 | } else {
|
917 | self.setEdge(v, w);
|
918 | }
|
919 | return w;
|
920 | });
|
921 | return this;
|
922 | };
|
923 |
|
924 |
|
925 |
|
926 |
|
927 |
|
928 | Graph.prototype.setEdge = function() {
|
929 | var v, w, name, value,
|
930 | valueSpecified = false;
|
931 |
|
932 | if (_.isPlainObject(arguments[0])) {
|
933 | v = arguments[0].v;
|
934 | w = arguments[0].w;
|
935 | name = arguments[0].name;
|
936 | if (arguments.length === 2) {
|
937 | value = arguments[1];
|
938 | valueSpecified = true;
|
939 | }
|
940 | } else {
|
941 | v = arguments[0];
|
942 | w = arguments[1];
|
943 | name = arguments[3];
|
944 | if (arguments.length > 2) {
|
945 | value = arguments[2];
|
946 | valueSpecified = true;
|
947 | }
|
948 | }
|
949 |
|
950 | v = "" + v;
|
951 | w = "" + w;
|
952 | if (!_.isUndefined(name)) {
|
953 | name = "" + name;
|
954 | }
|
955 |
|
956 | var e = edgeArgsToId(this._isDirected, v, w, name);
|
957 | if (_.has(this._edgeLabels, e)) {
|
958 | if (valueSpecified) {
|
959 | this._edgeLabels[e] = value;
|
960 | }
|
961 | return this;
|
962 | }
|
963 |
|
964 | if (!_.isUndefined(name) && !this._isMultigraph) {
|
965 | throw new Error("Cannot set a named edge when isMultigraph = false");
|
966 | }
|
967 |
|
968 |
|
969 |
|
970 | this.setNode(v);
|
971 | this.setNode(w);
|
972 |
|
973 | this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name);
|
974 |
|
975 | var edgeObj = edgeArgsToObj(this._isDirected, v, w, name);
|
976 |
|
977 | v = edgeObj.v;
|
978 | w = edgeObj.w;
|
979 |
|
980 | Object.freeze(edgeObj);
|
981 | this._edgeObjs[e] = edgeObj;
|
982 | incrementOrInitEntry(this._preds[w], v);
|
983 | incrementOrInitEntry(this._sucs[v], w);
|
984 | this._in[w][e] = edgeObj;
|
985 | this._out[v][e] = edgeObj;
|
986 | this._edgeCount++;
|
987 | return this;
|
988 | };
|
989 |
|
990 | Graph.prototype.edge = function(v, w, name) {
|
991 | var e = (arguments.length === 1
|
992 | ? edgeObjToId(this._isDirected, arguments[0])
|
993 | : edgeArgsToId(this._isDirected, v, w, name));
|
994 | return this._edgeLabels[e];
|
995 | };
|
996 |
|
997 | Graph.prototype.hasEdge = function(v, w, name) {
|
998 | var e = (arguments.length === 1
|
999 | ? edgeObjToId(this._isDirected, arguments[0])
|
1000 | : edgeArgsToId(this._isDirected, v, w, name));
|
1001 | return _.has(this._edgeLabels, e);
|
1002 | };
|
1003 |
|
1004 | Graph.prototype.removeEdge = function(v, w, name) {
|
1005 | var e = (arguments.length === 1
|
1006 | ? edgeObjToId(this._isDirected, arguments[0])
|
1007 | : edgeArgsToId(this._isDirected, v, w, name)),
|
1008 | edge = this._edgeObjs[e];
|
1009 | if (edge) {
|
1010 | v = edge.v;
|
1011 | w = edge.w;
|
1012 | delete this._edgeLabels[e];
|
1013 | delete this._edgeObjs[e];
|
1014 | decrementOrRemoveEntry(this._preds[w], v);
|
1015 | decrementOrRemoveEntry(this._sucs[v], w);
|
1016 | delete this._in[w][e];
|
1017 | delete this._out[v][e];
|
1018 | this._edgeCount--;
|
1019 | }
|
1020 | return this;
|
1021 | };
|
1022 |
|
1023 | Graph.prototype.inEdges = function(v, u) {
|
1024 | var inV = this._in[v];
|
1025 | if (inV) {
|
1026 | var edges = _.values(inV);
|
1027 | if (!u) {
|
1028 | return edges;
|
1029 | }
|
1030 | return _.filter(edges, function(edge) { return edge.v === u; });
|
1031 | }
|
1032 | };
|
1033 |
|
1034 | Graph.prototype.outEdges = function(v, w) {
|
1035 | var outV = this._out[v];
|
1036 | if (outV) {
|
1037 | var edges = _.values(outV);
|
1038 | if (!w) {
|
1039 | return edges;
|
1040 | }
|
1041 | return _.filter(edges, function(edge) { return edge.w === w; });
|
1042 | }
|
1043 | };
|
1044 |
|
1045 | Graph.prototype.nodeEdges = function(v, w) {
|
1046 | var inEdges = this.inEdges(v, w);
|
1047 | if (inEdges) {
|
1048 | return inEdges.concat(this.outEdges(v, w));
|
1049 | }
|
1050 | };
|
1051 |
|
1052 | function incrementOrInitEntry(map, k) {
|
1053 | if (_.has(map, k)) {
|
1054 | map[k]++;
|
1055 | } else {
|
1056 | map[k] = 1;
|
1057 | }
|
1058 | }
|
1059 |
|
1060 | function decrementOrRemoveEntry(map, k) {
|
1061 | if (!--map[k]) { delete map[k]; }
|
1062 | }
|
1063 |
|
1064 | function edgeArgsToId(isDirected, v, w, name) {
|
1065 | if (!isDirected && v > w) {
|
1066 | var tmp = v;
|
1067 | v = w;
|
1068 | w = tmp;
|
1069 | }
|
1070 | return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM +
|
1071 | (_.isUndefined(name) ? DEFAULT_EDGE_NAME : name);
|
1072 | }
|
1073 |
|
1074 | function edgeArgsToObj(isDirected, v, w, name) {
|
1075 | if (!isDirected && v > w) {
|
1076 | var tmp = v;
|
1077 | v = w;
|
1078 | w = tmp;
|
1079 | }
|
1080 | var edgeObj = { v: v, w: w };
|
1081 | if (name) {
|
1082 | edgeObj.name = name;
|
1083 | }
|
1084 | return edgeObj;
|
1085 | }
|
1086 |
|
1087 | function edgeObjToId(isDirected, edgeObj) {
|
1088 | return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name);
|
1089 | }
|
1090 |
|
1091 | },{"./lodash":20}],18:[function(require,module,exports){
|
1092 |
|
1093 | module.exports = {
|
1094 | Graph: require("./graph"),
|
1095 | version: require("./version")
|
1096 | };
|
1097 |
|
1098 | },{"./graph":17,"./version":21}],19:[function(require,module,exports){
|
1099 | var _ = require("./lodash"),
|
1100 | Graph = require("./graph");
|
1101 |
|
1102 | module.exports = {
|
1103 | write: write,
|
1104 | read: read
|
1105 | };
|
1106 |
|
1107 | function write(g) {
|
1108 | var json = {
|
1109 | options: {
|
1110 | directed: g.isDirected(),
|
1111 | multigraph: g.isMultigraph(),
|
1112 | compound: g.isCompound()
|
1113 | },
|
1114 | nodes: writeNodes(g),
|
1115 | edges: writeEdges(g)
|
1116 | };
|
1117 | if (!_.isUndefined(g.graph())) {
|
1118 | json.value = _.clone(g.graph());
|
1119 | }
|
1120 | return json;
|
1121 | }
|
1122 |
|
1123 | function writeNodes(g) {
|
1124 | return _.map(g.nodes(), function(v) {
|
1125 | var nodeValue = g.node(v),
|
1126 | parent = g.parent(v),
|
1127 | node = { v: v };
|
1128 | if (!_.isUndefined(nodeValue)) {
|
1129 | node.value = nodeValue;
|
1130 | }
|
1131 | if (!_.isUndefined(parent)) {
|
1132 | node.parent = parent;
|
1133 | }
|
1134 | return node;
|
1135 | });
|
1136 | }
|
1137 |
|
1138 | function writeEdges(g) {
|
1139 | return _.map(g.edges(), function(e) {
|
1140 | var edgeValue = g.edge(e),
|
1141 | edge = { v: e.v, w: e.w };
|
1142 | if (!_.isUndefined(e.name)) {
|
1143 | edge.name = e.name;
|
1144 | }
|
1145 | if (!_.isUndefined(edgeValue)) {
|
1146 | edge.value = edgeValue;
|
1147 | }
|
1148 | return edge;
|
1149 | });
|
1150 | }
|
1151 |
|
1152 | function read(json) {
|
1153 | var g = new Graph(json.options).setGraph(json.value);
|
1154 | _.each(json.nodes, function(entry) {
|
1155 | g.setNode(entry.v, entry.value);
|
1156 | if (entry.parent) {
|
1157 | g.setParent(entry.v, entry.parent);
|
1158 | }
|
1159 | });
|
1160 | _.each(json.edges, function(entry) {
|
1161 | g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value);
|
1162 | });
|
1163 | return g;
|
1164 | }
|
1165 |
|
1166 | },{"./graph":17,"./lodash":20}],20:[function(require,module,exports){
|
1167 |
|
1168 |
|
1169 | var lodash;
|
1170 |
|
1171 | if (typeof require === "function") {
|
1172 | try {
|
1173 | lodash = require("lodash");
|
1174 | } catch (e) {}
|
1175 | }
|
1176 |
|
1177 | if (!lodash) {
|
1178 | lodash = window._;
|
1179 | }
|
1180 |
|
1181 | module.exports = lodash;
|
1182 |
|
1183 | },{"lodash":undefined}],21:[function(require,module,exports){
|
1184 | module.exports = '1.0.2';
|
1185 |
|
1186 | },{}]},{},[1]);
|