Find all perfect matching of a graph, very fast!

find_perfect_matching.py

from collections import defaultdict
from pprint import pprint
import time

def tryAppend(combinations, nodeA, nodeB):
    """
    Try to add edge (nodeA, nodeB) to the existing combinations.
    Return new combinations that contains edge (nodeA, nodeB)
    """
    newCombinations = []
    
    if len(combinations) == 0:
        return newCombinations
    
    for pairedNodes, combination in combinations:
        if nodeA in pairedNodes or nodeB in pairedNodes:
            continue
                
        newPairedNodes = pairedNodes.copy()
        newCombination = combination.copy()

        newPairedNodes.add(nodeA)
        newPairedNodes.add(nodeB)
        newCombination.append((nodeA, nodeB))
        newCombinations.append((newPairedNodes, newCombination))

    return newCombinations

if __name__ == '__main__':
    connectionPairs = defaultdict(set)

    # "A;B|A;C|B;C" indicates there're 3 edges, A-B, A-C, and B-C
    serializedGraph = "0;1|0;2|0;4|0;5|1;4|1;5|2;3|2;4|4;5"
    nodeNumber = 6
    
    serializedEdges = serializedGraph.split("|")
    for edge in serializedEdges:
        nodes = edge.split(";")
        nodes = sorted(nodes)
        nodeA = int(nodes[0])
        nodeB = int(nodes[1])
        connectionPairs[nodeA].add(nodeB)

    # main logic
    startTime = time.time()
    
    combinations = []
    sortedKeys = sorted(connectionPairs.keys())
    for i, nodeA in enumerate(sortedKeys):
        connectedNodes = connectionPairs[nodeA]
        
        newCombinations = []
        for nodeB in connectedNodes:
            if i == 0:
                newCombinations.append((set([nodeA, nodeB]), [(nodeA, nodeB)]))
            else:
                newCombinations.extend(tryAppend(combinations, nodeA, nodeB))
        
        # for the old combinations that doesn't contain nodeA, we abandon
        # them because it's impossible for them to form a perfect matching
        for combination in combinations:
            if nodeA in combination[0]:
                newCombinations.append(combination)
        
        combinations = newCombinations

        print(i + 1, '/', len(connectionPairs), ": ", len(combinations))

    # exclude unfinished combinations
    perfectMatchings = [x[1] for x in combinations if len(x[0]) == nodeNumber]
    
    endTime = time.time()

    print("Number of perfect matchings:", len(perfectMatchings))
    for perfectMatching in perfectMatchings:
        print(perfectMatching)
    print("Elapsed time: ", endTime - startTime, " seconds")