Maximum weight matching
=======================

>>> import math
>>> from networkx import *

>>> def sortdict(d):
...     s = d.items()
...     s.sort()
...     print '{' + ', '.join(map(lambda t: ': '.join(map(repr, t)), s)) + '}'


Trivial cases
-------------

>>> G = Graph()
>>> max_weight_matching(G)
{}

>>> G = Graph()
>>> G.add_edge(0, 0, weight=100)
>>> max_weight_matching(G)
{}

>>> G = Graph()
>>> G.add_edge(0, 1)
>>> sortdict(max_weight_matching(G))
{0: 1, 1: 0}

>>> G = Graph()
>>> G.add_edge('one', 'two', weight=10)
>>> G.add_edge('two', 'three', weight=11)
>>> sortdict(max_weight_matching(G))
{'three': 'two', 'two': 'three'}

>>> G = Graph()
>>> G.add_edge((1,), 2, weight=5)
>>> G.add_edge(2, 3, weight=11)
>>> G.add_edge(3, 4, weight=5)
>>> sortdict(max_weight_matching(G))
{2: 3, 3: 2}
>>> sortdict(max_weight_matching(G, 1))
{2: (1,), 3: 4, 4: 3, (1,): 2}

Floating point weights:

>>> G = Graph()
>>> G.add_edge(1, 2, weight=math.pi)
>>> G.add_edge(2, 3, weight=math.exp(1))
>>> G.add_edge(1, 3, weight=3.0)
>>> G.add_edge(1, 4, weight=math.sqrt(2.0))
>>> sortdict(max_weight_matching(G))
{1: 4, 2: 3, 3: 2, 4: 1}

Negative weights:

>>> G = Graph()
>>> G.add_edge(1, 2, weight=2)
>>> G.add_edge(1, 3, weight=-2)
>>> G.add_edge(2, 3, weight=1)
>>> G.add_edge(2, 4, weight=-1)
>>> G.add_edge(3, 4, weight=-6)
>>> sortdict(max_weight_matching(G))
{1: 2, 2: 1}
>>> sortdict(max_weight_matching(G, 1))
{1: 3, 2: 4, 3: 1, 4: 2}


Blossoms
--------

Create S-blossom and use it for augmentation:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 8), (1, 3, 9), (2, 3, 10), (3, 4, 7) ])
>>> sortdict(max_weight_matching(G))
{1: 2, 2: 1, 3: 4, 4: 3}
>>> G.add_weighted_edges_from([ (1, 6, 5), (4, 5, 6) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}

Create S-blossom, relabel as T-blossom, use for augmentation:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 9), (1, 3, 8), (2, 3, 10), (1, 4, 5),
...                    (4, 5, 4), (1, 6, 3) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}
>>> G.add_edge(4, 5, weight=3)
>>> G.add_edge(1, 6, weight=4)
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}
>>> G.remove_edge(1, 6)
>>> G.add_edge(3, 6, weight=4)
>>> sortdict(max_weight_matching(G))
{1: 2, 2: 1, 3: 6, 4: 5, 5: 4, 6: 3}

Create nested S-blossom, use for augmentation:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 9), (1, 3, 9), (2, 3, 10), (2, 4, 8),
...                    (3, 5, 8), (4, 5, 10), (5, 6, 6) ])
>>> sortdict(max_weight_matching(G))
{1: 3, 2: 4, 3: 1, 4: 2, 5: 6, 6: 5}

Create S-blossom, relabel as S, include in nested S-blossom:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 10), (1, 7, 10), (2, 3, 12), (3, 4, 20),
...                    (3, 5, 20), (4, 5, 25), (5, 6, 10), (6, 7, 10),
...                    (7, 8, 8) ])
>>> sortdict(max_weight_matching(G))
{1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5, 7: 8, 8: 7}

Create nested S-blossom, augment, expand recursively:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 8), (1, 3, 8), (2, 3, 10), (2, 4, 12),
...                    (3, 5, 12), (4, 5, 14), (4, 6, 12), (5, 7, 12),
...                    (6, 7, 14), (7, 8, 12) ])
>>> sortdict(max_weight_matching(G))
{1: 2, 2: 1, 3: 5, 4: 6, 5: 3, 6: 4, 7: 8, 8: 7}

Create S-blossom, relabel as T, expand:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 23), (1, 5, 22), (1, 6, 15), (2, 3, 25),
...                    (3, 4, 22), (4, 5, 25), (4, 8, 14), (5, 7, 13) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4}

Create nested S-blossom, relabel as T, expand:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 19), (1, 3, 20), (1, 8, 8), (2, 3, 25),
...                    (2, 4, 18), (3, 5, 18), (4, 5, 13), (4, 7, 7),
...                    (5, 6, 7) ])
>>> sortdict(max_weight_matching(G))
{1: 8, 2: 3, 3: 2, 4: 7, 5: 6, 6: 5, 7: 4, 8: 1}


Nasty cases
-----------

Create blossom, relabel as T in more than one way, expand, augment:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 45), (1, 5, 45), (2, 3, 50), (3, 4, 45),
...                    (4, 5, 50), (1, 6, 30), (3, 9, 35), (4, 8, 35),
...                    (5, 7, 26), (9, 10, 5) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9}

Again but slightly different:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 45), (1, 5, 45), (2, 3, 50), (3, 4, 45),
...                    (4, 5, 50), (1, 6, 30), (3, 9, 35), (4, 8, 26),
...                    (5, 7, 40), (9, 10, 5) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9}

Create blossom, relabel as T, expand such that a new least-slack S-to-free
edge is produced, augment:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 45), (1, 5, 45), (2, 3, 50), (3, 4, 45),
...                    (4, 5, 50), (1, 6, 30), (3, 9, 35), (4, 8, 28),
...                    (5, 7, 26), (9, 10, 5) ])
>>> sortdict(max_weight_matching(G))
{1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9}

Create nested blossom, relabel as T in more than one way, expand outer
blossom such that inner blossom ends up on an augmenting path:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 45), (1, 7, 45), (2, 3, 50), (3, 4, 45),
...                    (4, 5, 95), (4, 6, 94), (5, 6, 94), (6, 7, 50),
...                    (1, 8, 30), (3, 11, 35), (5, 9, 36), (7, 10, 26),
...                    (11, 12, 5) ])
>>> sortdict(max_weight_matching(G))
{1: 8, 2: 3, 3: 2, 4: 6, 5: 9, 6: 4, 7: 10, 8: 1, 9: 5, 10: 7, 11: 12, 12: 11}

Create nested S-blossom, relabel as S, expand recursively:

>>> G = Graph()
>>> G.add_weighted_edges_from([ (1, 2, 40), (1, 3, 40), (2, 3, 60), (2, 4, 55),
...                    (3, 5, 55), (4, 5, 50), (1, 8, 15), (5, 7, 30),
...                    (7, 6, 10), (8, 10, 10), (4, 9, 30) ])
>>> sortdict(max_weight_matching(G, 1))
{1: 2, 2: 1, 3: 5, 4: 9, 5: 3, 6: 7, 7: 6, 8: 10, 9: 4, 10: 8}