def find_matchings(graph, n=5):
    best_matching = nx.max_weight_matching(graph, True)
    matchings = [best_matching]

    for u, v in best_matching.items():
        if v <= u:
            continue
        smaller_graph = nx.Graph(graph)
        smaller_graph.remove_edge(u, v)
        matching = nx.max_weight_matching(smaller_graph, True)
        if len(matching) > 0:
            matchings.append(matching)

    matching_costs = [(matching_cost(graph, matching), matching) for matching in matchings]
    matching_costs.sort()

    final_matchings = []
    last_cost = None
    for cost, matching in matching_costs:
        if cost == last_cost:
            continue
        last_cost = cost
        final_matchings.append((cost, matching))

    return final_matchings

def find_matchings(graph, n=5):
    """
    Find the n best matchings for a graph. The best matching is guaranteed to be the best, but the others are only
    estimates.
    """
    best_matching = nx.max_weight_matching(graph, True)
    matchings = [best_matching]
    for u, v in best_matching.items():
        if v <= u:
            continue
        # Remove the matching
        smaller_graph = nx.Graph(graph)
        smaller_graph.remove_edge(u, v)
        matching = nx.max_weight_matching(smaller_graph, True)
        matchings.append(matching)

    matching_costs = [(matching_cost(graph, matching), matching) for matching in matchings]
    matching_costs.sort()

    # HACK: The above code end up giving duplicates of the same path, even though the matching is different. To prevent
    # this, we remove matchings with the same cost.
    final_matchings = []
    last_cost = None
    for cost, matching in matching_costs:
        if cost == last_cost:
            continue
        last_cost = cost
        final_matchings.append((cost, matching))

    return final_matchings

 def test_trivial5(self):
     """Path"""
     G = nx.Graph()
     G.add_edge(1, 2, weight=5)
     G.add_edge(2, 3, weight=11)
     G.add_edge(3, 4, weight=5)
     assert_equal(nx.max_weight_matching(G), {2: 3, 3: 2})
     assert_equal(nx.max_weight_matching(G, 1), {1: 2, 2: 1, 3: 4, 4: 3})

    def test_s_blossom(self):
        """Create S-blossom and use it for augmentation:"""
        G = nx.Graph()
        G.add_weighted_edges_from([(1, 2, 8), (1, 3, 9), (2, 3, 10), (3, 4, 7)])
        assert_equal(nx.max_weight_matching(G), {1: 2, 2: 1, 3: 4, 4: 3})

        G.add_weighted_edges_from([(1, 6, 5), (4, 5, 6)])
        assert_equal(nx.max_weight_matching(G), {1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1})

 def test_negative_weights(self):
     """Negative weights"""
     G = nx.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)
     assert_equal(nx.max_weight_matching(G), {1: 2, 2: 1})
     assert_equal(nx.max_weight_matching(G, 1), {1: 3, 2: 4, 3: 1, 4: 2})

 def test_s_t_blossom(self):
     """Create S-blossom, relabel as T-blossom, use for augmentation:"""
     G = nx.Graph()
     G.add_weighted_edges_from([(1, 2, 9), (1, 3, 8), (2, 3, 10), (1, 4, 5), (4, 5, 4), (1, 6, 3)])
     assert_equal(nx.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)
     assert_equal(nx.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)
     assert_equal(nx.max_weight_matching(G), {1: 2, 2: 1, 3: 6, 4: 5, 5: 4, 6: 3})

 def test_nested_s_blossom_relabel_expand(self):
     """Create nested S-blossom, relabel as T, expand:"""
     G = nx.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)]
     )
     assert_equal(nx.max_weight_matching(G), {1: 8, 2: 3, 3: 2, 4: 7, 5: 6, 6: 5, 7: 4, 8: 1})

 def test_s_blossom_relabel_expand(self):
     """Create S-blossom, relabel as T, expand:"""
     G = nx.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)]
     )
     assert_equal(nx.max_weight_matching(G), {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4})

 def test025_barbell_graph(self):
     """ Very small barbell graph. """
     g = nx.barbell_graph(9, 2)
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate2, "test025_barbell_graph_edmonds")
     mate1 = mv.max_cardinality_matching( g )
     self.assertEqual( len(mate1), len(mate2) )

def match_candidates_and_characters(characters, candidates):
    matches = dict([(character, {}) for character in characters])

    # generate a graph that connects candidates and characters that match
    G = nx.Graph()
    G.add_nodes_from(characters, bipartite=0)
    G.add_nodes_from(candidates, bipartite=1)
    for character in characters:
        names = []
        for name in [character] + characters[character]:
            names.append(tuple(name.replace(',', ' ').replace('\'s ', ' \'s ').replace('s\'', 's \' ').split()))
        for cand in candidates:
            score = match_to_any_names(names, cand)
            if score > 0:
                G.add_edge(character, cand, weight=score)
        # if don't find any match, try the other direction
        # sparknote character name might be contained by some candidate names
        if len(matches[character]) == 0 and len(candidates) > 0:
            scores = [strict_fuzzy_match_reference(cand, names[0]) for cand in candidates]
            index, score = max(enumerate(scores), key=operator.itemgetter(1))
            if score > 0:
                G.add_edge(character, candidates[index], weight=score)

    max_matching = nx.max_weight_matching(G, maxcardinality=True)

    return (max_matching, G)

 def test180_tutte_cage_graph(self):
     """ Tutte 12-cage graph. """
     g = nx.LCF_graph(126, [17, 27, -13, -59, -35, 35, -11, 13, -53\
                            , 53, -27, 21, 57, 11, -21, -57, 59, -17], 7)
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     self.assertEqual( len(mate1), len(mate2) )

 def test_trivial4(self):
     """Small graph"""
     G = nx.Graph()
     G.add_edge('one', 'two', weight=10)
     G.add_edge('two', 'three', weight=11)
     assert_equal(nx.max_weight_matching(G),
                  {'three': 'two', 'two': 'three'})

 def test170_bullgraph(self):
     """ Bull graph. """
     g = nx.bull_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     #td.showGraph(g, mate1, "test170_bullgraph")
     self.assertEqual( len(mate1), len(mate2) )

 def test030_twoedges(self):
     """ Two edges. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     self.assertEqual( len(mate1), len(mate2) )

 def test040_threeedges(self):
     """ Three edges, linear. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     self.assertEqual( len(mate1), len(mate2) )

 def test020_singleedge(self):
     """ Single edge. """
     g = nx.Graph()
     g.add_edge(0,1)
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     self.assertEqual( len(mate1), len(mate2) )

 def test200_icosahedralgraph(self):
     """ Icosahedral graph. """
     g = nx.icosahedral_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     #td.showGraph(g, mate1, "test200_icosahedralgraph")
     self.assertEqual( len(mate1), len(mate2) )

 def test190_octahedralgraph(self):
     """ Octahedral graph. """
     g = nx.octahedral_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test190_octahedralgraph")
     self.assertEqual( len(mate1), len(mate2) )

 def test_nasty_blossom_augmenting(self):
     """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 = nx.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),
         ]
     )
     assert_equal(
         nx.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}
     )

def add_edges_for_euler(in_g, out_g):
  # optimize_dead_ends(in_g, out_g)
  temp_graph = graph_of_odd_nodes(in_g, out_g)
  print "DEBUG: Finished calculating shortest paths, now calculating matching..."
  matching = networkx.max_weight_matching(temp_graph, maxcardinality=True)
  print "DEBUG: Finished calculating matching, now adding new edges..."
  short_matching = {}
  for k in matching:
    if k not in short_matching and matching[k] not in short_matching:
      short_matching[k] = matching[k]
  for source in short_matching:
    add_artificial_edge(in_g, out_g, source, short_matching[source])
  #assert(networkx.is_connected(out_g))
  nodes = odd_nodes(out_g)
  num_odd_nodes = len(nodes)
  print "DEBUG: After all that we have %s odd-degree nodes." % num_odd_nodes
#  reachable_nodes = set(networkx.dfs_preorder_nodes(out_g, 105437194))
#  unreachable_nodes = set(out_g.nodes()) - reachable_nodes
#  for n in unreachable_nodes:
#    print "%s (%s) is unreachable." % (n, out_g.node[n]['pretty_name'])
#    path = networkx.dijkstra_path(in_g, 105437194,  n, weight='length')
#    print "Here is how we would get there on the original graph: %s" % [(pn, in_g.node[pn]['pretty_name']) for pn in path]
#    print "Here are the nodes we have purged from that path: %s" % [(pn, in_g.node[pn]['pretty_name']) for pn in path if pn not in out_g]
  if not networkx.is_connected(out_g):
    print "The graph is still not connected. Components: %s" % [[(n, in_g.node[n]['pretty_name']) for n in comp] for comp in networkx.connected_components(out_g)]
  return out_g