1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//=======================================================================
// 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;
}
|
