Find path between nodes in flat array

Question

I Have a flat array of connections which represent the connection of nodes in a tree.

const connections = [
  {
    id: "first",
    source: "root",
    target: "A_fbb03",
  },
  {
    source: "A_fbb03",
    target: "W_c0f6f",
    id: "A_fbb03_W_c0f6f",
  },
  {
    source: "A_fbb03",
    target: "W_4c2dd",
    id: "A_fbb03_W_4c2dd",
  },
  {
    id: "A_fbb03_W_1f0ac",
    source: "A_fbb03",
    target: "W_1f0ac",
  },
  {
    id: "W_c0f6f_S_007f5",
    source: "W_c0f6f",
    target: "S_007f5",
  },
];

When adding a new connection between nodes, I want to check if this connection creating a loop, meaning that the target node has a path to the source node.

I came up with a function:

function isLoopConnection = (newConnection, connections) => {
  const theSource = newConnection.source
  let theTarget = newConnection.target
  let isLoop = false

 
  for (let i = 0; i < connections.length; i++) {
    const nextConnection = connections.filter(item => item.source === theTarget)
    if (nextConnection.length) {
      for (const nc of nextConnection) {
        if (nc.target === theSource) {
          isLoop = true
          break
        } else {
          theTarget = nc.target
        }
      }
    }
  }
  return isLoop
}

Obviously this is not working well in certain cases and feels way too complicated. For example: when I add a new connection which suppose to create a loop between S_007f5 to A_fbb03 because A_fbb03 has a path to S_007f5 through W_c0f6f

A_fbb03 -> W_c0f6f -> S_007f5 -> A_fbb03

{
  id: "S_007f5_A_fbb03",
  source: "S_007f5",
  target: "A_fbb03",
}

The function return false

Any suggestions how to improve this solution?

user_1447675 · Answer

You could take a Set and store seen node identifier.

This approach generates an object whit all children of all nodes. To get result, all items are used to check for circular references.

const
    hasLoop = array => {
        const
           children = array.reduce((r, { source, target }) => ((r[source] ??= []).push(target), r), {}),
           check = (node, seen = new Set) => {
               if (seen.has(node)) return true;
               seen.add(node);
               return (children[node] || []).some(node => check(node, seen));
           };

        return array.some(({ source }) => check(source));
    },
    connections = [{ source: "root", target: "A_fbb03" }, { source: "A_fbb03", target: "W_c0f6f" }, { source: "A_fbb03", target: "W_4c2dd" }, { source: "A_fbb03", target: "W_1f0ac" }, { source: "W_c0f6f", target: "S_007f5" }, { source: "S_007f5", target: "A_fbb03" }];


console.log(hasLoop(connections.slice(0, -1))); // false
console.log(hasLoop(connections));              //  true

Find path between nodes in flat array

1 Answers