1 | //======================================================================= |
2 | // Copyright (c) 2018 Yi Ji |
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 | |
10 | #include <boost/graph/max_cardinality_matching.hpp> |
11 | #include <boost/graph/maximum_weighted_matching.hpp> |
12 | |
13 | #include <iostream> |
14 | #include <fstream> |
15 | #include <sstream> |
16 | #include <boost/graph/adjacency_list.hpp> |
17 | #include <boost/graph/adjacency_matrix.hpp> |
18 | #include <boost/core/lightweight_test.hpp> |
19 | |
20 | using namespace boost; |
21 | |
22 | typedef property< edge_weight_t, float, property< edge_index_t, int > > |
23 | EdgeProperty; |
24 | |
25 | typedef adjacency_list< vecS, vecS, undirectedS, |
26 | property< vertex_index_t, int >, EdgeProperty > |
27 | undirected_graph; |
28 | typedef adjacency_list< listS, listS, undirectedS, |
29 | property< vertex_index_t, int >, EdgeProperty > |
30 | undirected_list_graph; |
31 | typedef adjacency_matrix< undirectedS, property< vertex_index_t, int >, |
32 | EdgeProperty > |
33 | undirected_adjacency_matrix_graph; |
34 | |
35 | template < typename Graph > struct vertex_index_installer |
36 | { |
37 | static void install(Graph&) {} |
38 | }; |
39 | |
40 | template <> struct vertex_index_installer< undirected_list_graph > |
41 | { |
42 | static void install(undirected_list_graph& g) |
43 | { |
44 | typedef graph_traits< undirected_list_graph >::vertex_iterator |
45 | vertex_iterator_t; |
46 | typedef graph_traits< undirected_list_graph >::vertices_size_type |
47 | v_size_t; |
48 | |
49 | vertex_iterator_t vi, vi_end; |
50 | v_size_t i = 0; |
51 | for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi, ++i) |
52 | put(p: vertex_index, g, key: *vi, value: i); |
53 | } |
54 | }; |
55 | |
56 | template < typename Graph > void print_graph(const Graph& g) |
57 | { |
58 | typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t; |
59 | edge_iterator_t ei, ei_end; |
60 | std::cout << std::endl << "The graph is: " << std::endl; |
61 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) |
62 | std::cout << "add_edge(" << source(*ei, g) << ", " << target(*ei, g) |
63 | << ", EdgeProperty(" << get(edge_weight, g, *ei) << "), );" |
64 | << std::endl; |
65 | } |
66 | |
67 | template < typename Graph > |
68 | void weighted_matching_test(const Graph& g, |
69 | typename property_traits< typename property_map< Graph, |
70 | edge_weight_t >::type >::value_type answer) |
71 | { |
72 | typedef |
73 | typename property_map< Graph, vertex_index_t >::type vertex_index_map_t; |
74 | typedef vector_property_map< |
75 | typename graph_traits< Graph >::vertex_descriptor, vertex_index_map_t > |
76 | mate_t; |
77 | mate_t mate(num_vertices(g)); |
78 | maximum_weighted_matching(g, mate); |
79 | bool same_result = (matching_weight_sum(g, mate) == answer); |
80 | BOOST_TEST(same_result); |
81 | if (!same_result) |
82 | { |
83 | mate_t max_mate(num_vertices(g)); |
84 | brute_force_maximum_weighted_matching(g, max_mate); |
85 | |
86 | std::cout << std::endl |
87 | << "Found a weighted matching of weight sum " |
88 | << matching_weight_sum(g, mate) << std::endl |
89 | << "While brute-force search found a weighted matching of " |
90 | "weight sum " |
91 | << matching_weight_sum(g, max_mate) << std::endl; |
92 | |
93 | typedef |
94 | typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; |
95 | vertex_iterator_t vi, vi_end; |
96 | |
97 | print_graph(g); |
98 | |
99 | std::cout << std::endl << "The algorithmic matching is:" << std::endl; |
100 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
101 | if (mate[*vi] != graph_traits< Graph >::null_vertex() |
102 | && *vi < mate[*vi]) |
103 | std::cout << "{" << *vi << ", " << mate[*vi] << "}" |
104 | << std::endl; |
105 | |
106 | std::cout << std::endl << "The brute-force matching is:" << std::endl; |
107 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
108 | if (max_mate[*vi] != graph_traits< Graph >::null_vertex() |
109 | && *vi < max_mate[*vi]) |
110 | std::cout << "{" << *vi << ", " << max_mate[*vi] << "}" |
111 | << std::endl; |
112 | |
113 | std::cout << std::endl; |
114 | } |
115 | } |
116 | |
117 | template < typename Graph > |
118 | Graph make_graph(typename graph_traits< Graph >::vertices_size_type num_v, |
119 | typename graph_traits< Graph >::edges_size_type num_e, |
120 | std::deque< std::size_t > input_edges) |
121 | { |
122 | Graph g(num_v); |
123 | vertex_index_installer< Graph >::install(g); |
124 | for (std::size_t i = 0; i < num_e; ++i) |
125 | { |
126 | std::size_t src_v, tgt_v, edge_weight; |
127 | src_v = input_edges.front(); |
128 | input_edges.pop_front(); |
129 | tgt_v = input_edges.front(); |
130 | input_edges.pop_front(); |
131 | edge_weight = input_edges.front(); |
132 | input_edges.pop_front(); |
133 | add_edge( |
134 | vertex(src_v, g), vertex(tgt_v, g), EdgeProperty(edge_weight), g); |
135 | } |
136 | return g; |
137 | } |
138 | |
139 | int main(int, char*[]) |
140 | { |
141 | std::ifstream in_file("weighted_matching.dat" ); |
142 | std::string line; |
143 | while (std::getline(is&: in_file, str&: line)) |
144 | { |
145 | std::istringstream in_graph(line); |
146 | std::size_t answer, num_v, num_e; |
147 | in_graph >> answer >> num_v >> num_e; |
148 | |
149 | std::deque< std::size_t > input_edges; |
150 | std::size_t i; |
151 | while (in_graph >> i) |
152 | input_edges.push_back(x: i); |
153 | |
154 | weighted_matching_test( |
155 | g: make_graph< undirected_graph >(num_v, num_e, input_edges), answer); |
156 | weighted_matching_test( |
157 | g: make_graph< undirected_list_graph >(num_v, num_e, input_edges), |
158 | answer); |
159 | weighted_matching_test(g: make_graph< undirected_adjacency_matrix_graph >( |
160 | num_v, num_e, input_edges), |
161 | answer); |
162 | } |
163 | return boost::report_errors(); |
164 | } |
165 | |