| //======================================================================= |
| // 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 <cstdlib> |
| #include <iostream> |
| #include <boost/property_map/vector_property_map.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/random.hpp> |
| #include <ctime> |
| #include <boost/random.hpp> |
| |
| #include <boost/graph/max_cardinality_matching.hpp> |
| |
| using namespace boost; |
| |
| typedef adjacency_list<vecS, |
| vecS, |
| undirectedS, |
| property<vertex_index_t, int> > undirected_graph; |
| |
| typedef property_map<undirected_graph,vertex_index_t>::type vertex_index_map_t; |
| typedef vector_property_map<graph_traits<undirected_graph>::vertex_descriptor, vertex_index_map_t > mate_t; |
| typedef graph_traits<undirected_graph>::vertex_iterator vertex_iterator_t; |
| typedef graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor_t; |
| typedef graph_traits<undirected_graph>::vertices_size_type v_size_t; |
| |
| |
| int main(int argc, char** argv) |
| { |
| if (argc < 3) |
| { |
| std::cout << "Usage: " << argv[0] << " n m" << std::endl |
| << "Tests the checked matching on a random graph w/ n vertices and m edges" << std::endl; |
| exit(-1); |
| } |
| |
| int n = atoi(argv[1]); |
| int m = atoi(argv[2]); |
| |
| undirected_graph g(n); |
| |
| |
| typedef boost::mt19937 base_generator_type; |
| base_generator_type generator(static_cast<unsigned int>(std::time(0))); |
| boost::uniform_int<> distribution(0, n-1); |
| boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution); |
| |
| int num_edges = 0; |
| bool success; |
| |
| while (num_edges < m) |
| { |
| vertex_descriptor_t u = random_vertex(g,rand_num); |
| vertex_descriptor_t v = random_vertex(g,rand_num); |
| if (u != v) |
| { |
| if (!edge(u,v,g).second) |
| boost::tie(tuples::ignore, success) = add_edge(u, v, g); |
| else |
| success = false; |
| |
| if (success) |
| num_edges++; |
| } |
| } |
| |
| mate_t mate(n); |
| bool random_graph_result = checked_edmonds_maximum_cardinality_matching(g,mate); |
| |
| if (!random_graph_result) |
| { |
| std::cout << "TEST 1 FAILED!!!" << std::endl << std::endl; |
| |
| std::cout << "Graph has edges: "; |
| typedef graph_traits<undirected_graph>::edge_iterator edge_iterator_t; |
| edge_iterator_t ei,ei_end; |
| for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) |
| std:: cout << *ei << ", "; |
| std::cout << std::endl; |
| |
| std::cout << "Matching is: "; |
| vertex_iterator_t vi, vi_end; |
| for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
| if (mate[*vi] != graph_traits<undirected_graph>::null_vertex() && |
| *vi < mate[*vi]) |
| std::cout << "{" << *vi << "," << mate[*vi] << "}, "; |
| std::cout << std::endl; |
| } |
| |
| //Now remove an edge from the random_mate matching. |
| vertex_iterator_t vi, vi_end; |
| for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
| if (mate[*vi] != graph_traits<undirected_graph>::null_vertex()) |
| break; |
| |
| mate[mate[*vi]] = graph_traits<undirected_graph>::null_vertex(); |
| mate[*vi] = graph_traits<undirected_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<undirected_graph,mate_t,vertex_index_map_t>::verify_matching(g,mate,get(vertex_index,g)); |
| |
| if (modified_random_verification_result) |
| { |
| std::cout << "TEST 2 FAILED!!!" << std::endl; |
| } |
| |
| //find a greedy matching on the graph |
| mate_t greedy_mate(n); |
| greedy_matching<undirected_graph, mate_t>::find_matching(g,greedy_mate); |
| |
| if (matching_size(g,mate) > matching_size(g,greedy_mate) && |
| maximum_cardinality_matching_verifier<undirected_graph,mate_t,vertex_index_map_t>::verify_matching(g,greedy_mate,get(vertex_index,g))) |
| std::cout << "TEST 3 FAILED!!!" << std::endl; |
| |
| return 0; |
| } |
| |