boost/libs/graph/test/matching_test.cpp

//=======================================================================
// Copyright (c) 2005 Aaron Windsor
//
// 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/config.hpp>

#ifdef BOOST_MSVC
// Without disabling this we get hard errors about initialialized pointers:
#pragma warning(disable : 4703)
#endif

#include <boost/graph/max_cardinality_matching.hpp>

#include <iostream> // for std::cout
#include <boost/property_map/vector_property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/random.hpp>
#include <ctime>
#include <boost/random.hpp>
#include <boost/core/lightweight_test.hpp>

using namespace boost;

typedef adjacency_list< vecS, vecS, undirectedS,
    property< vertex_index_t, int > >
    undirected_graph;

typedef adjacency_list< listS, listS, undirectedS,
    property< vertex_index_t, int > >
    undirected_list_graph;

typedef adjacency_matrix< undirectedS, property< vertex_index_t, int > >
    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 complete_graph(Graph& g, int n)
{
    // creates the complete graph on n vertices
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;

    g = Graph(n);
    vertex_iterator_t vi, vi_end, wi;
    boost::tie(vi, vi_end) = vertices(g);
    for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    {
        wi = vi;
        ++wi;
        for (; wi != vi_end; ++wi)
            add_edge(*vi, *wi, g);
    }
}

template < typename Graph > void gabows_graph(Graph& g, int n)
{
    // creates a graph with 2n vertices, consisting of the complete graph
    // on n vertices plus n vertices of degree one, each adjacent to one
    // vertex in the complete graph. without any initial matching, this
    // graph forces edmonds' algorithm into worst-case behavior.

    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;

    g = Graph(2 * n);

    vertex_iterator_t vi, vi_end, ui, ui_end, halfway;

    boost::tie(ui, ui_end) = vertices(g);

    halfway = ui;
    for (int i = 0; i < n; ++i)
        ++halfway;

    while (ui != halfway)
    {
        vi = ui;
        ++vi;
        while (vi != halfway)
        {
            add_edge(*ui, *vi, g);
            ++vi;
        }
        ++ui;
    }

    boost::tie(ui, ui_end) = vertices(g);

    while (halfway != ui_end)
    {
        add_edge(*ui, *halfway, g);
        ++ui;
        ++halfway;
    }
}

template < typename Graph >
void matching_test(std::size_t num_v, const std::string& graph_name)
{
    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;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;

    const std::size_t double_num_v = num_v * 2;

    bool all_tests_passed = true;

    // form the complete graph on 2*n vertices; the maximum cardinality
    // matching, greedy matching, and extra greedy matching should all be the
    // same - a matching of size n.

    Graph g(double_num_v);
    complete_graph(g, double_num_v);

    vertex_index_installer< Graph >::install(g);

    mate_t edmonds_mate(double_num_v);
    mate_t greedy_mate(double_num_v);
    mate_t extra_greedy_mate(double_num_v);

    // find a maximum cardinality matching using edmonds' blossom-shrinking
    // algorithm, starting with an empty matching.
    bool edmonds_result = matching< Graph, mate_t, vertex_index_map_t,
        edmonds_augmenting_path_finder, empty_matching,
        maximum_cardinality_matching_verifier >(
        g, edmonds_mate, get(vertex_index, g));

    BOOST_TEST(edmonds_result);
    if (!edmonds_result)
    {
        std::cout
            << "Verifier reporting a problem finding a perfect matching on"
            << std::endl
            << "the complete graph using " << graph_name << std::endl;
        all_tests_passed = false;
    }

    // find a greedy matching
    bool greedy_result = matching< Graph, mate_t, vertex_index_map_t,
        no_augmenting_path_finder, greedy_matching,
        maximum_cardinality_matching_verifier >(
        g, greedy_mate, get(vertex_index, g));

    BOOST_TEST(greedy_result);
    if (!greedy_result)
    {
        std::cout << "Verifier reporting a problem finding a greedy matching on"
                  << std::endl
                  << "the complete graph using " << graph_name << std::endl;
        all_tests_passed = false;
    }

    // find an extra greedy matching
    bool extra_greedy_result = matching< Graph, mate_t, vertex_index_map_t,
        no_augmenting_path_finder, extra_greedy_matching,
        maximum_cardinality_matching_verifier >(
        g, extra_greedy_mate, get(vertex_index, g));

    BOOST_TEST(extra_greedy_result);
    if (!extra_greedy_result)
    {
        std::cout << "Verifier reporting a problem finding an extra greedy "
                     "matching on"
                  << std::endl
                  << "the complete graph using " << graph_name << std::endl;
        all_tests_passed = false;
    }

    // as a sanity check, make sure that each of the matchings returned is a
    // valid matching and has 1000 edges.

    bool edmonds_sanity_check = is_a_matching(g, edmonds_mate)
        && matching_size(g, edmonds_mate) == num_v;

    BOOST_TEST(edmonds_sanity_check);
    if (edmonds_result && !edmonds_sanity_check)
    {
        std::cout
            << "Verifier okayed edmonds' algorithm on the complete graph, but"
            << std::endl
            << "the matching returned either wasn't a valid matching or wasn't"
            << std::endl
            << "actually a maximum cardinality matching." << std::endl;
        all_tests_passed = false;
    }

    bool greedy_sanity_check = is_a_matching(g, greedy_mate)
        && matching_size(g, greedy_mate) == num_v;

    BOOST_TEST(greedy_sanity_check);
    if (greedy_result && !greedy_sanity_check)
    {
        std::cout
            << "Verifier okayed greedy algorithm on the complete graph, but"
            << std::endl
            << "the matching returned either wasn't a valid matching or wasn't"
            << std::endl
            << "actually a maximum cardinality matching." << std::endl;
        all_tests_passed = false;
    }

    bool extra_greedy_sanity_check = is_a_matching(g, extra_greedy_mate)
        && matching_size(g, extra_greedy_mate) == num_v;

    BOOST_TEST(extra_greedy_sanity_check);
    if (extra_greedy_result && !extra_greedy_sanity_check)
    {
        std::cout
            << "Verifier okayed extra greedy algorithm on the complete graph, "
               "but"
            << std::endl
            << "the matching returned either wasn't a valid matching or wasn't"
            << std::endl
            << "actually a maximum cardinality matching." << std::endl;
        all_tests_passed = false;
    }

    // Now remove an edge from the edmonds_mate matching.
    vertex_iterator_t vi, vi_end;
    for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        if (edmonds_mate[*vi] != graph_traits< Graph >::null_vertex())
            break;

    edmonds_mate[edmonds_mate[*vi]] = graph_traits< Graph >::null_vertex();
    edmonds_mate[*vi] = graph_traits< Graph >::null_vertex();

    //...and run the matching verifier - it should tell us that the matching
    // isn't a maximum matching.
    bool modified_edmonds_verification_result
        = maximum_cardinality_matching_verifier< Graph, mate_t,
            vertex_index_map_t >::verify_matching(g, edmonds_mate,
            get(vertex_index, g));

    BOOST_TEST(!modified_edmonds_verification_result);
    if (modified_edmonds_verification_result)
    {
        std::cout << "Verifier was fooled into thinking that a non-maximum "
                     "matching was maximum"
                  << std::endl;
        all_tests_passed = false;
    }

    Graph h(double_num_v);
    gabows_graph(h, num_v);

    vertex_index_installer< Graph >::install(h);

    // gabow's graph always has a perfect matching. it's also a good example of
    // why one should initialize with the extra_greedy_matching in most cases.

    mate_t gabow_mate(double_num_v);

    bool gabows_graph_result
        = checked_edmonds_maximum_cardinality_matching(h, gabow_mate);

    BOOST_TEST(gabows_graph_result);
    if (!gabows_graph_result)
    {
        std::cout
            << "Problem on Gabow's Graph with " << graph_name << ":"
            << std::endl
            << "   Verifier reporting a maximum cardinality matching not found."
            << std::endl;
        all_tests_passed = false;
    }

    BOOST_TEST(matching_size(h, gabow_mate) == num_v);
    if (gabows_graph_result && matching_size(h, gabow_mate) != num_v)
    {
        std::cout
            << "Problem on Gabow's Graph with " << graph_name << ":"
            << std::endl
            << "   Verifier reported a maximum cardinality matching found,"
            << std::endl
            << "   but matching size is " << matching_size(h, gabow_mate)
            << " when it should be " << num_v << std::endl;
        all_tests_passed = false;
    }

    Graph j(double_num_v);
    vertex_index_installer< Graph >::install(j);

    typedef boost::mt19937 base_generator_type;
    base_generator_type generator(static_cast< unsigned int >(std::time(0)));
    boost::uniform_int<> distribution(0, double_num_v - 1);
    boost::variate_generator< base_generator_type&, boost::uniform_int<> >
        rand_num(generator, distribution);

    std::size_t num_edges = 0;
    bool success;

    while (num_edges < 4 * double_num_v)
    {
        vertex_descriptor_t u = random_vertex(j, rand_num);
        vertex_descriptor_t v = random_vertex(j, rand_num);
        if (u != v)
        {
            boost::tie(tuples::ignore, success) = add_edge(u, v, j);
            if (success)
                num_edges++;
        }
    }

    mate_t random_mate(double_num_v);
    bool random_graph_result
        = checked_edmonds_maximum_cardinality_matching(j, random_mate);

    BOOST_TEST(random_graph_result);
    if (!random_graph_result)
    {
        std::cout << "Matching in random graph not maximum for " << graph_name
                  << std::endl;
        all_tests_passed = false;
    }

    // Now remove an edge from the random_mate matching.
    for (boost::tie(vi, vi_end) = vertices(j); vi != vi_end; ++vi)
        if (random_mate[*vi] != graph_traits< Graph >::null_vertex())
            break;

    random_mate[random_mate[*vi]] = graph_traits< Graph >::null_vertex();
    random_mate[*vi] = graph_traits< Graph >::null_vertex();

    //...and run the matching verifier - it should tell us that the matching
    // isn't a maximum matching.
    bool modified_random_verification_result
        = maximum_cardinality_matching_verifier< Graph, mate_t,
            vertex_index_map_t >::verify_matching(j, random_mate,
            get(vertex_index, j));

    BOOST_TEST(!modified_random_verification_result);
    if (modified_random_verification_result)
    {
        std::cout << "Verifier was fooled into thinking that a non-maximum "
                     "matching was maximum"
                  << std::endl;
        all_tests_passed = false;
    }

    BOOST_TEST(all_tests_passed);
    if (all_tests_passed)
    {
        std::cout << graph_name << " passed all tests for n = " << num_v << '.'
                  << std::endl;
    }
}

int main(int, char*[])
{

    matching_test< undirected_graph >(10, "adjacency_list (using vectors)");
    matching_test< undirected_list_graph >(10, "adjacency_list (using lists)");
    matching_test< undirected_adjacency_matrix_graph >(10, "adjacency_matrix");

    matching_test< undirected_graph >(20, "adjacency_list (using vectors)");
    matching_test< undirected_list_graph >(20, "adjacency_list (using lists)");
    matching_test< undirected_adjacency_matrix_graph >(20, "adjacency_matrix");

    matching_test< undirected_graph >(21, "adjacency_list (using vectors)");
    matching_test< undirected_list_graph >(21, "adjacency_list (using lists)");
    matching_test< undirected_adjacency_matrix_graph >(21, "adjacency_matrix");

#if 0
  matching_test<undirected_graph>(50, "adjacency_list (using vectors)");
  matching_test<undirected_list_graph>(50, "adjacency_list (using lists)");
  matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix");

  matching_test<undirected_graph>(51, "adjacency_list (using vectors)");
  matching_test<undirected_list_graph>(51, "adjacency_list (using lists)");
  matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix");
#endif

    return boost::report_errors();
}