boost/graph/vertex_and_edge_range.hpp

   1 // Copyright 2004 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9
  10 #ifndef BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
  11 #define BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
  12
  13 #include <boost/graph/graph_traits.hpp>
  14 #include <iterator>
  15
  16 namespace boost {
  17
  18 namespace graph {
  19   template<typename Graph, typename VertexIterator, typename EdgeIterator>
  20   class vertex_and_edge_range
  21   {
  22     typedef graph_traits<Graph> traits_type;
  23
  24   public:
  25     typedef typename traits_type::directed_category directed_category;
  26     typedef typename traits_type::edge_parallel_category
  27       edge_parallel_category;
  28     struct traversal_category
  29       : public virtual vertex_list_graph_tag,
  30         public virtual edge_list_graph_tag { };
  31
  32     typedef std::size_t vertices_size_type;
  33     typedef VertexIterator vertex_iterator;
  34     typedef typename std::iterator_traits<VertexIterator>::value_type
  35       vertex_descriptor;
  36
  37     typedef EdgeIterator edge_iterator;
  38     typedef typename std::iterator_traits<EdgeIterator>::value_type
  39       edge_descriptor;
  40
  41     typedef std::size_t edges_size_type;
  42
  43     typedef void adjacency_iterator;
  44     typedef void out_edge_iterator;
  45     typedef void in_edge_iterator;
  46     typedef void degree_size_type;
  47
  48     static vertex_descriptor null_vertex()
  49     { return traits_type::null_vertex(); }
  50
  51     vertex_and_edge_range(const Graph& g,
  52                           VertexIterator first_v, VertexIterator last_v,
  53                           vertices_size_type n,
  54                           EdgeIterator first_e, EdgeIterator last_e,
  55                           edges_size_type m)
  56       : g(&g),
  57         first_vertex(first_v), last_vertex(last_v), m_num_vertices(n),
  58         first_edge(first_e), last_edge(last_e), m_num_edges(m)
  59     {
  60     }
  61
  62     vertex_and_edge_range(const Graph& g,
  63                           VertexIterator first_v, VertexIterator last_v,
  64                           EdgeIterator first_e, EdgeIterator last_e)
  65       : g(&g),
  66         first_vertex(first_v), last_vertex(last_v),
  67         first_edge(first_e), last_edge(last_e)
  68     {
  69       m_num_vertices = std::distance(first_v, last_v);
  70       m_num_edges = std::distance(first_e, last_e);
  71     }
  72
  73     const Graph* g;
  74     vertex_iterator first_vertex;
  75     vertex_iterator last_vertex;
  76     vertices_size_type m_num_vertices;
  77     edge_iterator first_edge;
  78     edge_iterator last_edge;
  79     edges_size_type m_num_edges;
  80   };
  81
  82   template<typename Graph, typename VertexIterator, typename EdgeIterator>
  83   inline std::pair<VertexIterator, VertexIterator>
  84   vertices(const vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>& g)
  85   { return std::make_pair(g.first_vertex, g.last_vertex); }
  86
  87   template<typename Graph, typename VertexIterator, typename EdgeIterator>
  88   inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
  89                     ::vertices_size_type
  90   num_vertices(const vertex_and_edge_range<Graph, VertexIterator,
  91                                            EdgeIterator>& g)
  92   { return g.m_num_vertices; }
  93
  94   template<typename Graph, typename VertexIterator, typename EdgeIterator>
  95   inline std::pair<EdgeIterator, EdgeIterator>
  96   edges(const vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>& g)
  97   { return std::make_pair(g.first_edge, g.last_edge); }
  98
  99   template<typename Graph, typename VertexIterator, typename EdgeIterator>
 100   inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 101                     ::edges_size_type
 102   num_edges(const vertex_and_edge_range<Graph, VertexIterator,
 103                                         EdgeIterator>& g)
 104   { return g.m_num_edges; }
 105
 106   template<typename Graph, typename VertexIterator, typename EdgeIterator>
 107   inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 108                     ::vertex_descriptor
 109   source(typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 110                     ::edge_descriptor e,
 111          const vertex_and_edge_range<Graph, VertexIterator,
 112                                         EdgeIterator>& g)
 113   { return source(e, *g.g); }
 114
 115   template<typename Graph, typename VertexIterator, typename EdgeIterator>
 116   inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 117                     ::vertex_descriptor
 118   target(typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 119                     ::edge_descriptor e,
 120          const vertex_and_edge_range<Graph, VertexIterator,
 121                                         EdgeIterator>& g)
 122   { return target(e, *g.g); }
 123
 124   template<typename Graph, typename VertexIterator, typename EdgeIterator>
 125   inline vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 126   make_vertex_and_edge_range(const Graph& g,
 127                              VertexIterator first_v, VertexIterator last_v,
 128                              EdgeIterator first_e, EdgeIterator last_e)
 129   {
 130     typedef vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
 131       result_type;
 132     return result_type(g, first_v, last_v, first_e, last_e);
 133   }
 134
 135 } // end namespace graph
 136
 137 using graph::vertex_and_edge_range;
 138 using graph::make_vertex_and_edge_range;
 139
 140 } // end namespace boost
 141 #endif // BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP