在有向和无向图中找到所有固定长度为L的简单环。

Question

我是一位有用的助手，可以为您翻译文本。

我正在寻找一个算法，可以在有向和无向图中返回所有固定长度L的简单循环。

在我的研究中，我遇到了类似的问题，例如：

https://dev59.com/PXRB5IYBdhLWcg3wtJGF https://dev59.com/D3VC5IYBdhLWcg3wixs0

这些答案建议在有向图中使用Johnson算法。然而，在无向图中找到所有长度为L的环，尤其是在有向和无向图中找到循环，我没有找到任何清晰的内容。

我的问题源于需要逐步找到循环，以便对于大型图形，我可以及早停止而不会消耗过多时间。

- oneWayC

Answer 1

我会运行通常的循环查找算法，并添加一个筛选器，只通过所需长度的循环。

循环查找算法：

 - Run Depth First Search modified 
       to check for back edge ( Dijkstra )
       whenever a previously visited node is popped from the stack

这是我的C++代码实现：

    /// @brief Depth first search, finding cycles in directed graph
    /// @param start name of start vertex
    /// @return vector of vectors, each with the vertices in a cycle

std::vector<std::vector<vertex_t>>
cGraph::dfs_cycle_finder(const std::string &start)
{
    std::vector<std::vector<vertex_t>> ret;

    // track visited vertices
    std::vector<bool> visited(vVertexName.size(), false);

    // vertices waiting to be processed
    std::stack<vertex_t> wait;

    // start at the beginning
    wait.push(index(start));

    // continue until no more vertices need processing
    while (!wait.empty())
    {
        vertex_t v = wait.top();
        wait.pop();
        int vi = v;
        if (!visited[vi])
        {
            visited[vi] = true;

            for (vertex_t w : adjacentOut(v))
            {
                if (!visited[w])
                {
                    wait.push(w);
                }
                else
                {
                    // previously visited node, check for ancestor
                    auto cycle = path(w, v);
                    if (cycle.size() > 0)
                    {
                        // found a cycle
                        cycle.push_back(w);
                        ret.push_back(cycle);
                    }
                }
            }
        }
    }
    return ret;
}

完整应用程序的代码在https://github.com/JamesBremner/graphCycler上。

该应用程序可以在几秒钟内处理成千上万条边的图。（这里有一份关于我的C ++ DFS代码在300万链接图上性能的详细讨论https://github.com/JamesBremner/PathFinder3/wiki/Performance）

（我很乐意根据您的特定要求修改此应用程序，并收取少量费用。）

- ravenspoint

Answer 2

如果你有生成器（或协程，或续延），那么这可以通过递归简单地实现。在Python中：

def find_cycles_recursive(graph, L, cycle):
    successors = graph[cycle[-1]]
    if len(cycle) == L:
        if cycle[0] in successors:
            yield cycle
    elif len(cycle) < L:
        for v in successors:
            if v in cycle:
                continue
            yield from find_cycles_recursive(graph, L, cycle + [v])


def find_cycles(graph, L):
    for v in graph:
        yield from find_cycles_recursive(graph, L, [v])


print(list(find_cycles({0: {1, 2}, 1: {0, 2, 3}, 2: {0, 1, 3}, 3: {1, 2}}, 3)))

您可以通过将条件中的 v in cycle 更改为 v <= cycle[0] or v in cycle 来进行优化。对于无向图，您还可以在结尾处过滤掉 cycle[1] > cycle[-1] 的图形。

如果您正在使用控制流程简陋的语言，则需要使用数据结构来模拟缺失的控制流程。在这里，这相当于保持迭代器的堆栈。（一般来说，您需要“解函数化延续”）。

def find_cycles2(graph, L):
    for v, neighbors in graph.items():
        cycle = [v]
        stack = [iter(neighbors)]
        while stack:
            try:
                if len(cycle) == L:
                    if cycle[0] in graph[cycle[-1]]:
                        print(cycle)
                    del cycle[-1]
                    del stack[-1]
                elif len(cycle) < L:
                    v = next(stack[-1])
                    if v <= cycle[0] or v in cycle:
                        continue
                    cycle.append(v)
                    stack.append(iter(graph[v]))
            except StopIteration:
                del cycle[-1]
                del stack[-1]


find_cycles2({0: {1, 2}, 1: {0, 2, 3}, 2: {0, 1, 3}, 3: {1, 2}}, 3)

- David Eisenstat

---

谢谢！这正是我一直在寻找的解决方案，我也了解了对我来说很陌生的生成器概念。 - oneWayC