Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.