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