Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

boost/graph/reverse_graph.hpp

//  (C) Copyright David Abrahams 2000.
// 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 REVERSE_GRAPH_DWA092300_H_
#define REVERSE_GRAPH_DWA092300_H_

#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/properties.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/if.hpp>

namespace boost
{

struct reverse_graph_tag
{
};

namespace detail
{

    template < typename EdgeDesc > class reverse_graph_edge_descriptor
    {
    public:
        EdgeDesc
            underlying_descx; // Odd name is because this needs to be public but
                              // shouldn't be exposed to users anymore

    private:
        typedef EdgeDesc base_descriptor_type;

    public:
        explicit reverse_graph_edge_descriptor(
            const EdgeDesc& underlying_descx = EdgeDesc())
        : underlying_descx(underlying_descx)
        {
        }

        friend bool operator==(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx == b.underlying_descx;
        }
        friend bool operator!=(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx != b.underlying_descx;
        }
        friend bool operator<(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx < b.underlying_descx;
        }
        friend bool operator>(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx > b.underlying_descx;
        }
        friend bool operator<=(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx <= b.underlying_descx;
        }
        friend bool operator>=(const reverse_graph_edge_descriptor& a,
            const reverse_graph_edge_descriptor& b)
        {
            return a.underlying_descx >= b.underlying_descx;
        }
    };

    template < typename EdgeDesc > struct reverse_graph_edge_descriptor_maker
    {
        typedef reverse_graph_edge_descriptor< EdgeDesc > result_type;

        reverse_graph_edge_descriptor< EdgeDesc > operator()(
            const EdgeDesc& ed) const
        {
            return reverse_graph_edge_descriptor< EdgeDesc >(ed);
        }
    };

    template < typename EdgeDesc, typename Iter >
    std::pair< transform_iterator<
                   reverse_graph_edge_descriptor_maker< EdgeDesc >, Iter >,
        transform_iterator< reverse_graph_edge_descriptor_maker< EdgeDesc >,
            Iter > >
    reverse_edge_iter_pair(const std::pair< Iter, Iter >& ip)
    {
        return std::make_pair(
            make_transform_iterator(
                ip.first, reverse_graph_edge_descriptor_maker< EdgeDesc >()),
            make_transform_iterator(
                ip.second, reverse_graph_edge_descriptor_maker< EdgeDesc >()));
    }

    // Get the underlying descriptor from a vertex or edge descriptor
    template < typename Desc >
    struct get_underlying_descriptor_from_reverse_descriptor
    {
        typedef Desc type;
        static Desc convert(const Desc& d) { return d; }
    };
    template < typename Desc >
    struct get_underlying_descriptor_from_reverse_descriptor<
        reverse_graph_edge_descriptor< Desc > >
    {
        typedef Desc type;
        static Desc convert(const reverse_graph_edge_descriptor< Desc >& d)
        {
            return d.underlying_descx;
        }
    };

    template < bool isEdgeList > struct choose_rev_edge_iter
    {
    };
    template <> struct choose_rev_edge_iter< true >
    {
        template < class G > struct bind_
        {
            typedef transform_iterator<
                reverse_graph_edge_descriptor_maker<
                    typename graph_traits< G >::edge_descriptor >,
                typename graph_traits< G >::edge_iterator >
                type;
        };
    };
    template <> struct choose_rev_edge_iter< false >
    {
        template < class G > struct bind_
        {
            typedef void type;
        };
    };

} // namespace detail

template < class BidirectionalGraph,
    class GraphRef = const BidirectionalGraph& >
class reverse_graph
{
    typedef reverse_graph< BidirectionalGraph, GraphRef > Self;
    typedef graph_traits< BidirectionalGraph > Traits;

public:
    typedef BidirectionalGraph base_type;
    typedef GraphRef base_ref_type;

    // Constructor
    reverse_graph(GraphRef g) : m_g(g) {}
    // Conversion from reverse_graph on non-const reference to one on const
    // reference
    reverse_graph(
        const reverse_graph< BidirectionalGraph, BidirectionalGraph& >& o)
    : m_g(o.m_g)
    {
    }

    // Graph requirements
    typedef typename Traits::vertex_descriptor vertex_descriptor;
    typedef detail::reverse_graph_edge_descriptor<
        typename Traits::edge_descriptor >
        edge_descriptor;
    typedef typename Traits::directed_category directed_category;
    typedef typename Traits::edge_parallel_category edge_parallel_category;
    typedef typename Traits::traversal_category traversal_category;

    // IncidenceGraph requirements
    typedef transform_iterator< detail::reverse_graph_edge_descriptor_maker<
                                    typename Traits::edge_descriptor >,
        typename Traits::in_edge_iterator >
        out_edge_iterator;
    typedef typename Traits::degree_size_type degree_size_type;

    // BidirectionalGraph requirements
    typedef transform_iterator< detail::reverse_graph_edge_descriptor_maker<
                                    typename Traits::edge_descriptor >,
        typename Traits::out_edge_iterator >
        in_edge_iterator;

    // AdjacencyGraph requirements
    typedef typename adjacency_iterator_generator< Self, vertex_descriptor,
        out_edge_iterator >::type adjacency_iterator;

    // VertexListGraph requirements
    typedef typename Traits::vertex_iterator vertex_iterator;

    // EdgeListGraph requirements
    enum
    {
        is_edge_list
        = is_convertible< traversal_category, edge_list_graph_tag >::value
    };
    typedef detail::choose_rev_edge_iter< is_edge_list > ChooseEdgeIter;
    typedef typename ChooseEdgeIter::template bind_< BidirectionalGraph >::type
        edge_iterator;
    typedef typename Traits::vertices_size_type vertices_size_type;
    typedef typename Traits::edges_size_type edges_size_type;

    typedef reverse_graph_tag graph_tag;

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Bundled properties support
    template < typename Descriptor >
    typename graph::detail::bundled_result< BidirectionalGraph,
        typename detail::get_underlying_descriptor_from_reverse_descriptor<
            Descriptor >::type >::type&
    operator[](Descriptor x)
    {
        return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<
            Descriptor >::convert(x)];
    }

    template < typename Descriptor >
    typename graph::detail::bundled_result< BidirectionalGraph,
        typename detail::get_underlying_descriptor_from_reverse_descriptor<
            Descriptor >::type >::type const&
    operator[](Descriptor x) const
    {
        return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<
            Descriptor >::convert(x)];
    }
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    static vertex_descriptor null_vertex() { return Traits::null_vertex(); }

    // would be private, but template friends aren't portable enough.
    // private:
    GraphRef m_g;
};

// These are separate so they are not instantiated unless used (see bug 1021)
template < class BidirectionalGraph, class GraphRef >
struct vertex_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
{
    typedef
        typename boost::vertex_property_type< BidirectionalGraph >::type type;
};

template < class BidirectionalGraph, class GraphRef >
struct edge_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
{
    typedef typename boost::edge_property_type< BidirectionalGraph >::type type;
};

template < class BidirectionalGraph, class GraphRef >
struct graph_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
{
    typedef
        typename boost::graph_property_type< BidirectionalGraph >::type type;
};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template < typename Graph, typename GraphRef >
struct vertex_bundle_type< reverse_graph< Graph, GraphRef > >
: vertex_bundle_type< Graph >
{
};

template < typename Graph, typename GraphRef >
struct edge_bundle_type< reverse_graph< Graph, GraphRef > >
: edge_bundle_type< Graph >
{
};

template < typename Graph, typename GraphRef >
struct graph_bundle_type< reverse_graph< Graph, GraphRef > >
: graph_bundle_type< Graph >
{
};
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

template < class BidirectionalGraph >
inline reverse_graph< BidirectionalGraph > make_reverse_graph(
    const BidirectionalGraph& g)
{
    return reverse_graph< BidirectionalGraph >(g);
}

template < class BidirectionalGraph >
inline reverse_graph< BidirectionalGraph, BidirectionalGraph& >
make_reverse_graph(BidirectionalGraph& g)
{
    return reverse_graph< BidirectionalGraph, BidirectionalGraph& >(g);
}

template < class BidirectionalGraph, class GRef >
std::pair< typename reverse_graph< BidirectionalGraph >::vertex_iterator,
    typename reverse_graph< BidirectionalGraph >::vertex_iterator >
vertices(const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return vertices(g.m_g);
}

template < class BidirectionalGraph, class GRef >
std::pair< typename reverse_graph< BidirectionalGraph >::edge_iterator,
    typename reverse_graph< BidirectionalGraph >::edge_iterator >
edges(const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return detail::reverse_edge_iter_pair<
        typename graph_traits< BidirectionalGraph >::edge_descriptor >(
        edges(g.m_g));
}

template < class BidirectionalGraph, class GRef >
inline std::pair<
    typename reverse_graph< BidirectionalGraph >::out_edge_iterator,
    typename reverse_graph< BidirectionalGraph >::out_edge_iterator >
out_edges(
    const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return detail::reverse_edge_iter_pair<
        typename graph_traits< BidirectionalGraph >::edge_descriptor >(
        in_edges(u, g.m_g));
}

template < class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::vertices_size_type
num_vertices(const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return num_vertices(g.m_g);
}

template < class BidirectionalGraph, class GRef >
inline typename reverse_graph< BidirectionalGraph >::edges_size_type num_edges(
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return num_edges(g.m_g);
}

template < class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::degree_size_type out_degree(
    const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return in_degree(u, g.m_g);
}

template < class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::vertex_descriptor vertex(
    const typename graph_traits< BidirectionalGraph >::vertices_size_type v,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return vertex(v, g.m_g);
}

template < class BidirectionalGraph, class GRef >
inline std::pair< typename graph_traits< reverse_graph< BidirectionalGraph,
                      GRef > >::edge_descriptor,
    bool >
edge(const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const typename graph_traits< BidirectionalGraph >::vertex_descriptor v,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    typedef typename graph_traits< BidirectionalGraph >::edge_descriptor
        underlying_edge_descriptor;
    std::pair< underlying_edge_descriptor, bool > e = edge(v, u, g.m_g);
    return std::make_pair(
        detail::reverse_graph_edge_descriptor< underlying_edge_descriptor >(
            e.first),
        e.second);
}

template < class BidirectionalGraph, class GRef >
inline std::pair<
    typename reverse_graph< BidirectionalGraph >::in_edge_iterator,
    typename reverse_graph< BidirectionalGraph >::in_edge_iterator >
in_edges(const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return detail::reverse_edge_iter_pair<
        typename graph_traits< BidirectionalGraph >::edge_descriptor >(
        out_edges(u, g.m_g));
}

template < class BidirectionalGraph, class GRef >
inline std::pair<
    typename reverse_graph< BidirectionalGraph, GRef >::adjacency_iterator,
    typename reverse_graph< BidirectionalGraph, GRef >::adjacency_iterator >
adjacent_vertices(
    typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    typedef reverse_graph< BidirectionalGraph, GRef > Graph;
    typename graph_traits< Graph >::out_edge_iterator first, last;
    boost::tie(first, last) = out_edges(u, g);
    typedef
        typename graph_traits< Graph >::adjacency_iterator adjacency_iterator;
    return std::make_pair(adjacency_iterator(first, const_cast< Graph* >(&g)),
        adjacency_iterator(last, const_cast< Graph* >(&g)));
}

template < class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::degree_size_type in_degree(
    const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return out_degree(u, g.m_g);
}

template < class Edge, class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::vertex_descriptor source(
    const detail::reverse_graph_edge_descriptor< Edge >& e,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return target(e.underlying_descx, g.m_g);
}

template < class Edge, class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::vertex_descriptor target(
    const detail::reverse_graph_edge_descriptor< Edge >& e,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return source(e.underlying_descx, g.m_g);
}

template < class BidirectionalGraph, class GRef >
inline typename graph_traits< BidirectionalGraph >::degree_size_type degree(
    const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
    const reverse_graph< BidirectionalGraph, GRef >& g)
{
    return degree(u, g.m_g);
}

namespace detail
{

    template < typename PM > struct reverse_graph_edge_property_map
    {
    private:
        PM underlying_pm;

    public:
        typedef reverse_graph_edge_descriptor<
            typename property_traits< PM >::key_type >
            key_type;
        typedef typename property_traits< PM >::value_type value_type;
        typedef typename property_traits< PM >::reference reference;
        typedef typename property_traits< PM >::category category;

        explicit reverse_graph_edge_property_map(const PM& pm)
        : underlying_pm(pm)
        {
        }

        friend reference get(
            const reverse_graph_edge_property_map& m, const key_type& e)
        {
            return get(m.underlying_pm, e.underlying_descx);
        }

        friend void put(const reverse_graph_edge_property_map& m,
            const key_type& e, const value_type& v)
        {
            put(m.underlying_pm, e.underlying_descx, v);
        }

        reference operator[](const key_type& k) const
        {
            return (this->underlying_pm)[k.underlying_descx];
        }
    };

} // namespace detail

template < class BidirGraph, class GRef, class Property >
struct property_map< reverse_graph< BidirGraph, GRef >, Property >
{
    typedef boost::is_same<
        typename detail::property_kind_from_graph< BidirGraph, Property >::type,
        edge_property_tag >
        is_edge_prop;
    typedef boost::is_const< typename boost::remove_reference< GRef >::type >
        is_ref_const;
    typedef typename boost::mpl::if_< is_ref_const,
        typename property_map< BidirGraph, Property >::const_type,
        typename property_map< BidirGraph, Property >::type >::type orig_type;
    typedef typename property_map< BidirGraph, Property >::const_type
        orig_const_type;
    typedef typename boost::mpl::if_< is_edge_prop,
        detail::reverse_graph_edge_property_map< orig_type >, orig_type >::type
        type;
    typedef typename boost::mpl::if_< is_edge_prop,
        detail::reverse_graph_edge_property_map< orig_const_type >,
        orig_const_type >::type const_type;
};

template < class BidirGraph, class GRef, class Property >
struct property_map< const reverse_graph< BidirGraph, GRef >, Property >
{
    typedef boost::is_same<
        typename detail::property_kind_from_graph< BidirGraph, Property >::type,
        edge_property_tag >
        is_edge_prop;
    typedef typename property_map< BidirGraph, Property >::const_type
        orig_const_type;
    typedef typename boost::mpl::if_< is_edge_prop,
        detail::reverse_graph_edge_property_map< orig_const_type >,
        orig_const_type >::type const_type;
    typedef const_type type;
};

template < class BidirGraph, class GRef, class Property >
typename disable_if< is_same< Property, edge_underlying_t >,
    typename property_map< reverse_graph< BidirGraph, GRef >,
        Property >::type >::type
get(Property p, reverse_graph< BidirGraph, GRef >& g)
{
    return typename property_map< reverse_graph< BidirGraph, GRef >,
        Property >::type(get(p, g.m_g));
}

template < class BidirGraph, class GRef, class Property >
typename disable_if< is_same< Property, edge_underlying_t >,
    typename property_map< reverse_graph< BidirGraph, GRef >,
        Property >::const_type >::type
get(Property p, const reverse_graph< BidirGraph, GRef >& g)
{
    const BidirGraph& gref = g.m_g; // in case GRef is non-const
    return typename property_map< reverse_graph< BidirGraph, GRef >,
        Property >::const_type(get(p, gref));
}

template < class BidirectionalGraph, class GRef, class Property, class Key >
typename disable_if< is_same< Property, edge_underlying_t >,
    typename property_traits<
        typename property_map< reverse_graph< BidirectionalGraph, GRef >,
            Property >::const_type >::value_type >::type
get(Property p, const reverse_graph< BidirectionalGraph, GRef >& g,
    const Key& k)
{
    return get(get(p, g), k);
}

template < class BidirectionalGraph, class GRef, class Property, class Key,
    class Value >
void put(Property p, reverse_graph< BidirectionalGraph, GRef >& g, const Key& k,
    const Value& val)
{
    put(get(p, g), k, val);
}

// Get the underlying descriptor from a reverse_graph's wrapped edge descriptor

namespace detail
{
    template < class E > struct underlying_edge_desc_map_type
    {
        E operator[](const reverse_graph_edge_descriptor< E >& k) const
        {
            return k.underlying_descx;
        }
    };

    template < class E >
    E get(underlying_edge_desc_map_type< E > m,
        const reverse_graph_edge_descriptor< E >& k)
    {
        return m[k];
    }
}

template < class E >
struct property_traits< detail::underlying_edge_desc_map_type< E > >
{
    typedef detail::reverse_graph_edge_descriptor< E > key_type;
    typedef E value_type;
    typedef const E& reference;
    typedef readable_property_map_tag category;
};

template < class Graph, class GRef >
struct property_map< reverse_graph< Graph, GRef >, edge_underlying_t >
{
private:
    typedef typename graph_traits< Graph >::edge_descriptor ed;

public:
    typedef detail::underlying_edge_desc_map_type< ed > type;
    typedef detail::underlying_edge_desc_map_type< ed > const_type;
};

template < typename T > struct is_reverse_graph : boost::mpl::false_
{
};
template < typename G, typename R >
struct is_reverse_graph< reverse_graph< G, R > > : boost::mpl::true_
{
};

template < class G >
typename enable_if< is_reverse_graph< G >,
    detail::underlying_edge_desc_map_type< typename graph_traits<
        typename G::base_type >::edge_descriptor > >::type
get(edge_underlying_t, G&)
{
    return detail::underlying_edge_desc_map_type<
        typename graph_traits< typename G::base_type >::edge_descriptor >();
}

template < class G >
typename enable_if< is_reverse_graph< G >,
    typename graph_traits< typename G::base_type >::edge_descriptor >::type
get(edge_underlying_t, G&, const typename graph_traits< G >::edge_descriptor& k)
{
    return k.underlying_descx;
}

template < class G >
typename enable_if< is_reverse_graph< G >,
    detail::underlying_edge_desc_map_type< typename graph_traits<
        typename G::base_type >::edge_descriptor > >::type
get(edge_underlying_t, const G&)
{
    return detail::underlying_edge_desc_map_type<
        typename graph_traits< typename G::base_type >::edge_descriptor >();
}

template < class G >
typename enable_if< is_reverse_graph< G >,
    typename graph_traits< typename G::base_type >::edge_descriptor >::type
get(edge_underlying_t, const G&,
    const typename graph_traits< G >::edge_descriptor& k)
{
    return k.underlying_descx;
}

// Access to wrapped graph's graph properties

template < typename BidirectionalGraph, typename GRef, typename Tag,
    typename Value >
inline void set_property(const reverse_graph< BidirectionalGraph, GRef >& g,
    Tag tag, const Value& value)
{
    set_property(g.m_g, tag, value);
}

template < typename BidirectionalGraph, typename GRef, typename Tag >
inline typename boost::mpl::if_<
    boost::is_const< typename boost::remove_reference< GRef >::type >,
    const typename graph_property< BidirectionalGraph, Tag >::type&,
    typename graph_property< BidirectionalGraph, Tag >::type& >::type
get_property(const reverse_graph< BidirectionalGraph, GRef >& g, Tag tag)
{
    return get_property(g.m_g, tag);
}

} // namespace boost

#endif