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 null_vertex()48 static vertex_descriptor null_vertex() 49 { return traits_type::null_vertex(); } 50 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)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 vertex_and_edge_range(const Graph & g,VertexIterator first_v,VertexIterator last_v,EdgeIterator first_e,EdgeIterator last_e)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> vertices(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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 num_vertices(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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> edges(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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 num_edges(const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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 source(typename vertex_and_edge_range<Graph,VertexIterator,EdgeIterator>::edge_descriptor e,const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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 target(typename vertex_and_edge_range<Graph,VertexIterator,EdgeIterator>::edge_descriptor e,const vertex_and_edge_range<Graph,VertexIterator,EdgeIterator> & g)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> make_vertex_and_edge_range(const Graph & g,VertexIterator first_v,VertexIterator last_v,EdgeIterator first_e,EdgeIterator last_e)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 142