1 | //======================================================================= |
---|
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
---|
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
---|
4 | // |
---|
5 | // Distributed under the Boost Software License, Version 1.0. (See |
---|
6 | // accompanying file LICENSE_1_0.txt or copy at |
---|
7 | // http://www.boost.org/LICENSE_1_0.txt) |
---|
8 | //======================================================================= |
---|
9 | // |
---|
10 | |
---|
11 | #ifndef BOOST_GRAPH_EDGE_LIST_HPP |
---|
12 | #define BOOST_GRAPH_EDGE_LIST_HPP |
---|
13 | |
---|
14 | #include <iterator> |
---|
15 | #include <boost/config.hpp> |
---|
16 | #include <boost/pending/ct_if.hpp> |
---|
17 | #include <boost/pending/integer_range.hpp> |
---|
18 | #include <boost/graph/graph_traits.hpp> |
---|
19 | #include <boost/graph/properties.hpp> |
---|
20 | |
---|
21 | namespace boost { |
---|
22 | |
---|
23 | // |
---|
24 | // The edge_list class is an EdgeListGraph module that is constructed |
---|
25 | // from a pair of iterators whose value type is a pair of vertex |
---|
26 | // descriptors. |
---|
27 | // |
---|
28 | // For example: |
---|
29 | // |
---|
30 | // typedef std::pair<int,int> E; |
---|
31 | // list<E> elist; |
---|
32 | // ... |
---|
33 | // typedef edge_list<list<E>::iterator> Graph; |
---|
34 | // Graph g(elist.begin(), elist.end()); |
---|
35 | // |
---|
36 | // If the iterators are random access, then Graph::edge_descriptor |
---|
37 | // is of Integral type, otherwise it is a struct, though it is |
---|
38 | // convertible to an Integral type. |
---|
39 | // |
---|
40 | |
---|
41 | struct edge_list_tag { }; |
---|
42 | |
---|
43 | // The implementation class for edge_list. |
---|
44 | template <class G, class EdgeIter, class T, class D> |
---|
45 | class edge_list_impl |
---|
46 | { |
---|
47 | public: |
---|
48 | typedef D edge_id; |
---|
49 | typedef T Vpair; |
---|
50 | typedef typename Vpair::first_type V; |
---|
51 | typedef V vertex_descriptor; |
---|
52 | typedef edge_list_tag graph_tag; |
---|
53 | typedef void edge_property_type; |
---|
54 | |
---|
55 | struct edge_descriptor |
---|
56 | { |
---|
57 | edge_descriptor() { } |
---|
58 | edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { } |
---|
59 | operator edge_id() { return _id; } |
---|
60 | EdgeIter _ptr; |
---|
61 | edge_id _id; |
---|
62 | }; |
---|
63 | typedef edge_descriptor E; |
---|
64 | |
---|
65 | struct edge_iterator |
---|
66 | { |
---|
67 | typedef edge_iterator self; |
---|
68 | typedef E value_type; |
---|
69 | typedef E& reference; |
---|
70 | typedef E* pointer; |
---|
71 | typedef std::ptrdiff_t difference_type; |
---|
72 | typedef std::input_iterator_tag iterator_category; |
---|
73 | edge_iterator() { } |
---|
74 | edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { } |
---|
75 | E operator*() { return E(_iter, _i); } |
---|
76 | self& operator++() { ++_iter; ++_i; return *this; } |
---|
77 | self operator++(int) { self t = *this; ++(*this); return t; } |
---|
78 | bool operator==(const self& x) { return _iter == x._iter; } |
---|
79 | bool operator!=(const self& x) { return _iter != x._iter; } |
---|
80 | EdgeIter _iter; |
---|
81 | edge_id _i; |
---|
82 | }; |
---|
83 | typedef void out_edge_iterator; |
---|
84 | typedef void in_edge_iterator; |
---|
85 | typedef void adjacency_iterator; |
---|
86 | typedef void vertex_iterator; |
---|
87 | }; |
---|
88 | |
---|
89 | template <class G, class EI, class T, class D> |
---|
90 | std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator, |
---|
91 | typename edge_list_impl<G,EI,T,D>::edge_iterator> |
---|
92 | edges(const edge_list_impl<G,EI,T,D>& g_) { |
---|
93 | const G& g = static_cast<const G&>(g_); |
---|
94 | typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator; |
---|
95 | return std::make_pair(edge_iterator(g._first), edge_iterator(g._last)); |
---|
96 | } |
---|
97 | template <class G, class EI, class T, class D> |
---|
98 | typename edge_list_impl<G,EI,T,D>::vertex_descriptor |
---|
99 | source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e, |
---|
100 | const edge_list_impl<G,EI,T,D>&) { |
---|
101 | return (*e._ptr).first; |
---|
102 | } |
---|
103 | template <class G, class EI, class T, class D> |
---|
104 | typename edge_list_impl<G,EI,T,D>::vertex_descriptor |
---|
105 | target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e, |
---|
106 | const edge_list_impl<G,EI,T,D>&) { |
---|
107 | return (*e._ptr).second; |
---|
108 | } |
---|
109 | |
---|
110 | template <class D, class E> |
---|
111 | class el_edge_property_map |
---|
112 | : public put_get_helper<D, el_edge_property_map<D,E> >{ |
---|
113 | public: |
---|
114 | typedef E key_type; |
---|
115 | typedef D value_type; |
---|
116 | typedef D reference; |
---|
117 | typedef readable_property_map_tag category; |
---|
118 | |
---|
119 | value_type operator[](key_type e) const { |
---|
120 | return e._i; |
---|
121 | } |
---|
122 | }; |
---|
123 | struct edge_list_edge_property_selector { |
---|
124 | template <class Graph, class Property, class Tag> |
---|
125 | struct bind_ { |
---|
126 | typedef el_edge_property_map<typename Graph::edge_id, |
---|
127 | typename Graph::edge_descriptor> type; |
---|
128 | typedef type const_type; |
---|
129 | }; |
---|
130 | }; |
---|
131 | template <> |
---|
132 | struct edge_property_selector<edge_list_tag> { |
---|
133 | typedef edge_list_edge_property_selector type; |
---|
134 | }; |
---|
135 | |
---|
136 | template <class G, class EI, class T, class D> |
---|
137 | typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type |
---|
138 | get(edge_index_t, const edge_list_impl<G,EI,T,D>&) { |
---|
139 | typedef typename property_map< edge_list_impl<G,EI,T,D>, |
---|
140 | edge_index_t>::type EdgeIndexMap; |
---|
141 | return EdgeIndexMap(); |
---|
142 | } |
---|
143 | |
---|
144 | template <class G, class EI, class T, class D> |
---|
145 | inline D |
---|
146 | get(edge_index_t, const edge_list_impl<G,EI,T,D>&, |
---|
147 | typename edge_list_impl<G,EI,T,D>::edge_descriptor e) { |
---|
148 | return e._i; |
---|
149 | } |
---|
150 | |
---|
151 | // A specialized implementation for when the iterators are random access. |
---|
152 | |
---|
153 | struct edge_list_ra_tag { }; |
---|
154 | |
---|
155 | template <class G, class EdgeIter, class T, class D> |
---|
156 | class edge_list_impl_ra |
---|
157 | { |
---|
158 | public: |
---|
159 | typedef D edge_id; |
---|
160 | typedef T Vpair; |
---|
161 | typedef typename Vpair::first_type V; |
---|
162 | typedef edge_list_ra_tag graph_tag; |
---|
163 | typedef void edge_property_type; |
---|
164 | |
---|
165 | typedef edge_id edge_descriptor; |
---|
166 | typedef V vertex_descriptor; |
---|
167 | typedef typename boost::integer_range<edge_id>::iterator edge_iterator; |
---|
168 | typedef void out_edge_iterator; |
---|
169 | typedef void in_edge_iterator; |
---|
170 | typedef void adjacency_iterator; |
---|
171 | typedef void vertex_iterator; |
---|
172 | }; |
---|
173 | |
---|
174 | template <class G, class EI, class T, class D> |
---|
175 | std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator, |
---|
176 | typename edge_list_impl_ra<G,EI,T,D>::edge_iterator> |
---|
177 | edges(const edge_list_impl_ra<G,EI,T,D>& g_) |
---|
178 | { |
---|
179 | const G& g = static_cast<const G&>(g_); |
---|
180 | typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator; |
---|
181 | return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first)); |
---|
182 | } |
---|
183 | template <class G, class EI, class T, class D> |
---|
184 | typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor |
---|
185 | source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e, |
---|
186 | const edge_list_impl_ra<G,EI,T,D>& g_) |
---|
187 | { |
---|
188 | const G& g = static_cast<const G&>(g_); |
---|
189 | return g._first[e].first; |
---|
190 | } |
---|
191 | template <class G, class EI, class T, class D> |
---|
192 | typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor |
---|
193 | target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e, |
---|
194 | const edge_list_impl_ra<G,EI,T,D>& g_) |
---|
195 | { |
---|
196 | const G& g = static_cast<const G&>(g_); |
---|
197 | return g._first[e].second; |
---|
198 | } |
---|
199 | template <class E> |
---|
200 | class el_ra_edge_property_map |
---|
201 | : public put_get_helper<E, el_ra_edge_property_map<E> >{ |
---|
202 | public: |
---|
203 | typedef E key_type; |
---|
204 | typedef E value_type; |
---|
205 | typedef E reference; |
---|
206 | typedef readable_property_map_tag category; |
---|
207 | |
---|
208 | value_type operator[](key_type e) const { |
---|
209 | return e; |
---|
210 | } |
---|
211 | }; |
---|
212 | struct edge_list_ra_edge_property_selector { |
---|
213 | template <class Graph, class Property, class Tag> |
---|
214 | struct bind_ { |
---|
215 | typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type; |
---|
216 | typedef type const_type; |
---|
217 | }; |
---|
218 | }; |
---|
219 | template <> |
---|
220 | struct edge_property_selector<edge_list_ra_tag> { |
---|
221 | typedef edge_list_ra_edge_property_selector type; |
---|
222 | }; |
---|
223 | template <class G, class EI, class T, class D> |
---|
224 | inline |
---|
225 | typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type |
---|
226 | get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) { |
---|
227 | typedef typename property_map< edge_list_impl_ra<G,EI,T,D>, |
---|
228 | edge_index_t>::type EdgeIndexMap; |
---|
229 | return EdgeIndexMap(); |
---|
230 | } |
---|
231 | |
---|
232 | template <class G, class EI, class T, class D> |
---|
233 | inline D |
---|
234 | get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&, |
---|
235 | typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) { |
---|
236 | return e; |
---|
237 | } |
---|
238 | |
---|
239 | |
---|
240 | // Some helper classes for determining if the iterators are random access |
---|
241 | template <class Cat> |
---|
242 | struct is_random { |
---|
243 | enum { RET = false }; |
---|
244 | typedef false_type type; |
---|
245 | }; |
---|
246 | template <> |
---|
247 | struct is_random<std::random_access_iterator_tag> { |
---|
248 | enum { RET = true }; typedef true_type type; |
---|
249 | }; |
---|
250 | |
---|
251 | // The edge_list class conditionally inherits from one of the |
---|
252 | // above two classes. |
---|
253 | |
---|
254 | template <class EdgeIter, |
---|
255 | #if !defined BOOST_NO_STD_ITERATOR_TRAITS |
---|
256 | class T = typename std::iterator_traits<EdgeIter>::value_type, |
---|
257 | class D = typename std::iterator_traits<EdgeIter>::difference_type, |
---|
258 | class Cat = typename std::iterator_traits<EdgeIter>::iterator_category> |
---|
259 | #else |
---|
260 | class T, |
---|
261 | class D, |
---|
262 | class Cat> |
---|
263 | #endif |
---|
264 | class edge_list |
---|
265 | : public ct_if_t< typename is_random<Cat>::type, |
---|
266 | edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>, |
---|
267 | edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D> |
---|
268 | >::type |
---|
269 | { |
---|
270 | public: |
---|
271 | typedef directed_tag directed_category; |
---|
272 | typedef allow_parallel_edge_tag edge_parallel_category; |
---|
273 | typedef edge_list_graph_tag traversal_category; |
---|
274 | typedef std::size_t edges_size_type; |
---|
275 | typedef std::size_t vertices_size_type; |
---|
276 | typedef std::size_t degree_size_type; |
---|
277 | edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { |
---|
278 | m_num_edges = std::distance(first, last); |
---|
279 | } |
---|
280 | edge_list(EdgeIter first, EdgeIter last, edges_size_type E) |
---|
281 | : _first(first), _last(last), m_num_edges(E) { } |
---|
282 | |
---|
283 | EdgeIter _first, _last; |
---|
284 | edges_size_type m_num_edges; |
---|
285 | }; |
---|
286 | |
---|
287 | template <class EdgeIter, class T, class D, class Cat> |
---|
288 | std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) { |
---|
289 | return el.m_num_edges; |
---|
290 | } |
---|
291 | |
---|
292 | #ifndef BOOST_NO_STD_ITERATOR_TRAITS |
---|
293 | template <class EdgeIter> |
---|
294 | inline edge_list<EdgeIter> |
---|
295 | make_edge_list(EdgeIter first, EdgeIter last) |
---|
296 | { |
---|
297 | return edge_list<EdgeIter>(first, last); |
---|
298 | } |
---|
299 | #endif |
---|
300 | |
---|
301 | } /* namespace boost */ |
---|
302 | |
---|
303 | #endif /* BOOST_GRAPH_EDGE_LIST_HPP */ |
---|