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 19 namespace graph 20 { 21 template < typename Graph, typename VertexIterator, typename EdgeIterator > 22 class vertex_and_edge_range 23 { 24 typedef graph_traits< Graph > traits_type; 25 26 public: 27 typedef typename traits_type::directed_category directed_category; 28 typedef 29 typename traits_type::edge_parallel_category edge_parallel_category; 30 struct traversal_category : public virtual vertex_list_graph_tag, 31 public virtual edge_list_graph_tag 32 { 33 }; 34 35 typedef std::size_t vertices_size_type; 36 typedef VertexIterator vertex_iterator; 37 typedef typename std::iterator_traits< VertexIterator >::value_type 38 vertex_descriptor; 39 40 typedef EdgeIterator edge_iterator; 41 typedef typename std::iterator_traits< EdgeIterator >::value_type 42 edge_descriptor; 43 44 typedef std::size_t edges_size_type; 45 46 typedef void adjacency_iterator; 47 typedef void out_edge_iterator; 48 typedef void in_edge_iterator; 49 typedef void degree_size_type; 50 null_vertex()51 static vertex_descriptor null_vertex() 52 { 53 return traits_type::null_vertex(); 54 } 55 vertex_and_edge_range(const Graph & g,VertexIterator first_v,VertexIterator last_v,vertices_size_type n,EdgeIterator first_e,EdgeIterator last_e,edges_size_type m)56 vertex_and_edge_range(const Graph& g, VertexIterator first_v, 57 VertexIterator last_v, vertices_size_type n, EdgeIterator first_e, 58 EdgeIterator last_e, edges_size_type m) 59 : g(&g) 60 , first_vertex(first_v) 61 , last_vertex(last_v) 62 , m_num_vertices(n) 63 , first_edge(first_e) 64 , last_edge(last_e) 65 , m_num_edges(m) 66 { 67 } 68 vertex_and_edge_range(const Graph & g,VertexIterator first_v,VertexIterator last_v,EdgeIterator first_e,EdgeIterator last_e)69 vertex_and_edge_range(const Graph& g, VertexIterator first_v, 70 VertexIterator last_v, EdgeIterator first_e, EdgeIterator last_e) 71 : g(&g) 72 , first_vertex(first_v) 73 , last_vertex(last_v) 74 , first_edge(first_e) 75 , last_edge(last_e) 76 { 77 m_num_vertices = std::distance(first_v, last_v); 78 m_num_edges = std::distance(first_e, last_e); 79 } 80 81 const Graph* g; 82 vertex_iterator first_vertex; 83 vertex_iterator last_vertex; 84 vertices_size_type m_num_vertices; 85 edge_iterator first_edge; 86 edge_iterator last_edge; 87 edges_size_type m_num_edges; 88 }; 89 90 template < typename Graph, typename VertexIterator, typename EdgeIterator > vertices(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)91 inline std::pair< VertexIterator, VertexIterator > vertices( 92 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 93 { 94 return std::make_pair(g.first_vertex, g.last_vertex); 95 } 96 97 template < typename Graph, typename VertexIterator, typename EdgeIterator > 98 inline typename vertex_and_edge_range< Graph, VertexIterator, 99 EdgeIterator >::vertices_size_type num_vertices(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)100 num_vertices( 101 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 102 { 103 return g.m_num_vertices; 104 } 105 106 template < typename Graph, typename VertexIterator, typename EdgeIterator > edges(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)107 inline std::pair< EdgeIterator, EdgeIterator > edges( 108 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 109 { 110 return std::make_pair(g.first_edge, g.last_edge); 111 } 112 113 template < typename Graph, typename VertexIterator, typename EdgeIterator > 114 inline typename vertex_and_edge_range< Graph, VertexIterator, 115 EdgeIterator >::edges_size_type num_edges(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)116 num_edges( 117 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 118 { 119 return g.m_num_edges; 120 } 121 122 template < typename Graph, typename VertexIterator, typename EdgeIterator > 123 inline typename vertex_and_edge_range< Graph, VertexIterator, 124 EdgeIterator >::vertex_descriptor source(typename vertex_and_edge_range<Graph,VertexIterator,EdgeIterator>::edge_descriptor e,const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)125 source(typename vertex_and_edge_range< Graph, VertexIterator, 126 EdgeIterator >::edge_descriptor e, 127 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 128 { 129 return source(e, *g.g); 130 } 131 132 template < typename Graph, typename VertexIterator, typename EdgeIterator > 133 inline typename vertex_and_edge_range< Graph, VertexIterator, 134 EdgeIterator >::vertex_descriptor target(typename vertex_and_edge_range<Graph,VertexIterator,EdgeIterator>::edge_descriptor e,const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)135 target(typename vertex_and_edge_range< Graph, VertexIterator, 136 EdgeIterator >::edge_descriptor e, 137 const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g) 138 { 139 return target(e, *g.g); 140 } 141 142 template < typename Graph, typename VertexIterator, typename EdgeIterator > 143 inline vertex_and_edge_range< Graph, VertexIterator, EdgeIterator > make_vertex_and_edge_range(const Graph & g,VertexIterator first_v,VertexIterator last_v,EdgeIterator first_e,EdgeIterator last_e)144 make_vertex_and_edge_range(const Graph& g, VertexIterator first_v, 145 VertexIterator last_v, EdgeIterator first_e, EdgeIterator last_e) 146 { 147 typedef vertex_and_edge_range< Graph, VertexIterator, EdgeIterator > 148 result_type; 149 return result_type(g, first_v, last_v, first_e, last_e); 150 } 151 152 } // end namespace graph 153 154 using graph::make_vertex_and_edge_range; 155 using graph::vertex_and_edge_range; 156 157 } // end namespace boost 158 #endif // BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP 159