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