I asked recently about topological sorting in JavaScript, and now am wondering, along the same lines, how to handle cycles. Here is a theoretical collection of dependent modules, some of which involve a somewhat complex cycle.
There are two small cycles, D-E-F and D-E-F-G. Everything else is just a directed acyclic graph (DAG).
What I'd like to do is, imagine the following. These are all modules, dependent on each other as the diagram shows. The cycle becomes basically a single node, to simplify the graph back down to a DAG. Since the two cycles can be encapsulated in D-E-F-G, it seems we can just call that X. Then we have something like this I think.
From that, we can we can consider that X will be a super-module which wraps the 4 modules D, E, F, and G. And then we do a topological sort on this graph, to get the order...
[ A, B, C, X, H, K, M, N, I, J, L, O ]
This is the order in which the "modules" would be loaded. The X super-module would wire up the cyclic dependencies.
How could you convert the first cycle-containing graph into the second DAG? Something like this:
[ A, B, C, [ D, E, F, G ], H, K, M, N, I, J, L, O ]
The topsort JS snippet I am working with is:
const graph = {
edges: {
A: ['B', 'C'],
B: ['X'],
C: ['X'],
X: ['H', 'J', 'L', 'K', 'M', 'N'],
H: ['I', 'J'],
K: ['L'],
M: ['O'],
N: ['O'],
}
}
// Calcuate the incoming degree of each vertex
const vertices = Object.keys(graph.edges)
const inDegree = {}
for (const v of vertices) {
const neighbors = graph.edges[v]
neighbors?.forEach(neighbor => {
inDegree[neighbor] = inDegree[neighbor] + 1 || 1
})
}
const queue = vertices.filter((v) => !inDegree[v])
const list = []
while (queue.length) {
const v = queue.shift()
const neighbors = graph.edges[v]
list.push(v)
// adjust the incoming degree of its neighbors
neighbors?.forEach(neighbor => {
inDegree[neighbor]--
if (inDegree[neighbor] === 0) {
queue.push(neighbor)
}
})
}
console.log(list)If it's too complex to implement cycle detection in JavaScript, what research must I look into to figure this out? What algorithms are key to solving this problem? If it is possible to show, what is a basic implementation to give the desired output? I know "cycle detection" is a tough problem, but not sure how feasible this is, if it can be done. How would you break this problem down, into what steps?
To make it even more complex! I added this extended example with nested cycles! Not sure if it would even be possible to figure that out. This question could only handle the simple case for the time being, unless it is somehow obvious to you the full solution (it's quite complex to me).
