How do I find all possible paths between a simple structure?

Question

I have a structure like this:

[
  {index: 1, children: [2]},
  {index: 2, children: [3, 4]}
  {index: 3, children: [4]}
  {index: 4, children: []}
]

and I wanna find all possible paths in this structure so I eventually get the longest one (I need to decide the max length of the whole trip). So in this structure the algorithm should export something like

[[1, 2, 3, 4], [1, 2, 4]]

or just the final answer which is 4 (the length of the longest trip). I found a few solutions online, at this point I am sure that this is only solvable with recursion but just can't figure it out. Any ideas of implementing this would be awesome, I am trying to solve this with js.

Its very easy, Find a starting point, in this case its index 1; then check if it has any `children`, if it doesn't then this is the final node!, Otherwise look for each `children`, and continue looking... Example: [Get possible question answer paths](https://stackoverflow.com/a/68038624/12750399) — Nur, Aug 30 '21 at 19:22

Nur · Accepted Answer · 2021-08-31T10:56:59.570

1

let input = [{ index: 1, children: [2] }, { index: 2, children: [3, 4] }, { index: 3, children: [4] }, { index: 4, children: [] }];

function find_all_possible_paths(nodes, key) {
  let result = [];
  function next(key, paths = [key]) {
    let node = nodes.find(v => v.index == key);

    if (node?.children.length)
      for (let index of node.children) {
        if (paths.includes(index)) throw new Error("Reference cycle error:\n" + JSON.stringify({ paths, node }, null, 4));
        next(index, paths.concat(index))
      }
    else result.push(paths)
  }
  next(key);
  return result
}

console.log(find_all_possible_paths(input, 1))

edited Aug 31 '21 at 10:56

answered Aug 30 '21 at 19:37

Nur

2,361
2
16
34

Works awesome, thank you! Although browser give me a"Maximum call stack size exceeded" for arrays over the length of 10, which is the case. Any workarounds? – iNSIDE the mirror Aug 31 '21 at 08:14
I meant children arrays. – iNSIDE the mirror Aug 31 '21 at 08:24
1

_"Maximum call stack size exceeded"_ would only possible if, children refer cycle itself, In this case you should add `deep` counter and cycle `limit`, Each time when recursion, Increase `deep` counter by one and check if `limit` are equal to `deep` counter, If it does then break the loop. – Nur Aug 31 '21 at 10:11
1

When you found any reference cycle, you should not continue process farther, when you in count any bad state, its meaningful to throw an error, So a quick fix is, Add this line: `if (paths.includes(index)) throw new Error("Reference cycle error:\n" + JSON.stringify({ paths, node }, null, 4))`, I also added this line, In the answer – Nur Aug 31 '21 at 10:53
Worked!I really appreciate the time you've put into this. You're badass! – iNSIDE the mirror Sep 01 '21 at 11:45

How do I find all possible paths between a simple structure?

1 Answers1