将循环有向图转换为非循环有向图 (DAG)

Question

如何从有向图中删除循环？这是一个大图（100k+ 节点 200k+ 边），因此该方法需要高效。我需要使有向图成为非循环才能使用像 networkx.topological_ Generations.

这样的函数

我尝试过重复生成循环并删除每个循环路径中最后一个边缘的方法，但在运行了 10 多个小时而没有完成后，我认为这是一次失败的尝试。

失败的尝试（从未完成；效率低下）

def remove_cycles_from_G(G: nx.DiGraph):
    search_for_cycles = True
    while search_for_cycles:
        for cycle_path in nx.simple_cycles(G):
            try:
                G.remove_edge(cycle_path[-1], cycle_path[0])
            except nx.NetworkXError:
                # edge has already been disjointed by a previous edge removal.
                # Restart cycle generator.
                search_for_cycles = (
                    False  # Temporary condition which will be reversed.
                )
                break
        search_for_cycles = not (search_for_cycles)

我还根据这个项目中的演示设计了一种更复杂的启发式方法，但即使这种方法也不适用于这种大小的有向图（运行一小时后我的内存已经耗尽）。

我知道确定要删除的最少边以使有向图无环是一个 NP 难题（反馈弧集问题），但我不一定要尝试找到最少的边以使有向图无环，我只是想要一种快速有效的方法。

编辑

这是指向存储库的链接，其中包含实际数据和如下所示的功能。

Answer 1

最简单的方法是使用深度优先搜索（DFS）来检查循环，但是每当您发现表明循环的上升沿时，只需将其删除并继续即可。