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