test case

gistfile1.hpp

//=======================================================================
// 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, int, 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)
{
    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);
    mate_t max_mate(num_vertices(g));
    brute_force_maximum_weighted_matching(g, max_mate);
    const bool same_result = (matching_weight_sum(g, mate) == matching_weight_sum(g, max_mate));
    BOOST_TEST(same_result);
    if (!same_result)
    { 
        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;
    }
}

undirected_graph test_case_2()
{
    graph_traits< undirected_graph >::vertex_iterator vi, vi_end;
    const int n_vertices = 8;
    undirected_graph g(n_vertices);

    add_edge(0, 5, EdgeProperty(21), g);
    add_edge(1, 4, EdgeProperty(5), g);
    add_edge(1, 5, EdgeProperty(34), g);
    add_edge(1, 6, EdgeProperty(46), g);
    add_edge(2, 7, EdgeProperty(42), g);
    add_edge(2, 6, EdgeProperty(10), g);
    add_edge(3, 6, EdgeProperty(36), g);
    add_edge(3, 7, EdgeProperty(37), g);

    return g;
}

int main(int, char*[])
{
    weighted_matching_test(test_case_2());
    return boost::report_errors();
}