1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef BOOST_GRAPH_EDGE_LIST_HPP
12 #define BOOST_GRAPH_EDGE_LIST_HPP
15 #include <boost/config.hpp>
16 #include <boost/mpl/if.hpp>
17 #include <boost/mpl/bool.hpp>
18 #include <boost/pending/integer_range.hpp>
19 #include <boost/graph/graph_traits.hpp>
20 #include <boost/graph/properties.hpp>
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
31 // typedef std::pair<int,int> E;
34 // typedef edge_list<list<E>::iterator> Graph;
35 // Graph g(elist.begin(), elist.end());
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.
42 struct edge_list_tag
{ };
44 // The implementation class for edge_list.
45 template <class G
, class EdgeIter
, class T
, class D
>
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
;
56 struct edge_descriptor
59 edge_descriptor(EdgeIter p
, edge_id id
) : _ptr(p
), _id(id
) { }
60 operator edge_id() { return _id
; }
64 typedef edge_descriptor E
;
68 typedef edge_iterator self
;
72 typedef std::ptrdiff_t difference_type
;
73 typedef std::input_iterator_tag iterator_category
;
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
; }
84 typedef void out_edge_iterator
;
85 typedef void in_edge_iterator
;
86 typedef void adjacency_iterator
;
87 typedef void vertex_iterator
;
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
));
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
;
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
;
111 template <class D
, class E
>
112 class el_edge_property_map
113 : public put_get_helper
<D
, el_edge_property_map
<D
,E
> >{
116 typedef D value_type
;
118 typedef readable_property_map_tag category
;
120 value_type
operator[](key_type e
) const {
124 struct edge_list_edge_property_selector
{
125 template <class Graph
, class Property
, class Tag
>
127 typedef el_edge_property_map
<typename
Graph::edge_id
,
128 typename
Graph::edge_descriptor
> type
;
129 typedef type const_type
;
133 struct edge_property_selector
<edge_list_tag
> {
134 typedef edge_list_edge_property_selector type
;
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();
145 template <class G
, class EI
, class T
, class 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
) {
152 // A specialized implementation for when the iterators are random access.
154 struct edge_list_ra_tag
{ };
156 template <class G
, class EdgeIter
, class T
, class D
>
157 class edge_list_impl_ra
162 typedef typename
Vpair::first_type V
;
163 typedef edge_list_ra_tag graph_tag
;
164 typedef void edge_property_type
;
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
;
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_
)
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
));
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_
)
189 const G
& g
= static_cast<const G
&>(g_
);
190 return g
._first
[e
].first
;
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_
)
197 const G
& g
= static_cast<const G
&>(g_
);
198 return g
._first
[e
].second
;
201 class el_ra_edge_property_map
202 : public put_get_helper
<E
, el_ra_edge_property_map
<E
> >{
205 typedef E value_type
;
207 typedef readable_property_map_tag category
;
209 value_type
operator[](key_type e
) const {
213 struct edge_list_ra_edge_property_selector
{
214 template <class Graph
, class Property
, class Tag
>
216 typedef el_ra_edge_property_map
<typename
Graph::edge_descriptor
> type
;
217 typedef type const_type
;
221 struct edge_property_selector
<edge_list_ra_tag
> {
222 typedef edge_list_ra_edge_property_selector type
;
224 template <class G
, class EI
, class T
, class D
>
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();
233 template <class G
, class EI
, class T
, class 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
) {
241 // Some helper classes for determining if the iterators are random access
244 enum { RET
= false };
245 typedef mpl::false_ type
;
248 struct is_random
<std::random_access_iterator_tag
> {
249 enum { RET
= true }; typedef mpl::true_ type
;
252 // The edge_list class conditionally inherits from one of the
253 // above two classes.
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
>
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
>
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
);
281 edge_list(EdgeIter first
, EdgeIter last
, edges_size_type E
)
282 : _first(first
), _last(last
), m_num_edges(E
) { }
284 EdgeIter _first
, _last
;
285 edges_size_type m_num_edges
;
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
;
293 #ifndef BOOST_NO_STD_ITERATOR_TRAITS
294 template <class EdgeIter
>
295 inline edge_list
<EdgeIter
>
296 make_edge_list(EdgeIter first
, EdgeIter last
)
298 return edge_list
<EdgeIter
>(first
, last
);
302 } /* namespace boost */
304 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */