reverse_graph.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 274 行

//  (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/tuple/tuple.hpp>

namespace boost {

struct reverse_graph_tag { };

  namespace detail {

    template <bool isEdgeList> struct choose_rev_edge_iter { };
    template <> struct choose_rev_edge_iter<true> {
      template <class G> struct bind_ {
        typedef 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;

    // Constructor
    reverse_graph(GraphRef g) : m_g(g) {}

    // Graph requirements
    typedef typename Traits::vertex_descriptor vertex_descriptor;
    typedef 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 typename Traits::in_edge_iterator out_edge_iterator;
    typedef typename Traits::degree_size_type degree_size_type;

    // BidirectionalGraph requirements
    typedef 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;

    // More typedefs used by detail::edge_property_map, vertex_property_map
    typedef typename BidirectionalGraph::edge_property_type
      edge_property_type;
    typedef typename BidirectionalGraph::vertex_property_type
      vertex_property_type;
    typedef reverse_graph_tag graph_tag;

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

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

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 edges(g.m_g);
}

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

template <class BidirectionalGraph, class GRef>
inline typename 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 BidirectionalGraph::degree_size_type
out_degree(const typename BidirectionalGraph::vertex_descriptor u,
           const reverse_graph<BidirectionalGraph,GRef>& g)
{
    return in_degree(u, g.m_g);
}

template <class BidirectionalGraph, class GRef>
inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
edge(const typename BidirectionalGraph::vertex_descriptor u,
     const typename BidirectionalGraph::vertex_descriptor v,
     const reverse_graph<BidirectionalGraph,GRef>& g)
{
    return edge(v, u, g);
}

template <class BidirectionalGraph, class GRef>
inline std::pair<typename BidirectionalGraph::out_edge_iterator,
    typename BidirectionalGraph::out_edge_iterator>
in_edges(const typename BidirectionalGraph::vertex_descriptor u,
         const reverse_graph<BidirectionalGraph,GRef>& g)
{
    return 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(const typename BidirectionalGraph::vertex_descriptor u,
                  const reverse_graph<BidirectionalGraph,GRef>& g)
{
    typedef reverse_graph<BidirectionalGraph,GRef> Graph;
    typename Graph::out_edge_iterator first, last;
    tie(first, last) = out_edges(u, g);
    typedef typename 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 BidirectionalGraph::degree_size_type
in_degree(const typename 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 Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
{
    return target(e, g.m_g);
}

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


namespace detail {

  struct reverse_graph_vertex_property_selector {
    template <class ReverseGraph, class Property, class Tag>
    struct bind_ {
      typedef typename ReverseGraph::base_type Graph;
      typedef property_map<Graph, Tag> PMap;
      typedef typename PMap::type type;
      typedef typename PMap::const_type const_type;
    };
  };

  struct reverse_graph_edge_property_selector {
    template <class ReverseGraph, class Property, class Tag>
    struct bind_ {
      typedef typename ReverseGraph::base_type Graph;
      typedef property_map<Graph, Tag> PMap;
      typedef typename PMap::type type;
      typedef typename PMap::const_type const_type;
    };
  };

} // namespace detail

template <>
struct vertex_property_selector<reverse_graph_tag> {
  typedef detail::reverse_graph_vertex_property_selector type;
};

template <>
struct edge_property_selector<reverse_graph_tag> {
  typedef detail::reverse_graph_edge_property_selector type;
};

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

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

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

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


} // namespace boost

#endif