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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
//=======================================================================
// Copyright (c) 2018 Yi Ji
//
// 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/graph/max_cardinality_matching.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <iostream>
#include <fstream>
#include <sstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/core/lightweight_test.hpp>
using namespace boost;
typedef property< edge_weight_t, float, property< edge_index_t, int > >
EdgeProperty;
typedef adjacency_list< vecS, vecS, undirectedS,
property< vertex_index_t, int >, EdgeProperty >
undirected_graph;
typedef adjacency_list< listS, listS, undirectedS,
property< vertex_index_t, int >, EdgeProperty >
undirected_list_graph;
typedef adjacency_matrix< undirectedS, property< vertex_index_t, int >,
EdgeProperty >
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 print_graph(const Graph& g)
{
typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
edge_iterator_t ei, ei_end;
std::cout << std::endl << "The graph is: " << std::endl;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
std::cout << "add_edge(" << source(*ei, g) << ", " << target(*ei, g)
<< ", EdgeProperty(" << get(edge_weight, g, *ei) << "), );"
<< std::endl;
}
template < typename Graph >
void weighted_matching_test(const Graph& g,
typename property_traits< typename property_map< Graph,
edge_weight_t >::type >::value_type answer)
{
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;
mate_t mate(num_vertices(g));
maximum_weighted_matching(g, mate);
bool same_result = (matching_weight_sum(g, mate) == answer);
BOOST_TEST(same_result);
if (!same_result)
{
mate_t max_mate(num_vertices(g));
brute_force_maximum_weighted_matching(g, max_mate);
std::cout << std::endl
<< "Found a weighted matching of weight sum "
<< matching_weight_sum(g, mate) << std::endl
<< "While brute-force search found a weighted matching of "
"weight sum "
<< matching_weight_sum(g, max_mate) << std::endl;
typedef
typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
vertex_iterator_t vi, vi_end;
print_graph(g);
std::cout << std::endl << "The algorithmic matching is:" << std::endl;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (mate[*vi] != graph_traits< Graph >::null_vertex()
&& *vi < mate[*vi])
std::cout << "{" << *vi << ", " << mate[*vi] << "}"
<< std::endl;
std::cout << std::endl << "The brute-force matching is:" << std::endl;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (max_mate[*vi] != graph_traits< Graph >::null_vertex()
&& *vi < max_mate[*vi])
std::cout << "{" << *vi << ", " << max_mate[*vi] << "}"
<< std::endl;
std::cout << std::endl;
}
}
template < typename Graph >
Graph make_graph(typename graph_traits< Graph >::vertices_size_type num_v,
typename graph_traits< Graph >::edges_size_type num_e,
std::deque< std::size_t > input_edges)
{
Graph g(num_v);
vertex_index_installer< Graph >::install(g);
for (std::size_t i = 0; i < num_e; ++i)
{
std::size_t src_v, tgt_v, edge_weight;
src_v = input_edges.front();
input_edges.pop_front();
tgt_v = input_edges.front();
input_edges.pop_front();
edge_weight = input_edges.front();
input_edges.pop_front();
add_edge(
vertex(src_v, g), vertex(tgt_v, g), EdgeProperty(edge_weight), g);
}
return g;
}
int main(int, char*[])
{
std::ifstream in_file("weighted_matching.dat");
std::string line;
while (std::getline(in_file, line))
{
std::istringstream in_graph(line);
std::size_t answer, num_v, num_e;
in_graph >> answer >> num_v >> num_e;
std::deque< std::size_t > input_edges;
std::size_t i;
while (in_graph >> i)
input_edges.push_back(i);
weighted_matching_test(
make_graph< undirected_graph >(num_v, num_e, input_edges), answer);
weighted_matching_test(
make_graph< undirected_list_graph >(num_v, num_e, input_edges),
answer);
weighted_matching_test(make_graph< undirected_adjacency_matrix_graph >(
num_v, num_e, input_edges),
answer);
}
return boost::report_errors();
}
|
