1
/**
2
 * This source code is from https://github.com/jriecken/dependency-graph
3
 * Just added "any" types here, wrapper everything into exported class.
4
 * We cant use a package itself because we want to package "everything-in-it" for the frontend users of TypeORM.
5
 */
6

7
/**
8
 * A simple dependency graph
9
 */
10

11
/**
12
 * Helper for creating a Depth-First-Search on
13
 * a set of edges.
14
 *
15
 * Detects cycles and throws an Error if one is detected.
16
 *
17
 * @param edges The set of edges to DFS through
18
 * @param leavesOnly Whether to only return "leaf" nodes (ones who have no edges)
19
 * @param result An array in which the results will be populated
20
 */
21 10
function createDFS(edges: any, leavesOnly: any, result: any) {
22 10
    let currentPath: any[] = [];
23 10
    let visited: any = {};
24 10
    return function DFS(currentNode: any) {
25 10
        visited[currentNode] = true;
26 10
        currentPath.push(currentNode);
27 10
        edges[currentNode].forEach(function (node: any) {
28 10
            if (!visited[node]) {
29 10
                DFS(node);
30 10
            } else if (currentPath.indexOf(node) >= 0) {
31 10
                currentPath.push(node);
32 10
                throw new Error(`Dependency Cycle Found: ${currentPath.join(" -> ")}`);
33
            }
34
        });
35 10
        currentPath.pop();
36 10
        if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) {
37 10
            result.push(currentNode);
38
        }
39
    };
40
}
41

42

43 10
export class DepGraph {
44 10
    nodes: any = {};
45 10
    outgoingEdges: any = {}; // Node -> [Dependency Node]
46 10
    incomingEdges: any = {}; // Node -> [Dependant Node]
47

48
    /**
49
     * Add a node to the dependency graph. If a node already exists, this method will do nothing.
50
     */
51 10
    addNode(node: any, data?: any) {
52 10
        if (!this.hasNode(node)) {
53
            // Checking the arguments length allows the user to add a node with undefined data
54 10
            if (arguments.length === 2) {
55 0
                this.nodes[node] = data;
56
            } else {
57 10
                this.nodes[node] = node;
58
            }
59 10
            this.outgoingEdges[node] = [];
60 10
            this.incomingEdges[node] = [];
61
        }
62
    }
63

64
    /**
65
     * Remove a node from the dependency graph. If a node does not exist, this method will do nothing.
66
     */
67 10
    removeNode(node: any) {
68 0
        if (this.hasNode(node)) {
69 0
            delete this.nodes[node];
70 0
            delete this.outgoingEdges[node];
71 0
            delete this.incomingEdges[node];
72 0
            [this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) {
73 0
                Object.keys(edgeList).forEach(function (key: any) {
74 0
                    let idx = edgeList[key].indexOf(node);
75 0
                    if (idx >= 0) {
76 0
                        edgeList[key].splice(idx, 1);
77
                    }
78
                }, this);
79
            });
80
        }
81
    }
82

83
    /**
84
     * Check if a node exists in the graph
85
     */
86 10
    hasNode(node: any) {
87 10
        return this.nodes.hasOwnProperty(node);
88
    }
89

90
    /**
91
     * Get the data associated with a node name
92
     */
93 10
    getNodeData(node: any) {
94 0
        if (this.hasNode(node)) {
95 0
            return this.nodes[node];
96
        } else {
97 0
            throw new Error(`Node does not exist: ${node}`);
98
        }
99
    }
100

101
    /**
102
     * Set the associated data for a given node name. If the node does not exist, this method will throw an error
103
     */
104 10
    setNodeData(node: any, data: any) {
105 0
        if (this.hasNode(node)) {
106 0
            this.nodes[node] = data;
107
        } else {
108 0
            throw new Error(`Node does not exist: ${node}`);
109
        }
110
    }
111

112
    /**
113
     * Add a dependency between two nodes. If either of the nodes does not exist,
114
     * an Error will be thrown.
115
     */
116 10
    addDependency(from: any, to: any) {
117 10
        if (!this.hasNode(from)) {
118 0
            throw new Error(`Node does not exist: ${from}`);
119
        }
120 10
        if (!this.hasNode(to)) {
121 0
            throw new Error(`Node does not exist: ${to}`);
122
        }
123 10
        if (this.outgoingEdges[from].indexOf(to) === -1) {
124 10
            this.outgoingEdges[from].push(to);
125
        }
126 10
        if (this.incomingEdges[to].indexOf(from) === -1) {
127 10
            this.incomingEdges[to].push(from);
128
        }
129 10
        return true;
130
    }
131

132
    /**
133
     * Remove a dependency between two nodes.
134
     */
135 10
    removeDependency(from: any, to: any) {
136
        let idx: any;
137 0
        if (this.hasNode(from)) {
138 0
            idx = this.outgoingEdges[from].indexOf(to);
139 0
            if (idx >= 0) {
140 0
                this.outgoingEdges[from].splice(idx, 1);
141
            }
142
        }
143

144 0
        if (this.hasNode(to)) {
145 0
            idx = this.incomingEdges[to].indexOf(from);
146 0
            if (idx >= 0) {
147 0
                this.incomingEdges[to].splice(idx, 1);
148
            }
149
        }
150
    }
151

152
    /**
153
     * Get an array containing the nodes that the specified node depends on (transitively).
154
     *
155
     * Throws an Error if the graph has a cycle, or the specified node does not exist.
156
     *
157
     * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned
158
     * in the array.
159
     */
160 10
    dependenciesOf(node: any, leavesOnly: any) {
161 0
        if (this.hasNode(node)) {
162 0
            let result: any[] = [];
163 0
            let DFS = createDFS(this.outgoingEdges, leavesOnly, result);
164 0
            DFS(node);
165 0
            let idx = result.indexOf(node);
166 0
            if (idx >= 0) {
167 0
                result.splice(idx, 1);
168
            }
169 0
            return result;
170
        }
171
        else {
172 0
            throw new Error(`Node does not exist: ${node}`);
173
        }
174
    }
175

176
    /**
177
     * get an array containing the nodes that depend on the specified node (transitively).
178
     *
179
     * Throws an Error if the graph has a cycle, or the specified node does not exist.
180
     *
181
     * If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array.
182
     */
183 10
    dependantsOf(node: any, leavesOnly: any) {
184 0
        if (this.hasNode(node)) {
185 0
            let result: any[] = [];
186 0
            let DFS = createDFS(this.incomingEdges, leavesOnly, result);
187 0
            DFS(node);
188 0
            let idx = result.indexOf(node);
189 0
            if (idx >= 0) {
190 0
                result.splice(idx, 1);
191
            }
192 0
            return result;
193
        } else {
194 0
            throw new Error(`Node does not exist: ${node}`);
195
        }
196
    }
197

198
    /**
199
     * Construct the overall processing order for the dependency graph.
200
     *
201
     * Throws an Error if the graph has a cycle.
202
     *
203
     * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned.
204
     */
205 10
    overallOrder(leavesOnly?: any) {
206 10
        let self = this;
207 10
        let result: any[] = [];
208 10
        let keys = Object.keys(this.nodes);
209 10
        if (keys.length === 0) {
210 10
            return result; // Empty graph
211
        } else {
212
            // Look for cycles - we run the DFS starting at all the nodes in case there
213
            // are several disconnected subgraphs inside this dependency graph.
214 10
            let CycleDFS = createDFS(this.outgoingEdges, false, []);
215 10
            keys.forEach(function (n: any) {
216 10
                CycleDFS(n);
217
            });
218

219 10
            let DFS = createDFS(this.outgoingEdges, leavesOnly, result);
220
            // Find all potential starting points (nodes with nothing depending on them) an
221
            // run a DFS starting at these points to get the order
222 10
            keys.filter(function (node) {
223 10
                return self.incomingEdges[node].length === 0;
224 10
            }).forEach(function (n) {
225 10
                DFS(n);
226
            });
227

228 10
            return result;
229
        }
230
    }
231

232 10
}

Read our documentation on viewing source code .

Loading