JavaScript: Detect a Loop in a Hierarchical Graph

Note that I’ve already gone through How to detect a loop in a hierarchy of javascript elements In our case, we’re not dealing with a linked-list, but a hierarchical graph where each node may have multiple children linked to it. For example,

const graph = {
   a: {value: Va, children: {b, d}},
   b: {value: Vb, children: {c}},
   c: {value: Vc, children: {a, d, e}}
}

In this graph, we should detect the loop a -> b -> c -> a.

Answer

If you only need to determine whether a graph has a cycle, and don’t need to report what the cycle is, you can do this for a particular node of the graph with a simple recursion and wrap that in a call that tests all nodes.

Here’s one implementation:

const hasCycle = (graph, name, path = []) =>
  path .includes (name)
    ? true
   : (graph?.[name]?.children ?? []) .some (c => hasCycle (graph, c, [...path, name]))

const anyCycles = (graph) =>
  Object .keys (graph) .some (k => hasCycle (graph, k))

const graph1 = {a: {value: 1, children: ['b', 'd']}, b: {value: 2, children: ['c']}, c: {value: 3, children: ['a', 'd', 'e']}}
const graph2 = {a: {value: 1, children: ['b', 'd']}, b: {value: 2, children: ['c']}, c: {value: 3, children: ['d', 'e']}}

console .log (anyCycles (graph1))
console .log (anyCycles (graph2))