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 {
installvertex_index_installer37 static void install(Graph&) {}
38 };
39
40 template <> struct vertex_index_installer< undirected_list_graph >
41 {
installvertex_index_installer42 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(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
52 put(vertex_index, g, *vi, i);
53 }
54 };
55
print_graph(const Graph & g)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 >
weighted_matching_test(const Graph & g,typename property_traits<typename property_map<Graph,edge_weight_t>::type>::value_type answer)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 >
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)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
main(int,char * [])139 int main(int, char*[])
140 {
141 std::ifstream in_file("weighted_matching.dat");
142 std::string line;
143 while (std::getline(in_file, 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(i);
153
154 weighted_matching_test(
155 make_graph< undirected_graph >(num_v, num_e, input_edges), answer);
156 weighted_matching_test(
157 make_graph< undirected_list_graph >(num_v, num_e, input_edges),
158 answer);
159 weighted_matching_test(make_graph< undirected_adjacency_matrix_graph >(
160 num_v, num_e, input_edges),
161 answer);
162 }
163 return boost::report_errors();
164 }
165