在有向图中检测循环

Question

最近不得不在代码逻辑中检测有向图中的递归。我的 nodejs 实现感觉很复杂，我现在想知道：

代码有问题吗？
我们可以简化它/使其更具可读性吗？

const checkCyclic = (graph) => {
  const nodes = new Set(Object.keys(graph));
  const searchCycle = (trace, node) => {
    const cycleStartIdx = trace.indexOf(node);
    if (cycleStartIdx !== -1) {
      throw new Error(`Cycle detected: ${trace
        .slice(cycleStartIdx).concat(node).join(' <- ')}`);
    }
    if (nodes.delete(node) === true) {
      const nextTrace = trace.concat(node);
      graph[node].forEach((nextNode) => searchCycle(nextTrace, nextNode));
    }
  };
  while (nodes.size !== 0) {
    searchCycle([], nodes.values().next().value);
  }
};

checkCyclic({
  p1: ['p3'],
  p2: ['p1'],
  p3: ['p2']
});
// => Recursion detected: p1 <- p3 <- p2 <- p1

checkCyclic({
  p0: ['p1'],
  p1: ['p3'],
  p2: ['p1'],
  p3: ['p2']
});
// => Recursion detected: p1 <- p3 <- p2 <- p1

checkCyclic({
  p0: ['p0']
});
// => Cycle detected: p0 <- p0

出于好奇，这在 promise-pool-ext 中使用，其中还包含测试。

非常感谢您的反馈！

编辑： 试玩并迭代实现（看起来更丑！）

module.exports = (G) => {
  const pending = new Set(Object.keys(G));
  while (pending.size !== 0) {
    const trace = [pending.values().next().value];
    const parentIdx = [0];
    pending.delete(trace[0]);

    while (trace.length !== 0) {
      const c = trace.length - 1;
      const parent = G[trace[c]][parentIdx[c]];
      if (parent !== undefined) {
        if (trace.includes(parent)) {
          throw new Error(`Cycle detected: ${trace
            .slice(trace.indexOf(parent)).concat(parent).join(' <- ')}`);
        }

        parentIdx[c] += 1;
        if (pending.delete(parent)) {
          trace.push(parent);
          parentIdx.push(0);
        }
      } else {
        trace.pop();
        parentIdx.pop();
      }
    }
  }
};

我通常更喜欢迭代而不是递归，但在这种情况下，它可能不值得以可读性为代价。知道如何改进此实现吗？

Answer 1

我们可能会缩短一点：

function getCycle (G, n, path) {
  if (path.includes(n)) {
    throw `cycle ${path.slice(path.indexOf(n)).concat(n).join('<-')}`
  }
  path.push(n)
  return G[n].forEach(next => getCycle(G, next, path.slice(0)))
}
function validate (G) {
  Object.keys(G).forEach(n => getCycle(G, n, []))
}
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:[]
})
console.log('ok')
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:['p1']
})

现在这不是最有效的，因为我们：

找到一个数组而不是集合的路径（同上 O(k) 而不是 O(1)）
重新访问顶点，即使它们已经被访问过

为了可读性，下面是稍微优化的版本？

function getCycle (G, n, path, visited) {
  if (path.has(n)) {
    const v = [...path]
    throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
  }
  visited.add(n)
  path.add(n)
  return G[n].forEach(next => getCycle(G, next, new Set(path), visited))
}
function validate (G) {
  const visited = new Set()
  Object.keys(G).forEach(n => {
    if (visited.has(n)) return
    getCycle(G, n, new Set(), visited)
  })
}


validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:[]
})
console.log('ok')
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:['p1']
})

关于性能，我已经（廉价地）尝试在具有 50 个节点的同一图 G（由随机 dag 生成）上复制和比较算法。

它们似乎是等价的。

function checkCyclic (G) {
  const pending = new Set(Object.keys(G));
  while (pending.size !== 0) {
    const trace = [pending.values().next().value];
    const parentIdx = [0];
    pending.delete(trace[0]);

    while (trace.length !== 0) {
      const lastIdx = trace.length - 1;
      const parent = G[trace[lastIdx]][parentIdx[lastIdx]];
      if (parent === undefined) {
        trace.pop();
        parentIdx.pop();
      } else {
        if (trace.includes(parent)) {
          throw new Error(`cycle ${trace
            .slice(trace.indexOf(parent)).concat(parent).join('<-')}`);
        }
        parentIdx[lastIdx] += 1;
        if (pending.delete(parent)) {
          trace.push(parent);
          parentIdx.push(0);
        }
      }
    }
  }
};

function grodzi1(G) {
  function getCycle (G, n, path) {
    if (path.includes(n)) {
      throw `cycle ${path.slice(path.indexOf(n)).concat(n).join('<-')}`
    }
    path.push(n)
    return G[n].forEach(next => getCycle(G, next, path.slice(0)))
  }
  Object.keys(G).forEach(n => getCycle(G, n, []))
}
function grodzi2(G) {
  function getCycle (G, n, path, visited) {
    if (path.has(n)) {
      const v = [...path]
      throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
    }
    visited.add(n)
    path.add(n)
    return G[n].forEach(next => getCycle(G, next, new Set(path), visited))
  }
  const visited = new Set()
  Object.keys(G).forEach(n => {
    if (visited.has(n)) return
    getCycle(G, n, new Set(), visited)
  })
}

// avoid copying the set
function grodziNoCopy(G) {
  function getCycle (G, n, path, visited) {
    if (path.has(n)) {
      const v = [...path]
      throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
    }
    visited.add(n)
    path.add(n)
    return G[n].forEach(next => {
      getCycle(G, next, path, visited)
      path.delete(next)
    })
  }
  const visited = new Set()
  Object.keys(G).forEach(n => {
    if (visited.has(n)) return
    getCycle(G, n, new Set(), visited)
  })
}

// avoid visiting the already visited set of nodes
function grodziStopVisit(G) {
  function getCycle (G, n, path, visited) {
    if (path.has(n)) {
      const v = [...path]
      throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
    }
    if (visited.has(n)) return
    visited.add(n)
    path.add(n)
    return G[n].forEach(next => {
      getCycle(G, next, path, visited)
      path.delete(next)
    })
  }
  const visited = new Set()
  Object.keys(G).forEach(n => {
    if (visited.has(n)) return
    getCycle(G, n, new Set(), visited)
  })
}

// same but iterative
function grodziIter(G) {
  function dfs (G, n, visited) {
    let stack = [{ path: [], n }]
    let x
    while (x = stack.pop()) {
      const {n, path} = x
      if (path.includes(n)) {
        const v = [...path]
        throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
      }
      if (visited.has(n)) continue
      visited.add(n)
      path.push(n)
      G[n].forEach(next => stack.push({ path: path.slice(0), n: next }))
    }
  }
  const visited = new Set()
  Object.keys(G).forEach(n => visited.has(n) || dfs(G, n, visited))
}

const G = {"0":["5","6","12","15","18","30","31","32","33","35","39","41","52","54"],"1":["12","17","29","30","34","35","38","39","40","43","53"],"2":["5","7","12","13","14","15","16","19","21","31","35","36","37","40","41","53"],"3":["14","16","15","30","32","40","52","55"],"4":["5","6","13","15","17","18","32","35","40","41","42","51"],"5":["16","15","30","33","52","53","55"],"6":["11","16","18","33","36","37","42","51","53"],"7":["14","15","16","22","30","33","35","36","39","41","43","49","53","54","55"],"8":["31","36","41","51"],"9":["18","30","36","37","39","40","50","52"],"10":["15","17","18","19","31","32","33","35","37","40","41","48","54","55"],"11":["15","17","19","31","32","35","38","41","40","43","48","52"],"12":["17","21","32","33","35","52","54","55"],"13":["18","19","20","29","33","35","36","38","41","43","52"],"14":["16","17","19","35","39","55"],"15":["20","22","30","33","35","38","39","41","42","43","49","50","54"],"16":["20","32","34","36","37","39","40","42","44","53"],"17":["28","31","36","35","38","41","43","44","48"],"18":["19","31","34","36","35","38","41","49","52","53","55"],"19":["29","36","48","51"],"20":["29","32","33","36","37","49"],"21":["30","31","33","34","35","36","39","48"],"22":["30","31","32","34","36","37","41","43","48"],"23":["33","34","35","36","37","40","44","50"],"24":["28","34","35","36","38","41","42","48","52"],"25":["28","29","31","32","36","41","43","53"],"26":["29","35","37","38","39","41","43","50"],"27":["31","35","36","37","41","42","48","51","53"],"28":["35","37","38","40","41","50","55"],"29":["38","39","40","42","44","51","54"],"30":["37","38","40","41","42","43","49","50","53"],"31":["36","39","40","50","52","54"],"32":["37","38","39","41","44","48","49","52","55"],"33":["41","40","42","44","52","53"],"34":["35","36","41","42","49","52","54"],"35":["44","55"],"36":["41","50","52","53","54"],"37":["52","55"],"38":["55"],"39":["40","41","51"],"40":["48","49","52"],"41":["49","52","53"],"42":["53"],"43":["48","50","52","55"],"44":["48","52","54"],"45":["49","53","54"],"46":["49","50","52"],"47":["48","50","52","53","55"],"48":[],"49":[],"50":[],"51":[],"52":[],"53":[],"54":[],"55":[]}
function bench (fn, label) {
  console.time(label)
  for (let idx = 0; idx < 50; idx += 1) { fn(G) }
  console.timeEnd(label)
}
function shouldThrow (...fns) {
  const cyc = {"p1":["p2","p3","p4"],"p2":["p3"],"p3":["p0"],"p0":[],"p4":["p1"]}
  fns.forEach(fn => {
    let ok = false
    try { fn(cyc) } catch (e) {
      ok = e.toString().includes('cycle p1<-p4<-p1')
      if(!ok){
        throw new Error('failzed ', e)
      }
    }
    if (!ok){ throw 'should have thrown' }
  })
}
shouldThrow(checkCyclic, grodzi1, grodzi2, grodziNoCopy, grodziStopVisit, grodziIter)

for(let i = 0; i < 3; ++i) {
  bench(checkCyclic, 'cyclic')
  bench(grodzi1, 'grodzi1')
  bench(grodzi2, 'grodzi2')
  bench(grodziNoCopy, 'grodziNoCopy')
  bench(grodziStopVisit, 'grodziStopVisit')
  bench(grodziIter, 'grodziIter')
  console.log('next')
}

在有向图中检测循环

Detect cycle in directed Graph

algorithm

directed-graph

node.js

directed-acyclic-graphs