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 test142_utility_graph(self):
     """ Larger utility graph from LCF notation. """
     g = nx.LCF_graph(60, [3, -3], 3)
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test142_utility_graph")
     self.assertEqual( len(mate1), len(mate2) )

 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 test103_lollipop_graph(self):
     """ Large lollipop graph. """
     g = nx.lollipop_graph(17, 11)
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test103_lollipop_graph")
     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 test090_singlebloom(self):
     """ Single bloom, two edge extensions, case 1. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5),(5,1),(3,6)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     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 test083_barabasi_albert_graph(self):
     """ Random graph using Barabasi-Albert preferential
     attachment model. """
     g = nx.barabasi_albert_graph(100, 5)
     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 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 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 test050_linear(self):
     """ Multiple edges, linear. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5),(5,6)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     self.assertEqual( len(mate1), len(mate2) )

 def test160_petersengraph(self):
     """ Petersen graph. """
     g = nx.petersen_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test160_petersengraph")
     self.assertEqual( len(mate1), len(mate2) )

 def test070_circle(self):
     """ Multiple edges, circle of even length. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)])
     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 test035_dense_gnm_random_graph(self):
     """ Larger random graph picked from set of all graphs 
     with n nodes and m edges. """
     g = nx.dense_gnm_random_graph(300, 10000)
     mate1 = mv.max_cardinality_matching(g)
     mate2 = nx.max_weight_matching(g, True)
     self.assertEqual(len(mate1), len(mate2))

 def test142_doublebloom(self):
     """ Two blooms, connected together by one edge. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,0),(3,6),(6,7),(7,8),(8,9),(9,10),(10,6)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test142_doublebloom")
     self.assertEqual( len(mate1), len(mate2) )

 def test220_fruchtgraph(self):
     """ Frucht graph, smallest cubical graph. """
     g = nx.frucht_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test220_fruchtgraph")
     td.showGraph(g, mate2, "test220_fruchtgraph_edmonds")
     self.assertEqual( len(mate1), len(mate2) )

 def test149_doublebloom(self):
     """ Two blooms, one embedded, connected at their centers. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,3),(4,6),(4,1),(3,4),(4,0),(3,7),(7,8),(8,9),(9,10),(10,3)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test149_doublebloom")
     self.assertEqual( len(mate1), len(mate2) )

 def test145_doublebloom(self):
     """ Two blooms, with three vertices, connected by one edge. """
     g = nx.Graph()
     g.add_edges_from([(0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3),(4,6),(6,7),(7,8),(8,6)])
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test145_doublebloom")
     self.assertEqual( len(mate1), len(mate2) )