python - 在 Python 中从 A 到 B 算法切割路径所需的最小移除节点

Question

我正在尝试解决与图论相关的问题，但似乎无法记住/找到/理解正确/最佳方法，所以我想我应该问问专家...

我有一个来自两个节点(示例代码中的 1 和 10)的路径列表。我试图找到要删除的最小节点数以切断所有路径。我也只能删除某些节点。

我目前(在下方)将其实现为暴力搜索。这在我的测试集上运行良好，但在扩展到具有 100K 路径和 100 可用节点(阶乘问题)的图形时将成为问题。现在，我不关心我删除节点的顺序，但我会在某个时候考虑到这一点(切换集以在下面的代码中列出)。

我相信应该有一种方法可以使用最大流/最小切割算法来解决这个问题。我正在阅读的所有内容在某种程度上都超出了我的理解范围。自从做这类事情以来已经好几年了，我似乎什么都不记得了。

所以我的问题是:

1)除了测试所有组合并取最小的集合之外，是否有更好的方法来解决这个问题？

2) 如果是这样，您能否解释一下，或者最好给出伪代码来帮助解释？我猜可能有一个图书馆已经以某种方式做到了这一点(我最近一直在寻找和使用 networkX，但对其他人开放)

3) 如果不是(或什至是)，关于如何解决多线程/进程的建议？我想尽我所能从计算机获得每一点性能。 (我在这个问题上找到了一些很好的线索，但我还没有机会实现，所以我想我会同时问这个问题。我首先想让一切正常工作，然后再进行优化。)

4) 关于使代码更“Pythonic”的一般建议(可能也有助于提高性能)。我知道我可以做出一些改进，但我对 Python 还是个新手。

感谢您的帮助。

#!/usr/bin/env python


def bruteForcePaths(paths, availableNodes, setsTested, testCombination, results, loopId):

    #for each node available, we are going to
    # check if we have already tested set with node
    # if true- move to next node
    # if false- remove the paths effected,
    #           if there are paths left,
    #               record combo, continue removing with current combo,
    #           if there are no paths left,
    #               record success, record combo, continue to next node

    #local copy
    currentPaths = list(paths)
    currentAvailableNodes = list(availableNodes)
    currentSetsTested = set(setsTested)
    currentTestCombination= set(testCombination)

    currentLoopId = loopId+1

    print "loop ID: %d" %(currentLoopId)
    print "currentAvailableNodes:"
    for set1 in currentAvailableNodes:
        print "  %s" %(set1)

    for node in currentAvailableNodes:
        #add to the current test set
        print "%d-current node: %s current combo: %s" % (currentLoopId, node, currentTestCombination)
        currentTestCombination.add(node)
        # print "Testing: %s" % currentTestCombination
        # print "Sets tested:"
        # for set1 in currentSetsTested:
        #     print "  %s" % set1

        if currentTestCombination in currentSetsTested:
            #we already tested this combination of nodes so go to next node
            print "Already test: %s" % currentTestCombination
            currentTestCombination.remove(node)
            continue

        #get all the paths that don't have node in it
        currentRemainingPaths = [path for path in currentPaths if not (node in path)]

        #if there are no paths left
        if len(currentRemainingPaths) == 0:
            #save this combination
            print "successful combination: %s" % currentTestCombination
            results.append(frozenset(currentTestCombination))
            #add to remember we tested combo
            currentSetsTested.add(frozenset(currentTestCombination))
            #now remove the node that was add, and go to the next one
            currentTestCombination.remove(node)
        else:
            #this combo didn't work, save it so we don't test it again
            currentSetsTested.add(frozenset(currentTestCombination))
            newAvailableNodes = list(currentAvailableNodes)
            newAvailableNodes.remove(node)
            bruteForcePaths(currentRemainingPaths,
                            newAvailableNodes,
                            currentSetsTested,
                            currentTestCombination,
                            results,
                            currentLoopId)

            currentTestCombination.remove(node)

    print "-------------------"
    #need to pass "up" the tested sets from this loop
    setsTested.update(currentSetsTested)

    return None

if __name__ == '__main__':

    testPaths = [
        [1,2,14,15,16,18,9,10],
        [1,2,24,25,26,28,9,10],
        [1,2,34,35,36,38,9,10],
        [1,3,44,45,46,48,9,10],
        [1,3,54,55,56,58,9,10],
        [1,3,64,65,66,68,9,10],

        [1,2,14,15,16,7,10],
        [1,2,24,7,10],
        [1,3,34,35,7,10],

        [1,3,44,35,6,10],
        ]


    setsTested = set()
    availableNodes = [2, 3, 6, 7, 9]
    results = list()
    currentTestCombination = set()

    bruteForcePaths(testPaths, availableNodes, setsTested, currentTestCombination, results, 0)

    print "results:"
    for result in sorted(results, key=len):
        print result

更新: 我使用 itertool 重新编写了代码以生成组合。它使代码更干净、更快(并且应该更容易进行多进程处理。现在尝试按照建议和多进程函数找出支配节点。

def bruteForcePaths3(paths, availableNodes, results):

    #start by taking each combination 2 at a time, then 3, etc
    for i in range(1,len(availableNodes)+1):
        print "combo number: %d" % i

        currentCombos = combinations(availableNodes, i)

        for combo in currentCombos:
            #get a fresh copy of paths for this combiniation
            currentPaths = list(paths)
            currentRemainingPaths = []
            # print combo

            for node in combo:
                #determine better way to remove nodes, for now- if it's in, we remove
                currentRemainingPaths = [path for path in currentPaths if not (node in path)]
                currentPaths = currentRemainingPaths

            #if there are no paths left
            if len(currentRemainingPaths) == 0:
                #save this combination
                print combo
                results.append(frozenset(combo))

    return None

Answer 1

这是一个忽略路径列表的答案。它只需要一个网络、一个源节点和一个目标节点，并找到网络中的最小节点集，既不是源节点也不是目标节点，因此删除这些节点会断开源与目标的连接。

如果我想找到最小边集，我可以通过搜索 Max-Flow min-cut 找到方法。请注意，位于 http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Generalized_max-flow_min-cut_theorem 的维基百科文章指出有一个广义的最大流最小割定理，它考虑了顶点容量和边容量，这至少是令人鼓舞的。另请注意，边缘容量以 Cuv 给出，其中 Cuv 是从 u 到 v 的最大容量。在图中，它们似乎被绘制为 u/v。因此前向的边容量可以不同于后向的边容量。

为了将最小顶点切割问题伪装成最小边切割问题，我建议利用这种不对称性。首先给所有现有边一个巨大的容量——例如图中节点数的 100 倍。现在用两个顶点 Xi 和 Xo 替换每个顶点 X，我将它们称为传入和传出顶点。对于 X 和 Y 之间的每条边，在 Xo 和 Yi 之间创建一条边，现有容量向前移动，但容量为 0 向后移动 - 这些是单向边。现在为每个 X 在 Xi 和 Xo 之间创建一条边，其中容量 1 向前，容量 0 向后。

现在在结果图上运行最大流最小切割。因为所有原始链接都具有巨大的容量，min cut 必须全部由容量为 1 的链接组成(实际上 min cut 定义为将节点集一分为二:你真正想要的是对的集合节点 Xi、Xo，一半是 Xi，另一半是 Xo，但你可以很容易地从另一半得到一个)。如果断开这些链接，就会将图形断开为两部分，就像标准的最大流最小切割一样，因此删除这些节点将断开源与目标的连接。因为您有最小切割，所以这是最小的此类节点集。

如果你能找到 max-flow min-cut 的代码，比如 http://www.cs.sunysb.edu/~algorith/files/network-flow.shtml 指向的代码我希望它会给你最小的削减。如果不是，例如，如果你通过解决线性规划问题来解决问题，因为你碰巧手边有一个线性规划求解器，请注意来自 http://www.cse.yorku.ca/~aaw/Wang/MaxFlowMinCutAlg.html 的示例。当图形被修改以减去解决方案实际使用的边缘容量时，最小切割的一半是从源可到达的节点集 - 因此仅给出最大流量下使用的边缘容量，您可以很容易地找到它.