// (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
|
