1
2
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
34
35
36
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
|
/**
* A simple dependency graph
*/
/**
* Helper for creating a Depth-First-Search on
* a set of edges.
*
* Detects cycles and throws an Error if one is detected.
*
* @param edges The set of edges to DFS through
* @param leavesOnly Whether to only return "leaf" nodes (ones who have no edges)
* @param result An array in which the results will be populated
* @param circular A boolean to allow circular dependencies
*/
function createDFS(edges, leavesOnly, result, circular) {
var currentPath = [];
var visited = {};
return function DFS(currentNode) {
visited[currentNode] = true;
currentPath.push(currentNode);
edges[currentNode].forEach(function (node) {
if (!visited[node]) {
DFS(node);
} else if (currentPath.indexOf(node) >= 0) {
currentPath.push(node);
if (!circular) {
throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> '));
}
}
});
currentPath.pop();
if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) {
result.push(currentNode);
}
};
}
/**
* Simple Dependency Graph
*/
var DepGraph = exports.DepGraph = function DepGraph(opts) {
this.nodes = {}; // Node -> Node/Data (treated like a Set)
this.outgoingEdges = {}; // Node -> [Dependency Node]
this.incomingEdges = {}; // Node -> [Dependant Node]
this.circular = opts && !!opts.circular; // Allows circular deps
};
DepGraph.prototype = {
/**
* The number of nodes in the graph.
*/
size:function () {
return Object.keys(this.nodes).length;
},
/**
* Add a node to the dependency graph. If a node already exists, this method will do nothing.
*/
addNode:function (node, data) {
if (!this.hasNode(node)) {
// Checking the arguments length allows the user to add a node with undefined data
if (arguments.length === 2) {
this.nodes[node] = data;
} else {
this.nodes[node] = node;
}
this.outgoingEdges[node] = [];
this.incomingEdges[node] = [];
}
},
/**
* Remove a node from the dependency graph. If a node does not exist, this method will do nothing.
*/
removeNode:function (node) {
if (this.hasNode(node)) {
delete this.nodes[node];
delete this.outgoingEdges[node];
delete this.incomingEdges[node];
[this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) {
Object.keys(edgeList).forEach(function (key) {
var idx = edgeList[key].indexOf(node);
if (idx >= 0) {
edgeList[key].splice(idx, 1);
}
}, this);
});
}
},
/**
* Check if a node exists in the graph
*/
hasNode:function (node) {
return this.nodes.hasOwnProperty(node);
},
/**
* Get the data associated with a node name
*/
getNodeData:function (node) {
if (this.hasNode(node)) {
return this.nodes[node];
} else {
throw new Error('Node does not exist: ' + node);
}
},
/**
* Set the associated data for a given node name. If the node does not exist, this method will throw an error
*/
setNodeData:function (node, data) {
if (this.hasNode(node)) {
this.nodes[node] = data;
} else {
throw new Error('Node does not exist: ' + node);
}
},
/**
* Add a dependency between two nodes. If either of the nodes does not exist,
* an Error will be thrown.
*/
addDependency:function (from, to) {
if (!this.hasNode(from)) {
throw new Error('Node does not exist: ' + from);
}
if (!this.hasNode(to)) {
throw new Error('Node does not exist: ' + to);
}
if (this.outgoingEdges[from].indexOf(to) === -1) {
this.outgoingEdges[from].push(to);
}
if (this.incomingEdges[to].indexOf(from) === -1) {
this.incomingEdges[to].push(from);
}
return true;
},
/**
* Remove a dependency between two nodes.
*/
removeDependency:function (from, to) {
var idx;
if (this.hasNode(from)) {
idx = this.outgoingEdges[from].indexOf(to);
if (idx >= 0) {
this.outgoingEdges[from].splice(idx, 1);
}
}
if (this.hasNode(to)) {
idx = this.incomingEdges[to].indexOf(from);
if (idx >= 0) {
this.incomingEdges[to].splice(idx, 1);
}
}
},
/**
* Return a clone of the dependency graph. If any custom data is attached
* to the nodes, it will only be shallow copied.
*/
clone:function () {
var source = this;
var result = new DepGraph();
var keys = Object.keys(source.nodes);
keys.forEach(function (n) {
result.nodes[n] = source.nodes[n];
result.outgoingEdges[n] = source.outgoingEdges[n].slice(0);
result.incomingEdges[n] = source.incomingEdges[n].slice(0);
});
return result;
},
/**
* Get an array containing the nodes that the specified node depends on (transitively).
*
* Throws an Error if the graph has a cycle, or the specified node does not exist.
*
* If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned
* in the array.
*/
dependenciesOf:function (node, leavesOnly) {
if (this.hasNode(node)) {
var result = [];
var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular);
DFS(node);
var idx = result.indexOf(node);
if (idx >= 0) {
result.splice(idx, 1);
}
return result;
}
else {
throw new Error('Node does not exist: ' + node);
}
},
/**
* get an array containing the nodes that depend on the specified node (transitively).
*
* Throws an Error if the graph has a cycle, or the specified node does not exist.
*
* If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array.
*/
dependantsOf:function (node, leavesOnly) {
if (this.hasNode(node)) {
var result = [];
var DFS = createDFS(this.incomingEdges, leavesOnly, result, this.circular);
DFS(node);
var idx = result.indexOf(node);
if (idx >= 0) {
result.splice(idx, 1);
}
return result;
} else {
throw new Error('Node does not exist: ' + node);
}
},
/**
* Construct the overall processing order for the dependency graph.
*
* Throws an Error if the graph has a cycle.
*
* If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned.
*/
overallOrder:function (leavesOnly) {
var self = this;
var result = [];
var keys = Object.keys(this.nodes);
if (keys.length === 0) {
return result; // Empty graph
} else {
// Look for cycles - we run the DFS starting at all the nodes in case there
// are several disconnected subgraphs inside this dependency graph.
var CycleDFS = createDFS(this.outgoingEdges, false, [], this.circular);
keys.forEach(function(n) {
CycleDFS(n);
});
var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular);
// Find all potential starting points (nodes with nothing depending on them) an
// run a DFS starting at these points to get the order
keys.filter(function (node) {
return self.incomingEdges[node].length === 0;
}).forEach(function (n) {
DFS(n);
});
return result;
}
}
};
|
