boost_1_45_0/libs/graph/test/matching_test.cpp - nest-learning-thermostat/5.0/boost - Git at Google

 //=======================================================================
 // Copyright (c) 2005 Aaron Windsor
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 //
 //=======================================================================

 #include <boost/graph/max_cardinality_matching.hpp>

 #include <iostream>                      // for std::cout
 #include <boost/property_map/vector_property_map.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/adjacency_matrix.hpp>
 #include <boost/graph/random.hpp>
 #include <ctime>
 #include <boost/random.hpp>
 #include <boost/test/minimal.hpp>

 using namespace boost;

 typedef adjacency_list<vecS,
                        vecS,
                        undirectedS,
                        property<vertex_index_t, int> >  undirected_graph;

 typedef adjacency_list<listS,
                        listS,
                        undirectedS,
                        property<vertex_index_t, int> >  undirected_list_graph;

 typedef adjacency_matrix<undirectedS,
                          property<vertex_index_t,int> > undirected_adjacency_matrix_graph;


 template <typename Graph>
 struct vertex_index_installer
 {
   static void install(Graph&) {}
 };


 template <>
 struct vertex_index_installer<undirected_list_graph>
 {
   static void install(undirected_list_graph& g)
   {
     typedef graph_traits<undirected_list_graph>::vertex_iterator vertex_iterator_t;
     typedef graph_traits<undirected_list_graph>::vertices_size_type v_size_t;

     vertex_iterator_t vi, vi_end;
     v_size_t i = 0;
     for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
       put(vertex_index, g, *vi, i);
   }
 };


 template <typename Graph>
 void complete_graph(Graph& g, int n)
 {
   //creates the complete graph on n vertices
   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;

   g = Graph(n);
   vertex_iterator_t vi, vi_end, wi;
   boost::tie(vi,vi_end) = vertices(g);
   for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
     {
       wi = vi;
       ++wi;
       for(; wi != vi_end; ++wi)
         add_edge(*vi,*wi,g);
     }
 }


 template <typename Graph>
 void gabows_graph(Graph& g, int n)
 {
   //creates a graph with 2n vertices, consisting of the complete graph
   //on n vertices plus n vertices of degree one, each adjacent to one
   //vertex in the complete graph. without any initial matching, this
   //graph forces edmonds' algorithm into worst-case behavior.

   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;

   g = Graph(2* n);

   vertex_iterator_t vi, vi_end, ui, ui_end, halfway;

   boost::tie(ui,ui_end) = vertices(g);

   halfway = ui;
   for(int i = 0; i < n; ++i)
     ++halfway;


   while(ui != halfway)
     {
       vi = ui;
       ++vi;
       while (vi != halfway)
         {
           add_edge(*ui,*vi,g);
           ++vi;
         }
       ++ui;
     }

   boost::tie(ui,ui_end) = vertices(g);

   while(halfway != ui_end)
     {
       add_edge(*ui, *halfway, g);
       ++ui;
       ++halfway;
     }

 }


 template <typename Graph>
 void matching_test(std::size_t num_v, const std::string& graph_name)
 {
   typedef typename property_map<Graph,vertex_index_t>::type vertex_index_map_t;
   typedef vector_property_map< typename graph_traits<Graph>::vertex_descriptor, vertex_index_map_t > mate_t;
   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
   typedef typename graph_traits<Graph>::vertices_size_type v_size_t;

   const std::size_t double_num_v = num_v * 2;

   bool all_tests_passed = true;

   //form the complete graph on 2*n vertices; the maximum cardinality matching, greedy matching,
   //and extra greedy matching should all be the same - a matching of size n.

   Graph g(double_num_v);
   complete_graph(g,double_num_v);

   vertex_index_installer<Graph>::install(g);

   mate_t edmonds_mate(double_num_v);
   mate_t greedy_mate(double_num_v);
   mate_t extra_greedy_mate(double_num_v);

   //find a maximum cardinality matching using edmonds' blossom-shrinking algorithm, starting
   //with an empty matching.
   bool edmonds_result =
     matching < Graph, mate_t, vertex_index_map_t,
                edmonds_augmenting_path_finder, empty_matching, maximum_cardinality_matching_verifier>
     (g,edmonds_mate, get(vertex_index,g));

   BOOST_CHECK (edmonds_result);
   if (!edmonds_result)
     {
       std::cout << "Verifier reporting a problem finding a perfect matching on" << std::endl
                 << "the complete graph using " << graph_name << std::endl;
       all_tests_passed = false;
     }

   //find a greedy matching
   bool greedy_result =
     matching<Graph, mate_t, vertex_index_map_t,
              no_augmenting_path_finder, greedy_matching, maximum_cardinality_matching_verifier>
     (g,greedy_mate, get(vertex_index,g));

   BOOST_CHECK (greedy_result);
   if (!greedy_result)
     {
       std::cout << "Verifier reporting a problem finding a greedy matching on" << std::endl
                 << "the complete graph using " << graph_name << std::endl;
       all_tests_passed = false;
     }

   //find an extra greedy matching
   bool extra_greedy_result =
     matching<Graph, mate_t, vertex_index_map_t,
              no_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
     (g,extra_greedy_mate,get(vertex_index,g));

   BOOST_CHECK (extra_greedy_result);
   if (!extra_greedy_result)
     {
       std::cout << "Verifier reporting a problem finding an extra greedy matching on" << std::endl
                 << "the complete graph using " << graph_name << std::endl;
       all_tests_passed = false;
     }

   //as a sanity check, make sure that each of the matchings returned is a valid matching and has
   //1000 edges.

   bool edmonds_sanity_check =
     is_a_matching(g,edmonds_mate) && matching_size(g,edmonds_mate) == num_v;

   BOOST_CHECK (edmonds_sanity_check);
   if (edmonds_result && !edmonds_sanity_check)
     {
       std::cout << "Verifier okayed edmonds' algorithm on the complete graph, but" << std::endl
                 << "the matching returned either wasn't a valid matching or wasn't" << std::endl
                 << "actually a maximum cardinality matching." << std::endl;
       all_tests_passed = false;
     }

   bool greedy_sanity_check =
     is_a_matching(g,greedy_mate) && matching_size(g,greedy_mate) == num_v;

   BOOST_CHECK (greedy_sanity_check);
   if (greedy_result && !greedy_sanity_check)
     {
       std::cout << "Verifier okayed greedy algorithm on the complete graph, but" << std::endl
                 << "the matching returned either wasn't a valid matching or wasn't" << std::endl
                 << "actually a maximum cardinality matching." << std::endl;
       all_tests_passed = false;
     }

   bool extra_greedy_sanity_check =
     is_a_matching(g,extra_greedy_mate) && matching_size(g,extra_greedy_mate) == num_v;

   BOOST_CHECK (extra_greedy_sanity_check);
   if (extra_greedy_result && !extra_greedy_sanity_check)
     {
       std::cout << "Verifier okayed extra greedy algorithm on the complete graph, but" << std::endl
                 << "the matching returned either wasn't a valid matching or wasn't" << std::endl
                 << "actually a maximum cardinality matching." << std::endl;
       all_tests_passed = false;
     }

   //Now remove an edge from the edmonds_mate matching.
   vertex_iterator_t vi,vi_end;
   for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
     if (edmonds_mate[*vi] != graph_traits<Graph>::null_vertex())
       break;

   edmonds_mate[edmonds_mate[*vi]] = graph_traits<Graph>::null_vertex();
   edmonds_mate[*vi] = graph_traits<Graph>::null_vertex();

   //...and run the matching verifier - it should tell us that the matching isn't
   //a maximum matching.
   bool modified_edmonds_verification_result =
     maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(g,edmonds_mate,get(vertex_index,g));

   BOOST_CHECK (!modified_edmonds_verification_result);
   if (modified_edmonds_verification_result)
     {
       std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
       all_tests_passed = false;
     }

   Graph h(double_num_v);
   gabows_graph(h,num_v);

   vertex_index_installer<Graph>::install(h);

   //gabow's graph always has a perfect matching. it's also a good example of why
   //one should initialize with the extra_greedy_matching in most cases.

   mate_t gabow_mate(double_num_v);

   bool gabows_graph_result = checked_edmonds_maximum_cardinality_matching(h,gabow_mate);

   BOOST_CHECK (gabows_graph_result);
   if (!gabows_graph_result)
     {
       std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
                 << "   Verifier reporting a maximum cardinality matching not found." << std::endl;
       all_tests_passed = false;
     }

   BOOST_CHECK (matching_size(h,gabow_mate) == num_v);
   if (gabows_graph_result && matching_size(h,gabow_mate) != num_v)
     {
       std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
                 << "   Verifier reported a maximum cardinality matching found," << std::endl
                 << "   but matching size is " << matching_size(h,gabow_mate)
                 << " when it should be " << num_v << std::endl;
       all_tests_passed = false;
     }

   Graph j(double_num_v);
   vertex_index_installer<Graph>::install(j);

   typedef boost::mt19937 base_generator_type;
   base_generator_type generator(static_cast<unsigned int>(std::time(0)));
   boost::uniform_int<> distribution(0, double_num_v-1);
   boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution);

   std::size_t num_edges = 0;
   bool success;

   while (num_edges < 4*double_num_v)
     {
       vertex_descriptor_t u = random_vertex(j,rand_num);
       vertex_descriptor_t v = random_vertex(j,rand_num);
       if (u != v)
         {
           boost::tie(tuples::ignore, success) = add_edge(u, v, j);
           if (success)
             num_edges++;
         }
     }

   mate_t random_mate(double_num_v);
   bool random_graph_result = checked_edmonds_maximum_cardinality_matching(j,random_mate);

   BOOST_CHECK(random_graph_result);
   if (!random_graph_result)
     {
       std::cout << "Matching in random graph not maximum for " << graph_name << std::endl;
       all_tests_passed = false;
     }

   //Now remove an edge from the random_mate matching.
   for(boost::tie(vi,vi_end) = vertices(j); vi != vi_end; ++vi)
     if (random_mate[*vi] != graph_traits<Graph>::null_vertex())
       break;

   random_mate[random_mate[*vi]] = graph_traits<Graph>::null_vertex();
   random_mate[*vi] = graph_traits<Graph>::null_vertex();

   //...and run the matching verifier - it should tell us that the matching isn't
   //a maximum matching.
   bool modified_random_verification_result =
     maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(j,random_mate,get(vertex_index,j));

   BOOST_CHECK(!modified_random_verification_result);
   if (modified_random_verification_result)
     {
       std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
       all_tests_passed = false;
     }

   BOOST_CHECK(all_tests_passed);
   if (all_tests_passed)
     {
       std::cout << graph_name << " passed all tests for n = " << num_v << '.' << std::endl;
     }

 }


 int test_main(int, char*[])
 {

   matching_test<undirected_graph>(10, "adjacency_list (using vectors)");
   matching_test<undirected_list_graph>(10, "adjacency_list (using lists)");
   matching_test<undirected_adjacency_matrix_graph>(10, "adjacency_matrix");

   matching_test<undirected_graph>(20, "adjacency_list (using vectors)");
   matching_test<undirected_list_graph>(20, "adjacency_list (using lists)");
   matching_test<undirected_adjacency_matrix_graph>(20, "adjacency_matrix");

   matching_test<undirected_graph>(21, "adjacency_list (using vectors)");
   matching_test<undirected_list_graph>(21, "adjacency_list (using lists)");
   matching_test<undirected_adjacency_matrix_graph>(21, "adjacency_matrix");

 #if 0
   matching_test<undirected_graph>(50, "adjacency_list (using vectors)");
   matching_test<undirected_list_graph>(50, "adjacency_list (using lists)");
   matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix");

   matching_test<undirected_graph>(51, "adjacency_list (using vectors)");
   matching_test<undirected_list_graph>(51, "adjacency_list (using lists)");
   matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix");
 #endif

   return 0;
 }
	//=======================================================================
	// Copyright (c) 2005 Aaron Windsor
	//
	// Distributed under the Boost Software License, Version 1.0.
	// (See accompanying file LICENSE_1_0.txt or copy at
	// http://www.boost.org/LICENSE_1_0.txt)
	//
	//=======================================================================

	#include <boost/graph/max_cardinality_matching.hpp>

	#include <iostream> // for std::cout
	#include <boost/property_map/vector_property_map.hpp>
	#include <boost/graph/adjacency_list.hpp>
	#include <boost/graph/adjacency_matrix.hpp>
	#include <boost/graph/random.hpp>
	#include <ctime>
	#include <boost/random.hpp>
	#include <boost/test/minimal.hpp>

	using namespace boost;

	typedef adjacency_list<vecS,
	vecS,
	undirectedS,
	property<vertex_index_t, int> > undirected_graph;

	typedef adjacency_list<listS,
	listS,
	undirectedS,
	property<vertex_index_t, int> > undirected_list_graph;

	typedef adjacency_matrix<undirectedS,
	property<vertex_index_t,int> > undirected_adjacency_matrix_graph;


	template <typename Graph>
	struct vertex_index_installer
	{
	static void install(Graph&) {}
	};


	template <>
	struct vertex_index_installer<undirected_list_graph>
	{
	static void install(undirected_list_graph& g)
	{
	typedef graph_traits<undirected_list_graph>::vertex_iterator vertex_iterator_t;
	typedef graph_traits<undirected_list_graph>::vertices_size_type v_size_t;

	vertex_iterator_t vi, vi_end;
	v_size_t i = 0;
	for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
	put(vertex_index, g, *vi, i);
	}
	};



	template <typename Graph>
	void complete_graph(Graph& g, int n)
	{
	//creates the complete graph on n vertices
	typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;

	g = Graph(n);
	vertex_iterator_t vi, vi_end, wi;
	boost::tie(vi,vi_end) = vertices(g);
	for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
	{
	wi = vi;
	++wi;
	for(; wi != vi_end; ++wi)
	add_edge(vi,wi,g);
	}
	}



	template <typename Graph>
	void gabows_graph(Graph& g, int n)
	{
	//creates a graph with 2n vertices, consisting of the complete graph
	//on n vertices plus n vertices of degree one, each adjacent to one
	//vertex in the complete graph. without any initial matching, this
	//graph forces edmonds' algorithm into worst-case behavior.

	typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;

	g = Graph(2* n);

	vertex_iterator_t vi, vi_end, ui, ui_end, halfway;

	boost::tie(ui,ui_end) = vertices(g);

	halfway = ui;
	for(int i = 0; i < n; ++i)
	++halfway;


	while(ui != halfway)
	{
	vi = ui;
	++vi;
	while (vi != halfway)
	{
	add_edge(ui,vi,g);
	++vi;
	}
	++ui;
	}

	boost::tie(ui,ui_end) = vertices(g);

	while(halfway != ui_end)
	{
	add_edge(ui, halfway, g);
	++ui;
	++halfway;
	}

	}



	template <typename Graph>
	void matching_test(std::size_t num_v, const std::string& graph_name)
	{
	typedef typename property_map<Graph,vertex_index_t>::type vertex_index_map_t;
	typedef vector_property_map< typename graph_traits<Graph>::vertex_descriptor, vertex_index_map_t > mate_t;
	typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
	typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
	typedef typename graph_traits<Graph>::vertices_size_type v_size_t;

	const std::size_t double_num_v = num_v * 2;

	bool all_tests_passed = true;

	//form the complete graph on 2*n vertices; the maximum cardinality matching, greedy matching,
	//and extra greedy matching should all be the same - a matching of size n.

	Graph g(double_num_v);
	complete_graph(g,double_num_v);

	vertex_index_installer<Graph>::install(g);

	mate_t edmonds_mate(double_num_v);
	mate_t greedy_mate(double_num_v);
	mate_t extra_greedy_mate(double_num_v);

	//find a maximum cardinality matching using edmonds' blossom-shrinking algorithm, starting
	//with an empty matching.
	bool edmonds_result =
	matching < Graph, mate_t, vertex_index_map_t,
	edmonds_augmenting_path_finder, empty_matching, maximum_cardinality_matching_verifier>
	(g,edmonds_mate, get(vertex_index,g));

	BOOST_CHECK (edmonds_result);
	if (!edmonds_result)
	{
	std::cout << "Verifier reporting a problem finding a perfect matching on" << std::endl
	<< "the complete graph using " << graph_name << std::endl;
	all_tests_passed = false;
	}

	//find a greedy matching
	bool greedy_result =
	matching<Graph, mate_t, vertex_index_map_t,
	no_augmenting_path_finder, greedy_matching, maximum_cardinality_matching_verifier>
	(g,greedy_mate, get(vertex_index,g));

	BOOST_CHECK (greedy_result);
	if (!greedy_result)
	{
	std::cout << "Verifier reporting a problem finding a greedy matching on" << std::endl
	<< "the complete graph using " << graph_name << std::endl;
	all_tests_passed = false;
	}

	//find an extra greedy matching
	bool extra_greedy_result =
	matching<Graph, mate_t, vertex_index_map_t,
	no_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
	(g,extra_greedy_mate,get(vertex_index,g));

	BOOST_CHECK (extra_greedy_result);
	if (!extra_greedy_result)
	{
	std::cout << "Verifier reporting a problem finding an extra greedy matching on" << std::endl
	<< "the complete graph using " << graph_name << std::endl;
	all_tests_passed = false;
	}

	//as a sanity check, make sure that each of the matchings returned is a valid matching and has
	//1000 edges.

	bool edmonds_sanity_check =
	is_a_matching(g,edmonds_mate) && matching_size(g,edmonds_mate) == num_v;

	BOOST_CHECK (edmonds_sanity_check);
	if (edmonds_result && !edmonds_sanity_check)
	{
	std::cout << "Verifier okayed edmonds' algorithm on the complete graph, but" << std::endl
	<< "the matching returned either wasn't a valid matching or wasn't" << std::endl
	<< "actually a maximum cardinality matching." << std::endl;
	all_tests_passed = false;
	}

	bool greedy_sanity_check =
	is_a_matching(g,greedy_mate) && matching_size(g,greedy_mate) == num_v;

	BOOST_CHECK (greedy_sanity_check);
	if (greedy_result && !greedy_sanity_check)
	{
	std::cout << "Verifier okayed greedy algorithm on the complete graph, but" << std::endl
	<< "the matching returned either wasn't a valid matching or wasn't" << std::endl
	<< "actually a maximum cardinality matching." << std::endl;
	all_tests_passed = false;
	}

	bool extra_greedy_sanity_check =
	is_a_matching(g,extra_greedy_mate) && matching_size(g,extra_greedy_mate) == num_v;

	BOOST_CHECK (extra_greedy_sanity_check);
	if (extra_greedy_result && !extra_greedy_sanity_check)
	{
	std::cout << "Verifier okayed extra greedy algorithm on the complete graph, but" << std::endl
	<< "the matching returned either wasn't a valid matching or wasn't" << std::endl
	<< "actually a maximum cardinality matching." << std::endl;
	all_tests_passed = false;
	}

	//Now remove an edge from the edmonds_mate matching.
	vertex_iterator_t vi,vi_end;
	for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
	if (edmonds_mate[*vi] != graph_traits<Graph>::null_vertex())
	break;

	edmonds_mate[edmonds_mate[*vi]] = graph_traits<Graph>::null_vertex();
	edmonds_mate[*vi] = graph_traits<Graph>::null_vertex();

	//...and run the matching verifier - it should tell us that the matching isn't
	//a maximum matching.
	bool modified_edmonds_verification_result =
	maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(g,edmonds_mate,get(vertex_index,g));

	BOOST_CHECK (!modified_edmonds_verification_result);
	if (modified_edmonds_verification_result)
	{
	std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
	all_tests_passed = false;
	}

	Graph h(double_num_v);
	gabows_graph(h,num_v);

	vertex_index_installer<Graph>::install(h);

	//gabow's graph always has a perfect matching. it's also a good example of why
	//one should initialize with the extra_greedy_matching in most cases.

	mate_t gabow_mate(double_num_v);

	bool gabows_graph_result = checked_edmonds_maximum_cardinality_matching(h,gabow_mate);

	BOOST_CHECK (gabows_graph_result);
	if (!gabows_graph_result)
	{
	std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
	<< " Verifier reporting a maximum cardinality matching not found." << std::endl;
	all_tests_passed = false;
	}

	BOOST_CHECK (matching_size(h,gabow_mate) == num_v);
	if (gabows_graph_result && matching_size(h,gabow_mate) != num_v)
	{
	std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
	<< " Verifier reported a maximum cardinality matching found," << std::endl
	<< " but matching size is " << matching_size(h,gabow_mate)
	<< " when it should be " << num_v << std::endl;
	all_tests_passed = false;
	}

	Graph j(double_num_v);
	vertex_index_installer<Graph>::install(j);

	typedef boost::mt19937 base_generator_type;
	base_generator_type generator(static_cast<unsigned int>(std::time(0)));
	boost::uniform_int<> distribution(0, double_num_v-1);
	boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution);

	std::size_t num_edges = 0;
	bool success;

	while (num_edges < 4*double_num_v)
	{
	vertex_descriptor_t u = random_vertex(j,rand_num);
	vertex_descriptor_t v = random_vertex(j,rand_num);
	if (u != v)
	{
	boost::tie(tuples::ignore, success) = add_edge(u, v, j);
	if (success)
	num_edges++;
	}
	}

	mate_t random_mate(double_num_v);
	bool random_graph_result = checked_edmonds_maximum_cardinality_matching(j,random_mate);

	BOOST_CHECK(random_graph_result);
	if (!random_graph_result)
	{
	std::cout << "Matching in random graph not maximum for " << graph_name << std::endl;
	all_tests_passed = false;
	}

	//Now remove an edge from the random_mate matching.
	for(boost::tie(vi,vi_end) = vertices(j); vi != vi_end; ++vi)
	if (random_mate[*vi] != graph_traits<Graph>::null_vertex())
	break;

	random_mate[random_mate[*vi]] = graph_traits<Graph>::null_vertex();
	random_mate[*vi] = graph_traits<Graph>::null_vertex();

	//...and run the matching verifier - it should tell us that the matching isn't
	//a maximum matching.
	bool modified_random_verification_result =
	maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(j,random_mate,get(vertex_index,j));

	BOOST_CHECK(!modified_random_verification_result);
	if (modified_random_verification_result)
	{
	std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
	all_tests_passed = false;
	}

	BOOST_CHECK(all_tests_passed);
	if (all_tests_passed)
	{
	std::cout << graph_name << " passed all tests for n = " << num_v << '.' << std::endl;
	}

	}




	int test_main(int, char*[])
	{

	matching_test<undirected_graph>(10, "adjacency_list (using vectors)");
	matching_test<undirected_list_graph>(10, "adjacency_list (using lists)");
	matching_test<undirected_adjacency_matrix_graph>(10, "adjacency_matrix");

	matching_test<undirected_graph>(20, "adjacency_list (using vectors)");
	matching_test<undirected_list_graph>(20, "adjacency_list (using lists)");
	matching_test<undirected_adjacency_matrix_graph>(20, "adjacency_matrix");

	matching_test<undirected_graph>(21, "adjacency_list (using vectors)");
	matching_test<undirected_list_graph>(21, "adjacency_list (using lists)");
	matching_test<undirected_adjacency_matrix_graph>(21, "adjacency_matrix");

	#if 0
	matching_test<undirected_graph>(50, "adjacency_list (using vectors)");
	matching_test<undirected_list_graph>(50, "adjacency_list (using lists)");
	matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix");

	matching_test<undirected_graph>(51, "adjacency_list (using vectors)");
	matching_test<undirected_list_graph>(51, "adjacency_list (using lists)");
	matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix");
	#endif

	return 0;
	}