ceph/src/boost/libs/graph/test/weighted_matching_test.cpp

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