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?
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