min_matching.py

from tqdm import tqdm_notebook as tqdm

def min_matching(edges):
    # Find odd-degree nodes in MST
    odd = []
    for i in range(num):
        cnt = 0
        for e in sum(edges, []):
            if i == e:
                cnt += 1
        if cnt % 2 == 1:
            odd.append(i)
    print('odd: ', odd)   
    
    # Combination of the edges from the odd-degree nodes: 10*9/2=45 if 10 odd-degree edges
    plist = []
    for i in range(len(odd)-1):
        qlist = []
        for j in range(i+1, len(odd)):
            qlist.append([odd[i], odd[j]])
        plist.append(qlist)
    #print('plist:', plist)
    
    # Combination of M edges: 9*7*5*3*1=945 combs
    alist = []
    index = [0 for _ in range(len(odd)-1)]
    
    pbar = tqdm(total=np.math.factorial(len(odd)-1))
    while True:
        blist = []
        for i in range(0, len(odd)-1):
            for pair in plist[i][index[i]:]+plist[i][:index[i]]:
                if not set(pair) & set(sum(blist, [])):
                    blist.append(pair)

        check = False           
        for a in alist:
            if blist == a:
                check = True
        
        if check:
            pass
        elif sorted(sum(blist, [])) != odd:
            pass
        else:
            alist.append(blist) 

        index[-1] += 1
        for j in range(-1, -(len(odd)-1), -1):
            if index[j] > len(plist[j])-1:
                index[j] = 0
                index[j-1] += 1
                
        pbar.update(1)
        if index[0] > len(plist[0])-1:
            break
    pbar.close()
    
    # Minimum Weight Perfect Matching M
    dist = []
    for pl in alist:
        d = 0
        for p in pl:
            d += abs(XY[p[0]] - XY[p[1]]) 
        dist.append(d)
    arg = np.argsort(dist)[0]
    M = alist[arg]
    
    return M