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

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重写了代码，这使得速度提高了约20倍...50倍。但这仍然无法满足实际任务的要求 =(

- v_0ver

---

这个图是可平面化的吗？ - MkWTF

一般来说，图不是平面图。 - v_0ver

在代码行edges2 = combinations(edges,level)中，combinations函数的作用是什么？ - aak318

@aak318 itertools.combinations()（https://docs.python.org/2/library/itertools.html#itertools.combinations） - v_0ver

Answer 1

所述问题NP-Hard。不确定是否属于NP。 为了验证问题的NP-hardness，考虑这样的图形，每个蓝色节点都有一个来自橙色节点的入边。对于这样的图形，我们需要的是在删除边后图形仍然保持强连通性。我们还假设需要删除的最大循环数。 现在，为了尽可能地打破尽可能多的循环，并最小化删除的边数，假设在继续保持强连通的情况下，可以删除图G的最大循环数为removable(G) = k。这对于任何图形G都是明确定义的数量。因此，我们需要一个子图G'，它是G的子图，循环次数为cycles(G)-k。现在，最大化k等价于最小化在G'中幸存的循环数。这就是问题难以解决的原因。

考虑已知为NP难的哈密顿回路问题。假设我们有一个程序breakCycles(G)，它计算图G'作为G的子图，其中移除了最大数量的环（移除最少数量的边），或者cycles(G') = cycles(G) - k。那么，很容易看出，可以使用breakCycles(G)解决哈密顿回路问题，只需将输入图G提供给breakCycles以获取图G'，并当且仅当G'是涉及所有顶点（来自G）的简单环时返回true。

---

更新: 为了得到一个实际的解决方案，让我们尝试获取一个具有最小循环的图形，即蓝色节点的子图，这样删除任何边缘都将导致与橙色节点相连的节点失去连接。

解决上述问题要简单得多，并且在实践中应该有效。

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

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

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

有了上面初始化的图表，我们按照以下方式执行函数...

In [5]: %time eL = getRemovableEdges(DG, list(DG.edges()), [2, 5])                                                                                                                                     
CPU times: user 791 µs, sys: 141 µs, total: 932 µs
Wall time: 936 µs

In [6]: DG.remove_edges_from(eL);                                                                                                                                                                      

In [7]: plt.subplot(121) 
   ...: nx.draw(DG, with_labels=True, font_weight='bold');                                                                                                                                             
   ...: plt.show();                                                                                                                                                                                    

我们得到以下图表：

- aak318

---

+1 意味着您的回答非常有用，因为它提供了问题背后的理论洞见。但是它并没有对问题本身提供太多帮助。用户想要提高代码的效率（即使问题是 NP-难的，也可以做到），或者获得一个可接受的（但快速的）解决方案而不是最佳方案。 - Riccardo Bucco

Answer 2

这不是针对你的问题的直接答案，只是我在思考你的问题时得出的一些见解。

你目前正在采用自下而上的方法来解决你的问题，即从原始图形开始，逐步删除边缘，直到找到一个好的解决方案。像你这样解决问题的方式具有极高的最坏情况复杂度，因为你使用了组合数学。

采用这种方法，你可以实现一种贪心的边缘删除解决方案，其中你获取所有属于简单循环的边缘，并将它们删除，直到橙色节点之间没有连接为止。

你还可以尝试找到最小生成强子图（MSSS）-但它仍然是 NP-Hard。假设所有蓝色节点至少与一个橙色节点相连，这将是最优解，因为它尽可能地减少了循环。添加到所得图形的解决方案中的任何边缘实际上都会创建一个新的循环，因为我们谈论的是强连通分量。在大多数情况下，这个解决方案将是你问题的一个上界，但如果你有很高比例的蓝色节点与橙色节点相连，相对于所有蓝色节点，可能并不那么遥远。

然而，另一种解决这个问题的方法是采用从上往下的方法，即从一个空图开始，逐步添加边直到所有橙色节点都与蓝色节点连接。这种方法会放宽您对“删除最少数量的边”的要求，因为隐含地，这种解决方案将尽可能地添加最少量的边。

以这种思路解决这个问题的方法是找到具有多个根节点的最小生成树。没有一种解决方案可以找到具有多个根节点的生成树，但是您可以实现一种贪心算法来解决这个问题：

1. 将所有边的权重设置为1，除了橙色和蓝色节点之间的边，其权重设置为0
2. 找到单个橙色节点的最小生成树
3. 将属于此生成树的所有边的权重设置为0
4. 对剩余的橙色节点重复2和3的步骤

您可以使用Edmonds算法找到最小生成树，但是还有更好的算法可供选择。

希望这些笔记在某种程度上有所帮助！你正在处理的问题确实相当困难。

- MkWTF

---

谢谢您非常有用的见解 :) - Riccardo Bucco

Answer 3

你可以考虑使用Python实现Bellman-Ford算法，当你得到最短路径后，尝试删除冗余边。这将确保打破沿计算路径的许多循环。同时，这将使你的图形连接，但强连接组件将停止成为这样的组件。这个算法是一种启发式算法，没有数学证明。我不知道这对于数百或数千个节点的规模如何扩展。

- pebox11

---

这个答案如果没有更深入的解释，是不是有点无用呢？ - Riccardo Bucco