Shot in the Dark: Minimum-weight perfect matching algorithm

[Paul Magwene]

On Fri, 15 Mar 2002 21:35:04 -0500, David Eppstein wrote:

> In article <pan.2002.03.15.19.52.32.366019.81993 at snet.net>,
>  Paul Magwene <p.magwene at snet.net> wrote:
> 
>> Does anybody happen to have a Python implementation of a minimum-weight
>> perfect matching algorithm?  Or a Python interface to one?
>> 
>> I'm aware of (some) of the literature on this topic, but as a
>> non-computer scientist I'd rather not have to twist my mind around one
>> of the Blossum algorithms.
> 
> I take it you need nonbipartite perfect matching?
> 
> Bipartite is much easier.  (I don't have Python even for that, but I do
> have some simple C code...)
> 

Hi David,

Yes, it's for non-bipartite matching I'm afraid.

Some more digging did turn up this neat little Java applet:

http://www.math.sfu.ca/~goddyn/Courseware/Visual_Matching.html

with source code in the same directory.  I may try and translate that to
something Pythonic - it's definitely more inviting than the Blossum4 code.

Thanks,
Paul

p.s. For anyone else who might be following this thread and is
interested in computational geometry and graph algorithms, David
Eppstein's web page, bibliography, and pubs are a real treasure trove.
Check 'em out!