Javascript: build possible paths through an object tree

Question

I have an object: {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]} which I would like to loop/traverse through.

• Each key of this object is like a point or location (eg location 1 or location 2).
• And each location is linked to one or two other locations, allowing you to jump from one to the next. These "links" are defined by the array-property of each key. For example, I can jump from location 1 to location 2, or from location 3 to location 8.

Now I would like to map out these links in the form of a 2D array. The 2D array should contain all possible paths, with each path starting with location 1 and ending with location End (defined only in the array of key 8).


I have the following code so far:

let paths_list;
function find_paths(obk, data={}) {
    paths_list = data?.paths_list || [];
    let newest_path = data?.newest_path || [1];
    let current_number = data?.current_number || 1;
    let next_possible_numbers_iteration = (data.next_possible_numbers_iteration || 0);

    if((current_number == "End" || current_number == undefined) && next_possible_numbers_iteration >= obk[1].length) {
        return paths_list;
    }

    let next_possible_numbers;
    let next_number;

    for(let i = 0; i < 2; i++) {
        if(current_number == "End" || current_number == undefined) {
            next_possible_numbers_iteration++;
            current_number = 1;
            paths_list.push(newest_path);
            newest_path = [1];
        }
        next_possible_numbers = obk[current_number]; // [2,2]
        next_number = next_possible_numbers[next_possible_numbers_iteration];
        newest_path.push(next_number);
        current_number = next_number;
    }
    

    if(current_number != "End" && current_number != undefined) {
        find_paths(obk, {
            paths_list,
            newest_path,
            current_number,
            next_possible_numbers_iteration
        });
    } else {
        next_possible_numbers_iteration++;
        paths_list.push(newest_path);
        find_paths(obk, {
            paths_list,
            current_number,
            next_possible_numbers_iteration
        });
    }
}


let my_obk = {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]};
find_paths(my_obk);
console.log(paths_list);

Problem

But there is a slight problem: The function returns only some of the possible paths. Specifically, it returns these correctly:

• 1,2,3,4,8,End
• 1,3,8,End

But does not return other paths such as:

• 1,2,3,8,End

This is because the function only searches in the same position in each array-property and does not fluctutate the position at which it searches (defiend by next_possible_numbers_iteration).

In short, my question is how would I make the func look at different positions in each array (or property) instead of just one in all arrays. This probably does not make sense when you read it, but if you look at how the variable next_possible_numbers_iteration is used, you'll see what I mean. Feel free to change my function if it is hopeless.

Answer 1

You could take a recursive approach and collect all pathes from the given node.

This approach takes only unique targets the in the arrays.

---

A recursive function contains usually an exit condition where the function decides to call the function again or just leave the function with a value. This happens here, too.

If a node is found which is the target, it returns a nested array with a single value, the target node.

To understand the algorithm, take a simple three node object, like

{ 1: [2, 3], 2: ['End'], 3: ['End'] }

where the final result would be two pathes:

[
    [1, 2, 'End'],
    [1, 3, 'End']
]

The algorithm works with a breadth-first search, because of the recursion and finding the end.

That means it returns for the final call of getPathes('End', 'End')

[['End']]

and for the previous call of getPathes(2, 'End') it returns

[[2, 'End']]

analog for getPathes(3, 'End') it returns

[[3, 'End']]

Both arrays are returned inside of the call of getPathes(1, 'End'), where the actual node is prepended to all arrays of the nested call.

const 
    getPathes = (from, to) => {
        if (from === to) return [[to]];
        return nodes[from].flatMap(n => getPathes(n, to).map(p => [from, ...p]));
    },
    nodes = { 1: [2, 3], 2: [3], 3: [4, 8], 4: [8], 8: ["End"] },
    pathes = getPathes(1, 'End');

pathes.forEach(p => console.log(...p));

Answer 2

The recursive solution by @Nina looks great

If you want a iterative way of solving the same you can check this

Keep on creating new paths until all paths end : )

const obj = { 1: [2, 3], 2: [3, 3], 3: [4, 8], 4: [8, 8], 8: ['End', 'End'] };

let paths = obj[1].map((x) => [1, x]);
let complete = false;

while (!complete) {
  complete = true;
  
  const result = [];
  paths.forEach((path) => {
    const lastElementOfPath = path[path.length - 1];
    const nextPathDirections = obj[lastElementOfPath];
    if (nextPathDirections) {
      Array.from(new Set(nextPathDirections)).forEach((nextPathElement) => {
        result.push([...path, nextPathElement]);
        if (nextPathElement !== 'End' && !!obj[nextPathElement]) {
          complete = false;
        }
      });
    } else {
      result.push([...path]);
    }
  });
  
  paths = result;
}


// Paths will be your desired result
paths.forEach(path => console.log(...path))