在保持某些节点的连通性的条件下打破有向图中的循环

Question

我有一个由强连通分量（蓝色）和一组节点（橙色）组成的有向图，它们是它的输入。挑战在于用最少的边缘去除尽可能多的循环。此外，每个橙色节点到每个蓝色节点都必须有一条路径。

我用蛮力解决了这个问题：

1. 去除随机边缘
2. 检查从每个橙色节点到每个蓝色节点的路径。如果一切正常，我会在列表中添加一条边并计算循环数。
3. 我将边返回到图形并转到步骤 1，直到我遍历所有边
4. 接下来，从结果列表（长度为 n）我生成组合 C (n, k) 其中 k = {2 ... n}
5. 我对所有边的组合执行操作 1、2、3

代码的核心如下所示：

    for level in range(2, len(edges)):
        stop = True
        edges2 = combinations(edges,level)
        for i, e in enumerate(edges2):
            g.remove_edges_from(e)

            test = True
            for node in orange_nodes:
                d = nx.algorithms.descendants(g, node)
                test = blue_nodes == d
                if not test:
                    break
            if test:
                stop = False
                cycles_count = len(list(nx.simple_cycles(g)))
                print(f'{i}\t{level}\t{cycles_count}\t{e}')

            g.add_edges_from(e)

        if stop:
            break

问题：

1. 是否有可能以某种方式优化代码（nx.algorithms.descendants() 和 nx.simple_cycles() 非常慢）？是否可以使用生成树或反馈弧集重写代码？
2. 也许有一种快速搜索算法不是最好的解决方案，而是一个好的解决方案？

另外： 我重写了代码，因为它使用了graph-tool，它提供了 ~20x...50x 的速度提升。但这仍然不允许我们接近设定的实际任务=（

Answer 1

所述问题是NP-Hard。也不确定它是否属于 NP 类型。\n为了验证问题的NP 难度，请考虑这样的图：每个蓝色节点都有来自橙色节点的传入边。对于这样的图，我们需要的是去掉边后的图仍然是强连通的。我们还假设需要删除最大数量的循环。

\n

现在，为了以最少的移除边打破尽可能多的循环，假设图 G 在继续强连接的同时可以移除的最大循环数为removable(G) = k。对于任何图形来说，这都是一个明确定义的量G。因此，我们需要一个图G\'，它是 的子图，G循环数为cycles(G)-k。现在最大化k相当于最小化 中存活的周期数G\'。这就是问题变得困难的原因。

\n

考虑已知为NP 困难的哈密顿循环问题。\n假设我们有一个程序将图计算为 的子图，其中删除了最大数量的循环（删除了最少数量的边）或。然后，很容易看出，哈密顿循环问题也可以通过仅提供输入图来获得图并返回 true 来解决，当且仅当是一个涉及所有顶点（的）的简单循环。breakCycles(G)G\'Gcycles(G\') = cycles(G) - kbreakCycles(G)GbreakCyclesG\'G\'G

\n\n

更新：为了获得实际的解决方案，让我们看看获得一个具有最小循环的图，这是蓝色节点的子图，这样删除任何边将导致具有橙色节点的那些节点失去连接其事件。

\n

解决上述问题要容易得多，并且在实践中应该效果很好

\n

def getRemovableEdges(G, edgeLst, initNodes):\n    import networkx as nx\n    removableEdgeLst = []\n    for (u,v) in edgeLst:\n        G.remove_edge(u, v)\n        f = nx.floyd_warshall(G)\n        addEdge = True\n        for s in initNodes:\n            if \'inf\' in list(map(str, f[s].values())):\n                G.add_edge(u,v)\n                addEdge = False\n                break\n        if addEdge:\n            removableEdgeLst.append((u,v))\n    return removableEdgeLst\n\n

\n

要在提供的示例上进行尝试，我们需要首先初始化图表

\n

DG = nx.DiGraph()\nDG.add_nodes_from(range(1,8))\nDG.add_edges_from([(1,2), (2,3), (3,4), (3,5), (4,5), (5,1), (5,4), (5,7), (6,4), (7,6)]);\n

\n

通过上面初始化的图表，我们执行如下函数......

\n

\nIn [5]: %time eL = getRemovableEdges(DG, list(DG.edges()), [2, 5])                                                                                                                                     \nCPU times: user 791 \xc2\xb5s, sys: 141 \xc2\xb5s, total: 932 \xc2\xb5s\nWall time: 936 \xc2\xb5s\n\nIn [6]: DG.remove_edges_from(eL);                                                                                                                                                                      \n\nIn [7]: plt.subplot(121) \n   ...: nx.draw(DG, with_labels=True, font_weight=\'bold\');                                                                                                                                             \n   ...: plt.show();                                                                                                                                                                                    \n

\n

我们得到如下图，

\n

\n