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
19using namespace boost;
20
21typedef adjacency_list< vecS, vecS, undirectedS,
22 property< vertex_index_t, int > >
23 undirected_graph;
24
25typedef property_map< undirected_graph, vertex_index_t >::type
26 vertex_index_map_t;
27typedef vector_property_map<
28 graph_traits< undirected_graph >::vertex_descriptor, vertex_index_map_t >
29 mate_t;
30typedef graph_traits< undirected_graph >::vertex_iterator vertex_iterator_t;
31typedef graph_traits< undirected_graph >::vertex_descriptor vertex_descriptor_t;
32typedef graph_traits< undirected_graph >::vertices_size_type v_size_t;
33
34int 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

source code of boost/libs/graph/test/random_matching_test.cpp