The minimum remote nodes needed to shorten the path from algorithm A to B in Python

I am trying to solve a problem related to graph theory, but I don’t seem to remember / did not find / did not understand the correct / best approach, so I decided that I would ask experts ...

I have a list of paths from two nodes (1 and 10 in the sample code). I am trying to find the minimum number of nodes to remove to cut all paths. I can also delete only certain nodes.

I have currently implemented (below) as a brute force search. This works fine on my test suite, but it will be a problem when scaling to graphs with paths at 100K and available nodes at 100 (factor problem). Right now, I don’t care about the order in which I delete the nodes, but at some point I will take this into account (the switch sets are listed in the code below).

I believe that there should be a way to solve this problem using the maximum flow / min algorithm. Everything that I read, at least in some way, goes through my head. It has been a few (SEVERAL) years since I did such things, and I can’t remember anything.

So my questions are:

1) Is there a better way to solve this problem besides testing all combinations and making the smallest set?

2) If so, can you either explain this or, preferably, give a pseudo code to help explain? I guess there is probably a library that is already doing this in some way (I have searched and used networkX lately, but open to others)

3) If not (or even so), suggestions on how a multi-threaded / technological solution? I want to try to get every bit of performance that I can from a computer. (I found some good topics on this subject. I simply didn’t have the opportunity to implement in such a way that I understood what I would ask at the same time by chance. First I want everything to be correct before optimizing.)

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

UPDATE: , 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 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