123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383 |
- //=======================================================================
- // 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/config.hpp>
- #ifdef BOOST_MSVC
- // Without disabling this we get hard errors about initialialized pointers:
- #pragma warning(disable:4703)
- #endif
- #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;
- 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;
- }
|