robot/include/boost/graph/max_cardinality_matching.hpp

//=======================================================================
// 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)
//
//=======================================================================

#ifndef BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
#define BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP

#include <vector>
#include <list>
#include <deque>
#include <algorithm> // for std::sort and std::stable_sort
#include <utility> // for std::pair
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/assert.hpp>

namespace boost
{
namespace graph
{
    namespace detail
    {
        enum VERTEX_STATE
        {
            V_EVEN,
            V_ODD,
            V_UNREACHED
        };
    }
} // end namespace graph::detail

template < typename Graph, typename MateMap, typename VertexIndexMap >
typename graph_traits< Graph >::vertices_size_type matching_size(
    const Graph& g, MateMap mate, VertexIndexMap vm)
{
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits< Graph >::vertices_size_type v_size_t;

    v_size_t size_of_matching = 0;
    vertex_iterator_t vi, vi_end;

    for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    {
        vertex_descriptor_t v = *vi;
        if (get(mate, v) != graph_traits< Graph >::null_vertex()
            && get(vm, v) < get(vm, get(mate, v)))
            ++size_of_matching;
    }
    return size_of_matching;
}

template < typename Graph, typename MateMap >
inline typename graph_traits< Graph >::vertices_size_type matching_size(
    const Graph& g, MateMap mate)
{
    return matching_size(g, mate, get(vertex_index, g));
}

template < typename Graph, typename MateMap, typename VertexIndexMap >
bool is_a_matching(const Graph& g, MateMap mate, VertexIndexMap)
{
    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;

    vertex_iterator_t vi, vi_end;
    for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    {
        vertex_descriptor_t v = *vi;
        if (get(mate, v) != graph_traits< Graph >::null_vertex()
            && v != get(mate, get(mate, v)))
            return false;
    }
    return true;
}

template < typename Graph, typename MateMap >
inline bool is_a_matching(const Graph& g, MateMap mate)
{
    return is_a_matching(g, mate, get(vertex_index, g));
}

//***************************************************************************
//***************************************************************************
//               Maximum Cardinality Matching Functors
//***************************************************************************
//***************************************************************************

template < typename Graph, typename MateMap,
    typename VertexIndexMap = dummy_property_map >
struct no_augmenting_path_finder
{
    no_augmenting_path_finder(const Graph&, MateMap, VertexIndexMap) {}

    inline bool augment_matching() { return false; }

    template < typename PropertyMap > void get_current_matching(PropertyMap) {}
};

template < typename Graph, typename MateMap, typename VertexIndexMap >
class edmonds_augmenting_path_finder
{
    // This implementation of Edmonds' matching algorithm closely
    // follows Tarjan's description of the algorithm in "Data
    // Structures and Network Algorithms."

public:
    // generates the type of an iterator property map from vertices to type X
    template < typename X > struct map_vertex_to_
    {
        typedef boost::iterator_property_map<
            typename std::vector< X >::iterator, VertexIndexMap >
            type;
    };

    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename std::pair< vertex_descriptor_t, vertex_descriptor_t >
        vertex_pair_t;
    typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t;
    typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
    typedef typename graph_traits< Graph >::edges_size_type e_size_t;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef
        typename graph_traits< Graph >::out_edge_iterator out_edge_iterator_t;
    typedef typename std::deque< vertex_descriptor_t > vertex_list_t;
    typedef typename std::vector< edge_descriptor_t > edge_list_t;
    typedef typename map_vertex_to_< vertex_descriptor_t >::type
        vertex_to_vertex_map_t;
    typedef typename map_vertex_to_< int >::type vertex_to_int_map_t;
    typedef typename map_vertex_to_< vertex_pair_t >::type
        vertex_to_vertex_pair_map_t;
    typedef typename map_vertex_to_< v_size_t >::type vertex_to_vsize_map_t;
    typedef typename map_vertex_to_< e_size_t >::type vertex_to_esize_map_t;

    edmonds_augmenting_path_finder(
        const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm)
    : g(arg_g)
    , vm(arg_vm)
    , n_vertices(num_vertices(arg_g))
    ,

        mate_vector(n_vertices)
    , ancestor_of_v_vector(n_vertices)
    , ancestor_of_w_vector(n_vertices)
    , vertex_state_vector(n_vertices)
    , origin_vector(n_vertices)
    , pred_vector(n_vertices)
    , bridge_vector(n_vertices)
    , ds_parent_vector(n_vertices)
    , ds_rank_vector(n_vertices)
    ,

        mate(mate_vector.begin(), vm)
    , ancestor_of_v(ancestor_of_v_vector.begin(), vm)
    , ancestor_of_w(ancestor_of_w_vector.begin(), vm)
    , vertex_state(vertex_state_vector.begin(), vm)
    , origin(origin_vector.begin(), vm)
    , pred(pred_vector.begin(), vm)
    , bridge(bridge_vector.begin(), vm)
    , ds_parent_map(ds_parent_vector.begin(), vm)
    , ds_rank_map(ds_rank_vector.begin(), vm)
    ,

        ds(ds_rank_map, ds_parent_map)
    {
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            mate[*vi] = get(arg_mate, *vi);
    }

    bool augment_matching()
    {
        // As an optimization, some of these values can be saved from one
        // iteration to the next instead of being re-initialized each
        // iteration, allowing for "lazy blossom expansion." This is not
        // currently implemented.

        e_size_t timestamp = 0;
        even_edges.clear();

        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        {
            vertex_descriptor_t u = *vi;

            origin[u] = u;
            pred[u] = u;
            ancestor_of_v[u] = 0;
            ancestor_of_w[u] = 0;
            ds.make_set(u);

            if (mate[u] == graph_traits< Graph >::null_vertex())
            {
                vertex_state[u] = graph::detail::V_EVEN;
                out_edge_iterator_t ei, ei_end;
                for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end;
                     ++ei)
                {
                    if (target(*ei, g) != u)
                    {
                        even_edges.push_back(*ei);
                    }
                }
            }
            else
                vertex_state[u] = graph::detail::V_UNREACHED;
        }

        // end initializations

        vertex_descriptor_t v, w, w_free_ancestor, v_free_ancestor;
        w_free_ancestor = graph_traits< Graph >::null_vertex();
        v_free_ancestor = graph_traits< Graph >::null_vertex();
        bool found_alternating_path = false;

        while (!even_edges.empty() && !found_alternating_path)
        {
            // since we push even edges onto the back of the list as
            // they're discovered, taking them off the back will search
            // for augmenting paths depth-first.
            edge_descriptor_t current_edge = even_edges.back();
            even_edges.pop_back();

            v = source(current_edge, g);
            w = target(current_edge, g);

            vertex_descriptor_t v_prime = origin[ds.find_set(v)];
            vertex_descriptor_t w_prime = origin[ds.find_set(w)];

            // because of the way we put all of the edges on the queue,
            // v_prime should be labeled V_EVEN; the following is a
            // little paranoid but it could happen...
            if (vertex_state[v_prime] != graph::detail::V_EVEN)
            {
                std::swap(v_prime, w_prime);
                std::swap(v, w);
            }

            if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
            {
                vertex_state[w_prime] = graph::detail::V_ODD;
                vertex_descriptor_t w_prime_mate = mate[w_prime];
                vertex_state[w_prime_mate] = graph::detail::V_EVEN;
                out_edge_iterator_t ei, ei_end;
                for (boost::tie(ei, ei_end) = out_edges(w_prime_mate, g);
                     ei != ei_end; ++ei)
                {
                    if (target(*ei, g) != w_prime_mate)
                    {
                        even_edges.push_back(*ei);
                    }
                }
                pred[w_prime] = v;
            }

            // w_prime == v_prime can happen below if we get an edge that has
            // been shrunk into a blossom
            else if (vertex_state[w_prime] == graph::detail::V_EVEN
                && w_prime != v_prime)
            {
                vertex_descriptor_t w_up = w_prime;
                vertex_descriptor_t v_up = v_prime;
                vertex_descriptor_t nearest_common_ancestor
                    = graph_traits< Graph >::null_vertex();
                w_free_ancestor = graph_traits< Graph >::null_vertex();
                v_free_ancestor = graph_traits< Graph >::null_vertex();

                // We now need to distinguish between the case that
                // w_prime and v_prime share an ancestor under the
                // "parent" relation, in which case we've found a
                // blossom and should shrink it, or the case that
                // w_prime and v_prime both have distinct ancestors that
                // are free, in which case we've found an alternating
                // path between those two ancestors.

                ++timestamp;

                while (nearest_common_ancestor
                        == graph_traits< Graph >::null_vertex()
                    && (v_free_ancestor == graph_traits< Graph >::null_vertex()
                        || w_free_ancestor
                            == graph_traits< Graph >::null_vertex()))
                {
                    ancestor_of_w[w_up] = timestamp;
                    ancestor_of_v[v_up] = timestamp;

                    if (w_free_ancestor == graph_traits< Graph >::null_vertex())
                        w_up = parent(w_up);
                    if (v_free_ancestor == graph_traits< Graph >::null_vertex())
                        v_up = parent(v_up);

                    if (mate[v_up] == graph_traits< Graph >::null_vertex())
                        v_free_ancestor = v_up;
                    if (mate[w_up] == graph_traits< Graph >::null_vertex())
                        w_free_ancestor = w_up;

                    if (ancestor_of_w[v_up] == timestamp)
                        nearest_common_ancestor = v_up;
                    else if (ancestor_of_v[w_up] == timestamp)
                        nearest_common_ancestor = w_up;
                    else if (v_free_ancestor == w_free_ancestor
                        && v_free_ancestor
                            != graph_traits< Graph >::null_vertex())
                        nearest_common_ancestor = v_up;
                }

                if (nearest_common_ancestor
                    == graph_traits< Graph >::null_vertex())
                    found_alternating_path = true; // to break out of the loop
                else
                {
                    // shrink the blossom
                    link_and_set_bridges(
                        w_prime, nearest_common_ancestor, std::make_pair(w, v));
                    link_and_set_bridges(
                        v_prime, nearest_common_ancestor, std::make_pair(v, w));
                }
            }
        }

        if (!found_alternating_path)
            return false;

        // retrieve the augmenting path and put it in aug_path
        reversed_retrieve_augmenting_path(v, v_free_ancestor);
        retrieve_augmenting_path(w, w_free_ancestor);

        // augment the matching along aug_path
        vertex_descriptor_t a, b;
        while (!aug_path.empty())
        {
            a = aug_path.front();
            aug_path.pop_front();
            b = aug_path.front();
            aug_path.pop_front();
            mate[a] = b;
            mate[b] = a;
        }

        return true;
    }

    template < typename PropertyMap > void get_current_matching(PropertyMap pm)
    {
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            put(pm, *vi, mate[*vi]);
    }

    template < typename PropertyMap > void get_vertex_state_map(PropertyMap pm)
    {
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            put(pm, *vi, vertex_state[origin[ds.find_set(*vi)]]);
    }

private:
    vertex_descriptor_t parent(vertex_descriptor_t x)
    {
        if (vertex_state[x] == graph::detail::V_EVEN
            && mate[x] != graph_traits< Graph >::null_vertex())
            return mate[x];
        else if (vertex_state[x] == graph::detail::V_ODD)
            return origin[ds.find_set(pred[x])];
        else
            return x;
    }

    void link_and_set_bridges(vertex_descriptor_t x,
        vertex_descriptor_t stop_vertex, vertex_pair_t the_bridge)
    {
        for (vertex_descriptor_t v = x; v != stop_vertex; v = parent(v))
        {
            ds.union_set(v, stop_vertex);
            origin[ds.find_set(stop_vertex)] = stop_vertex;

            if (vertex_state[v] == graph::detail::V_ODD)
            {
                bridge[v] = the_bridge;
                out_edge_iterator_t oei, oei_end;
                for (boost::tie(oei, oei_end) = out_edges(v, g); oei != oei_end;
                     ++oei)
                {
                    if (target(*oei, g) != v)
                    {
                        even_edges.push_back(*oei);
                    }
                }
            }
        }
    }

    // Since none of the STL containers support both constant-time
    // concatenation and reversal, the process of expanding an
    // augmenting path once we know one exists is a little more
    // complicated than it has to be. If we know the path is from v to
    // w, then the augmenting path is recursively defined as:
    //
    // path(v,w) = [v], if v = w
    //           = concat([v, mate[v]], path(pred[mate[v]], w),
    //                if v != w and vertex_state[v] == graph::detail::V_EVEN
    //           = concat([v], reverse(path(x,mate[v])), path(y,w)),
    //                if v != w, vertex_state[v] == graph::detail::V_ODD, and
    //                bridge[v] = (x,y)
    //
    // These next two mutually recursive functions implement this definition.

    void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w)
    {
        if (v == w)
            aug_path.push_back(v);
        else if (vertex_state[v] == graph::detail::V_EVEN)
        {
            aug_path.push_back(v);
            aug_path.push_back(mate[v]);
            retrieve_augmenting_path(pred[mate[v]], w);
        }
        else // vertex_state[v] == graph::detail::V_ODD
        {
            aug_path.push_back(v);
            reversed_retrieve_augmenting_path(bridge[v].first, mate[v]);
            retrieve_augmenting_path(bridge[v].second, w);
        }
    }

    void reversed_retrieve_augmenting_path(
        vertex_descriptor_t v, vertex_descriptor_t w)
    {

        if (v == w)
            aug_path.push_back(v);
        else if (vertex_state[v] == graph::detail::V_EVEN)
        {
            reversed_retrieve_augmenting_path(pred[mate[v]], w);
            aug_path.push_back(mate[v]);
            aug_path.push_back(v);
        }
        else // vertex_state[v] == graph::detail::V_ODD
        {
            reversed_retrieve_augmenting_path(bridge[v].second, w);
            retrieve_augmenting_path(bridge[v].first, mate[v]);
            aug_path.push_back(v);
        }
    }

    // private data members

    const Graph& g;
    VertexIndexMap vm;
    v_size_t n_vertices;

    // storage for the property maps below
    std::vector< vertex_descriptor_t > mate_vector;
    std::vector< e_size_t > ancestor_of_v_vector;
    std::vector< e_size_t > ancestor_of_w_vector;
    std::vector< int > vertex_state_vector;
    std::vector< vertex_descriptor_t > origin_vector;
    std::vector< vertex_descriptor_t > pred_vector;
    std::vector< vertex_pair_t > bridge_vector;
    std::vector< vertex_descriptor_t > ds_parent_vector;
    std::vector< v_size_t > ds_rank_vector;

    // iterator property maps
    vertex_to_vertex_map_t mate;
    vertex_to_esize_map_t ancestor_of_v;
    vertex_to_esize_map_t ancestor_of_w;
    vertex_to_int_map_t vertex_state;
    vertex_to_vertex_map_t origin;
    vertex_to_vertex_map_t pred;
    vertex_to_vertex_pair_map_t bridge;
    vertex_to_vertex_map_t ds_parent_map;
    vertex_to_vsize_map_t ds_rank_map;

    vertex_list_t aug_path;
    edge_list_t even_edges;
    disjoint_sets< vertex_to_vsize_map_t, vertex_to_vertex_map_t > ds;
};

//***************************************************************************
//***************************************************************************
//               Initial Matching Functors
//***************************************************************************
//***************************************************************************

template < typename Graph, typename MateMap > struct greedy_matching
{
    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t;
    typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;

    static void find_matching(const Graph& g, MateMap mate)
    {
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            put(mate, *vi, graph_traits< Graph >::null_vertex());

        edge_iterator_t ei, ei_end;
        for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        {
            edge_descriptor_t e = *ei;
            vertex_descriptor_t u = source(e, g);
            vertex_descriptor_t v = target(e, g);

            if (u != v && get(mate, u) == get(mate, v))
            // only way equality can hold is if
            //   mate[u] == mate[v] == null_vertex
            {
                put(mate, u, v);
                put(mate, v, u);
            }
        }
    }
};

template < typename Graph, typename MateMap > struct extra_greedy_matching
{
    // The "extra greedy matching" is formed by repeating the
    // following procedure as many times as possible: Choose the
    // unmatched vertex v of minimum non-zero degree.  Choose the
    // neighbor w of v which is unmatched and has minimum degree over
    // all of v's neighbors. Add (u,v) to the matching. Ties for
    // either choice are broken arbitrarily. This procedure takes time
    // O(m log n), where m is the number of edges in the graph and n
    // is the number of vertices.

    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t;
    typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
    typedef std::pair< vertex_descriptor_t, vertex_descriptor_t > vertex_pair_t;

    struct select_first
    {
        inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
        {
            return p.first;
        }
    };

    struct select_second
    {
        inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
        {
            return p.second;
        }
    };

    template < class PairSelector > class less_than_by_degree
    {
    public:
        less_than_by_degree(const Graph& g) : m_g(g) {}
        bool operator()(const vertex_pair_t x, const vertex_pair_t y)
        {
            return out_degree(PairSelector::select_vertex(x), m_g)
                < out_degree(PairSelector::select_vertex(y), m_g);
        }

    private:
        const Graph& m_g;
    };

    static void find_matching(const Graph& g, MateMap mate)
    {
        typedef std::vector<
            std::pair< vertex_descriptor_t, vertex_descriptor_t > >
            directed_edges_vector_t;

        directed_edges_vector_t edge_list;
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            put(mate, *vi, graph_traits< Graph >::null_vertex());

        edge_iterator_t ei, ei_end;
        for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        {
            edge_descriptor_t e = *ei;
            vertex_descriptor_t u = source(e, g);
            vertex_descriptor_t v = target(e, g);
            if (u == v)
                continue;
            edge_list.push_back(std::make_pair(u, v));
            edge_list.push_back(std::make_pair(v, u));
        }

        // sort the edges by the degree of the target, then (using a
        // stable sort) by degree of the source
        std::sort(edge_list.begin(), edge_list.end(),
            less_than_by_degree< select_second >(g));
        std::stable_sort(edge_list.begin(), edge_list.end(),
            less_than_by_degree< select_first >(g));

        // construct the extra greedy matching
        for (typename directed_edges_vector_t::const_iterator itr
             = edge_list.begin();
             itr != edge_list.end(); ++itr)
        {
            if (get(mate, itr->first) == get(mate, itr->second))
            // only way equality can hold is if mate[itr->first] ==
            // mate[itr->second] == null_vertex
            {
                put(mate, itr->first, itr->second);
                put(mate, itr->second, itr->first);
            }
        }
    }
};

template < typename Graph, typename MateMap > struct empty_matching
{
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;

    static void find_matching(const Graph& g, MateMap mate)
    {
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            put(mate, *vi, graph_traits< Graph >::null_vertex());
    }
};

//***************************************************************************
//***************************************************************************
//               Matching Verifiers
//***************************************************************************
//***************************************************************************

namespace detail
{

    template < typename SizeType >
    class odd_components_counter : public dfs_visitor<>
    // This depth-first search visitor will count the number of connected
    // components with an odd number of vertices. It's used by
    // maximum_matching_verifier.
    {
    public:
        odd_components_counter(SizeType& c_count) : m_count(c_count)
        {
            m_count = 0;
        }

        template < class Vertex, class Graph > void start_vertex(Vertex, Graph&)
        {
            m_parity = false;
        }

        template < class Vertex, class Graph >
        void discover_vertex(Vertex, Graph&)
        {
            m_parity = !m_parity;
            m_parity ? ++m_count : --m_count;
        }

    protected:
        SizeType& m_count;

    private:
        bool m_parity;
    };

} // namespace detail

template < typename Graph, typename MateMap,
    typename VertexIndexMap = dummy_property_map >
struct no_matching_verifier
{
    inline static bool verify_matching(const Graph&, MateMap, VertexIndexMap)
    {
        return true;
    }
};

template < typename Graph, typename MateMap, typename VertexIndexMap >
struct maximum_cardinality_matching_verifier
{

    template < typename X > struct map_vertex_to_
    {
        typedef boost::iterator_property_map<
            typename std::vector< X >::iterator, VertexIndexMap >
            type;
    };

    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef typename map_vertex_to_< int >::type vertex_to_int_map_t;
    typedef typename map_vertex_to_< vertex_descriptor_t >::type
        vertex_to_vertex_map_t;

    template < typename VertexStateMap > struct non_odd_vertex
    {
        // this predicate is used to create a filtered graph that
        // excludes vertices labeled "graph::detail::V_ODD"
        non_odd_vertex() : vertex_state(0) {}

        non_odd_vertex(VertexStateMap* arg_vertex_state)
        : vertex_state(arg_vertex_state)
        {
        }

        template < typename Vertex > bool operator()(const Vertex& v) const
        {
            BOOST_ASSERT(vertex_state);
            return get(*vertex_state, v) != graph::detail::V_ODD;
        }

        VertexStateMap* vertex_state;
    };

    static bool verify_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
    {
        // For any graph G, let o(G) be the number of connected
        // components in G of odd size. For a subset S of G's vertex set
        // V(G), let (G - S) represent the subgraph of G induced by
        // removing all vertices in S from G. Let M(G) be the size of the
        // maximum cardinality matching in G. Then the Tutte-Berge
        // formula guarantees that
        //
        //           2 * M(G) = min ( |V(G)| + |U| + o(G - U) )
        //
        // where the minimum is taken over all subsets U of
        // V(G). Edmonds' algorithm finds a set U that achieves the
        // minimum in the above formula, namely the vertices labeled
        //"ODD." This function runs one iteration of Edmonds' algorithm
        // to find U, then verifies that the size of the matching given
        // by mate satisfies the Tutte-Berge formula.

        // first, make sure it's a valid matching
        if (!is_a_matching(g, mate, vm))
            return false;

        // We'll try to augment the matching once. This serves two
        // purposes: first, if we find some augmenting path, the matching
        // is obviously non-maximum. Second, running edmonds' algorithm
        // on a graph with no augmenting path will create the
        // Edmonds-Gallai decomposition that we need as a certificate of
        // maximality - we can get it by looking at the vertex_state map
        // that results.
        edmonds_augmenting_path_finder< Graph, MateMap, VertexIndexMap >
            augmentor(g, mate, vm);
        if (augmentor.augment_matching())
            return false;

        std::vector< int > vertex_state_vector(num_vertices(g));
        vertex_to_int_map_t vertex_state(vertex_state_vector.begin(), vm);
        augmentor.get_vertex_state_map(vertex_state);

        // count the number of graph::detail::V_ODD vertices
        v_size_t num_odd_vertices = 0;
        vertex_iterator_t vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            if (vertex_state[*vi] == graph::detail::V_ODD)
                ++num_odd_vertices;

        // count the number of connected components with odd cardinality
        // in the graph without graph::detail::V_ODD vertices
        non_odd_vertex< vertex_to_int_map_t > filter(&vertex_state);
        filtered_graph< Graph, keep_all, non_odd_vertex< vertex_to_int_map_t > >
            fg(g, keep_all(), filter);

        v_size_t num_odd_components;
        detail::odd_components_counter< v_size_t > occ(num_odd_components);
        depth_first_search(fg, visitor(occ).vertex_index_map(vm));

        if (2 * matching_size(g, mate, vm)
            == num_vertices(g) + num_odd_vertices - num_odd_components)
            return true;
        else
            return false;
    }
};

template < typename Graph, typename MateMap, typename VertexIndexMap,
    template < typename, typename, typename > class AugmentingPathFinder,
    template < typename, typename > class InitialMatchingFinder,
    template < typename, typename, typename > class MatchingVerifier >
bool matching(const Graph& g, MateMap mate, VertexIndexMap vm)
{

    InitialMatchingFinder< Graph, MateMap >::find_matching(g, mate);

    AugmentingPathFinder< Graph, MateMap, VertexIndexMap > augmentor(
        g, mate, vm);
    bool not_maximum_yet = true;
    while (not_maximum_yet)
    {
        not_maximum_yet = augmentor.augment_matching();
    }
    augmentor.get_current_matching(mate);

    return MatchingVerifier< Graph, MateMap, VertexIndexMap >::verify_matching(
        g, mate, vm);
}

template < typename Graph, typename MateMap, typename VertexIndexMap >
inline bool checked_edmonds_maximum_cardinality_matching(
    const Graph& g, MateMap mate, VertexIndexMap vm)
{
    return matching< Graph, MateMap, VertexIndexMap,
        edmonds_augmenting_path_finder, extra_greedy_matching,
        maximum_cardinality_matching_verifier >(g, mate, vm);
}

template < typename Graph, typename MateMap >
inline bool checked_edmonds_maximum_cardinality_matching(
    const Graph& g, MateMap mate)
{
    return checked_edmonds_maximum_cardinality_matching(
        g, mate, get(vertex_index, g));
}

template < typename Graph, typename MateMap, typename VertexIndexMap >
inline void edmonds_maximum_cardinality_matching(
    const Graph& g, MateMap mate, VertexIndexMap vm)
{
    matching< Graph, MateMap, VertexIndexMap, edmonds_augmenting_path_finder,
        extra_greedy_matching, no_matching_verifier >(g, mate, vm);
}

template < typename Graph, typename MateMap >
inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate)
{
    edmonds_maximum_cardinality_matching(g, mate, get(vertex_index, g));
}

} // namespace boost

#endif // BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP