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

Question

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

我用暴力破解了这个问题：

移除随机边
检查从每个橙色节点到每个蓝色节点的路径。如果一切正常，我在列表中添加一条边并计算循环数。
我 return 图形的边缘并转到步骤 1，直到我遍历所有边缘
接下来，根据结果列表（长度为 n），我生成组合 C (n, k)，其中 k = {2 ... n}
我对边的所有组合执行操作 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

问题：

是否有可能以某种方式优化代码（nx.algorithms.descendants() 和 nx.simple_cycles() 非常慢）？是否可以使用 Spanning tree or Feedback arc set 重写代码？
也许有一个快速搜索算法不是最好的解决方案，而是一个很好的解决方案？

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

Answer 1

您可以尝试考虑 Bellman-Ford 算法的 python 实现，当您获得最短路径时，尝试删除冗余边。这将确保打破计算路径上的许多循环。同时，这将使您的图表保持连接状态，但强连接组件将不再是这样的组件。该算法是一种启发式算法，没有数学证明。我不知道这如何扩展到数百或数千个节点。

Answer 2

所述问题是NP-Hard。也不确定它是否在 NP 中。为了验证问题的NP-hardness，请考虑这样的图形，即每个蓝色节点都有来自橙色节点的传入边。对于这样的图，我们需要的是去除边后的图继续强连通。我们还假设需要删除最大循环数。

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

考虑 Hamiltonian Cycle problem that is known to be NP-hard。假设我们有一个程序 breakCycles(G) 计算图 G' 作为 G 的子图，其中删除了最大数量的循环（删除了最少数量的边）或 cycles(G') = cycles(G) - k。然后，很明显哈密顿循环问题也可以使用breakCycles(G)解决，只需提供输入图G到breakCycles得到图G'和return true iff G' 是一个涉及所有顶点（G）的简单循环。

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

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

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();

我们得到如下图，

Answer 3

这不是您问题的直接答案，只是我在思考您的问题时得到的一些见解。

您目前正在以 自下而上 的方法研究您的问题，您从原始图形开始，然后开始删除边缘，直到找到一个好的解决方案。您正在解决的问题具有非常高的最坏情况复杂性，因为您使用的是组合数学。

使用这种方法，您可以实施贪婪的边删除解决方案，在该解决方案中获取所有属于简单循环的边并删除它们，直到橙色节点之间没有连接为止。

您也可以尝试找到最小跨度强子图 (MSSS) - 但它仍然是 NP-Hard。假设所有蓝色节点都至少连接了一个橙色节点，这将是最佳解决方案，因为它尽可能地减少了周期。添加到结果图的解决方案中的任何边缘实际上都会创建一个新的循环，因为我们正在谈论强连接的组件。在大多数情况下，此解决方案将是您问题的上限，但如果您有很高比例的蓝色节点连接到橙色节点，与所有蓝色节点相比，可能相距不远。

但是，研究这个问题的另一种方法是使用 自上而下 方法，从空图开始，然后开始添加边，直到所有的边都变成橙色与蓝色节点相连的节点。这种方法会放宽您对删除最小边数的要求，因为隐含地，这种类型的解决方案将添加尽可能少的边。

以这种思维方式解决此问题的一种方法是找到具有多个根节点的最小跨度树状结构。没有找到具有多个根节点的树状结构的解决方案，但您可以再次为此实施贪婪的方法：

将所有边权重设置为 1，除了设置为 0 的橙色和蓝色节点之间的边
求出单个橙色节点的最小跨度树状结构
将属于该树状结构的所有边的权重设置为0
对剩余的橙色节点重复 2 和 3

您可以使用 Edmonds algorithm 找到最小跨度树状结构，但还有更好的方法。

希望这些笔记对您有所帮助！你遇到的问题确实比较难

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

Breaking cycles in a digraph with the condition of preserving connectivity for certain nodes

python

digraphs

networkx