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
22namespace 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

source code of boost/boost/graph/edge_list.hpp