Tengo una matriz plana de conexiones que representan la conexión de los nodos en un árbol.
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", }, ];Al agregar una nueva conexión entre nodos, quiero verificar si esta conexión crea un bucle, lo que significa que el nodo de destino tiene una ruta al nodo de origen.
Se me ocurrió una función:
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 } Obviamente, esto no funciona bien en ciertos casos y se siente demasiado complicado. Por ejemplo: cuando agrego una nueva conexión que supone crear un bucle entre S_007f5 y A_fbb03 porque A_fbb03 tiene una ruta a S_007f5 a través de W_c0f6f
A_fbb03 -> W_c0f6f -> S_007f5 -> A_fbb03 { id: "S_007f5_A_fbb03", source: "S_007f5", target: "A_fbb03", } La función devuelve false
¿Alguna sugerencia sobre cómo mejorar esta solución?
Puede tomar un Set y almacenar el identificador de nodo visto.
Este enfoque genera un objeto con todos los hijos de todos los nodos. Para obtener resultados, todos los elementos se utilizan para verificar las referencias circulares.
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