1 | //======================================================================= |
2 | // Copyright (c) 2005 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. |
5 | // (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | // |
8 | //======================================================================= |
9 | #include <cstdlib> |
10 | #include <iostream> |
11 | #include <boost/property_map/vector_property_map.hpp> |
12 | #include <boost/graph/adjacency_list.hpp> |
13 | #include <boost/graph/random.hpp> |
14 | #include <ctime> |
15 | #include <boost/random.hpp> |
16 | |
17 | #include <boost/graph/max_cardinality_matching.hpp> |
18 | |
19 | using namespace boost; |
20 | |
21 | typedef adjacency_list< vecS, vecS, undirectedS, |
22 | property< vertex_index_t, int > > |
23 | undirected_graph; |
24 | |
25 | typedef property_map< undirected_graph, vertex_index_t >::type |
26 | vertex_index_map_t; |
27 | typedef vector_property_map< |
28 | graph_traits< undirected_graph >::vertex_descriptor, vertex_index_map_t > |
29 | mate_t; |
30 | typedef graph_traits< undirected_graph >::vertex_iterator vertex_iterator_t; |
31 | typedef graph_traits< undirected_graph >::vertex_descriptor vertex_descriptor_t; |
32 | typedef graph_traits< undirected_graph >::vertices_size_type v_size_t; |
33 | |
34 | int main(int argc, char** argv) |
35 | { |
36 | if (argc < 3) |
37 | { |
38 | std::cout << "Usage: " << argv[0] << " n m" << std::endl |
39 | << "Tests the checked matching on a random graph w/ n " |
40 | "vertices and m edges" |
41 | << std::endl; |
42 | exit(status: -1); |
43 | } |
44 | |
45 | int n = atoi(nptr: argv[1]); |
46 | int m = atoi(nptr: argv[2]); |
47 | |
48 | undirected_graph g(n); |
49 | |
50 | typedef boost::mt19937 base_generator_type; |
51 | base_generator_type generator(static_cast< unsigned int >(std::time(timer: 0))); |
52 | boost::uniform_int<> distribution(0, n - 1); |
53 | boost::variate_generator< base_generator_type&, boost::uniform_int<> > |
54 | rand_num(generator, distribution); |
55 | |
56 | int num_edges = 0; |
57 | bool success; |
58 | |
59 | while (num_edges < m) |
60 | { |
61 | vertex_descriptor_t u = random_vertex(g, gen&: rand_num); |
62 | vertex_descriptor_t v = random_vertex(g, gen&: rand_num); |
63 | if (u != v) |
64 | { |
65 | if (!edge(u, v, g_: g).second) |
66 | boost::tie(t0&: tuples::ignore, t1&: success) = add_edge(u, v, g_&: g); |
67 | else |
68 | success = false; |
69 | |
70 | if (success) |
71 | num_edges++; |
72 | } |
73 | } |
74 | |
75 | mate_t mate(n); |
76 | bool random_graph_result |
77 | = checked_edmonds_maximum_cardinality_matching(g, mate); |
78 | |
79 | if (!random_graph_result) |
80 | { |
81 | std::cout << "TEST 1 FAILED!!!" << std::endl << std::endl; |
82 | |
83 | std::cout << "Graph has edges: " ; |
84 | typedef graph_traits< undirected_graph >::edge_iterator edge_iterator_t; |
85 | edge_iterator_t ei, ei_end; |
86 | for (boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei) |
87 | std::cout << *ei << ", " ; |
88 | std::cout << std::endl; |
89 | |
90 | std::cout << "Matching is: " ; |
91 | vertex_iterator_t vi, vi_end; |
92 | for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi) |
93 | if (mate[*vi] != graph_traits< undirected_graph >::null_vertex() |
94 | && *vi < mate[*vi]) |
95 | std::cout << "{" << *vi << "," << mate[*vi] << "}, " ; |
96 | std::cout << std::endl; |
97 | } |
98 | |
99 | // Now remove an edge from the random_mate matching. |
100 | vertex_iterator_t vi, vi_end; |
101 | for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi) |
102 | if (mate[*vi] != graph_traits< undirected_graph >::null_vertex()) |
103 | break; |
104 | |
105 | mate[mate[*vi]] = graph_traits< undirected_graph >::null_vertex(); |
106 | mate[*vi] = graph_traits< undirected_graph >::null_vertex(); |
107 | |
108 | //...and run the matching verifier - it should tell us that the matching |
109 | // isn't a maximum matching. |
110 | bool modified_random_verification_result |
111 | = maximum_cardinality_matching_verifier< undirected_graph, mate_t, |
112 | vertex_index_map_t >::verify_matching(g, mate, |
113 | vm: get(p: vertex_index, g)); |
114 | |
115 | if (modified_random_verification_result) |
116 | { |
117 | std::cout << "TEST 2 FAILED!!!" << std::endl; |
118 | } |
119 | |
120 | // find a greedy matching on the graph |
121 | mate_t greedy_mate(n); |
122 | greedy_matching< undirected_graph, mate_t >::find_matching(g, mate: greedy_mate); |
123 | |
124 | if (matching_size(g, mate) > matching_size(g, mate: greedy_mate) |
125 | && maximum_cardinality_matching_verifier< undirected_graph, mate_t, |
126 | vertex_index_map_t >::verify_matching(g, mate: greedy_mate, |
127 | vm: get(p: vertex_index, g))) |
128 | std::cout << "TEST 3 FAILED!!!" << std::endl; |
129 | |
130 | return 0; |
131 | } |
132 | |