bug in definition of "minimum-weight perfect matching" function

[Shriyanshagro]

ChristofidesAlgorithm/christofides.py

Line 129 in 7e85e6d

def minimum_weight_matching(MST, G, odd_vert):

The current approach doesn't ensure minimum weighted edges from odd_vert with no two edge-sharing same vertices.

the function should be instead:

def minimum_weight_matching(MST, G, odd_vert):
    vertices = []
    for W, u, v in sorted((G[u][v], u, v)
                          for u in G
                          for v in G[u]
                          if v in odd_vert and u in odd_vert):
        if u not in vertices and v not in vertices:
            length = G[v][u]
            MST.append((u, v, length))
            vertices.append(u)
            vertices.append(v)

[Retsediv]

@Shriyanshagro Thank you so much! Great catch!

Could you, please, make PR to resolve this issue + test which shows that it will actually solve this problem?

[Shriyanshagro]

Sure, will do that

On Fri, 29 Nov 2019 at 3:03 PM, Andrew Zhuravchak ***@***.***> wrote: @Shriyanshagro <https://github.com/Shriyanshagro> Thank you so much! Great catch! Could you, please, make PR to resolve this issue + test which shows that it will actually solve this problem? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#4?email_source=notifications&email_token=ADJZYQTCJU5IAW75LNFU7CLQWDOXVA5CNFSM4JSFQ6JKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEFOLNCI#issuecomment-559724169>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADJZYQUCLHE3Y75EMPRBHLTQWDOXVANCNFSM4JSFQ6JA> .

-- Shriyansh

[PhanLeSon03]

This code is not running correctly. It is not written well (difficult to understand) and having a lot of mistakes. Example: finding the perfect matching and union with spanning tree is included in function 'minimum_weight_matching'. But did not check the redundance adding: 1 edge could be added more than 1 time.
def minimum_weight_matching(MST, G, odd_vert):
import random
random.shuffle(odd_vert)

while odd_vert:
    v = odd_vert.pop()
    length = float("inf")
    u = 1
    closest = 0
    for u in odd_vert:
        if v != u and G[v][u] < length:
            length = G[v][u]
            closest = u
    if (v, closest, length) not in MST:  ----------> to avoid repeated adding
        MST.append((v, closest, length))
        odd_vert.remove(closest)

Some more points but I do not list here.

[Retsediv]

@PhanLeSon03 You are welcome in submitting the PR to fix that

[CCSharper]

Unfortunately this code only finds a perfect matching with a lot of good edges, but it doesn't find the one and only minimal perfect matching (e.g. it is possible that the minimal perfect matching doesn't contain the edge with lowest weight)