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