]>
Commit | Line | Data |
---|---|---|
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 |