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/pending/ct_if.hpp>
17 #include <boost/pending/integer_range.hpp>
18 #include <boost/graph/graph_traits.hpp>
19 #include <boost/graph/properties.hpp>
24 // The edge_list class is an EdgeListGraph module that is constructed
25 // from a pair of iterators whose value type is a pair of vertex
30 // typedef std::pair<int,int> E;
33 // typedef edge_list<list<E>::iterator> Graph;
34 // Graph g(elist.begin(), elist.end());
36 // If the iterators are random access, then Graph::edge_descriptor
37 // is of Integral type, otherwise it is a struct, though it is
38 // convertible to an Integral type.
41 struct edge_list_tag { };
43 // The implementation class for edge_list.
44 template <class G, class EdgeIter, class T, class D>
50 typedef typename Vpair::first_type V;
51 typedef V vertex_descriptor;
52 typedef edge_list_tag graph_tag;
53 typedef void edge_property_type;
55 struct edge_descriptor
58 edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
59 operator edge_id() { return _id; }
63 typedef edge_descriptor E;
67 typedef edge_iterator self;
71 typedef std::ptrdiff_t difference_type;
72 typedef std::input_iterator_tag iterator_category;
74 edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
75 E operator*() { return E(_iter, _i); }
76 self& operator++() { ++_iter; ++_i; return *this; }
77 self operator++(int) { self t = *this; ++(*this); return t; }
78 bool operator==(const self& x) { return _iter == x._iter; }
79 bool operator!=(const self& x) { return _iter != x._iter; }
83 typedef void out_edge_iterator;
84 typedef void in_edge_iterator;
85 typedef void adjacency_iterator;
86 typedef void vertex_iterator;
89 template <class G, class EI, class T, class D>
90 std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,
91 typename edge_list_impl<G,EI,T,D>::edge_iterator>
92 edges(const edge_list_impl<G,EI,T,D>& g_) {
93 const G& g = static_cast<const G&>(g_);
94 typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;
95 return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
97 template <class G, class EI, class T, class D>
98 typename edge_list_impl<G,EI,T,D>::vertex_descriptor
99 source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
100 const edge_list_impl<G,EI,T,D>&) {
101 return (*e._ptr).first;
103 template <class G, class EI, class T, class D>
104 typename edge_list_impl<G,EI,T,D>::vertex_descriptor
105 target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
106 const edge_list_impl<G,EI,T,D>&) {
107 return (*e._ptr).second;
110 template <class D, class E>
111 class el_edge_property_map
112 : public put_get_helper<D, el_edge_property_map<D,E> >{
115 typedef D value_type;
117 typedef readable_property_map_tag category;
119 value_type operator[](key_type e) const {
123 struct edge_list_edge_property_selector {
124 template <class Graph, class Property, class Tag>
126 typedef el_edge_property_map<typename Graph::edge_id,
127 typename Graph::edge_descriptor> type;
128 typedef type const_type;
132 struct edge_property_selector<edge_list_tag> {
133 typedef edge_list_edge_property_selector type;
136 template <class G, class EI, class T, class D>
137 typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type
138 get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {
139 typedef typename property_map< edge_list_impl<G,EI,T,D>,
140 edge_index_t>::type EdgeIndexMap;
141 return EdgeIndexMap();
144 template <class G, class EI, class T, class D>
146 get(edge_index_t, const edge_list_impl<G,EI,T,D>&,
147 typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {
151 // A specialized implementation for when the iterators are random access.
153 struct edge_list_ra_tag { };
155 template <class G, class EdgeIter, class T, class D>
156 class edge_list_impl_ra
161 typedef typename Vpair::first_type V;
162 typedef edge_list_ra_tag graph_tag;
163 typedef void edge_property_type;
165 typedef edge_id edge_descriptor;
166 typedef V vertex_descriptor;
167 typedef typename boost::integer_range<edge_id>::iterator edge_iterator;
168 typedef void out_edge_iterator;
169 typedef void in_edge_iterator;
170 typedef void adjacency_iterator;
171 typedef void vertex_iterator;
174 template <class G, class EI, class T, class D>
175 std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,
176 typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>
177 edges(const edge_list_impl_ra<G,EI,T,D>& g_)
179 const G& g = static_cast<const G&>(g_);
180 typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;
181 return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
183 template <class G, class EI, class T, class D>
184 typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
185 source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
186 const edge_list_impl_ra<G,EI,T,D>& g_)
188 const G& g = static_cast<const G&>(g_);
189 return g._first[e].first;
191 template <class G, class EI, class T, class D>
192 typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
193 target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
194 const edge_list_impl_ra<G,EI,T,D>& g_)
196 const G& g = static_cast<const G&>(g_);
197 return g._first[e].second;
200 class el_ra_edge_property_map
201 : public put_get_helper<E, el_ra_edge_property_map<E> >{
204 typedef E value_type;
206 typedef readable_property_map_tag category;
208 value_type operator[](key_type e) const {
212 struct edge_list_ra_edge_property_selector {
213 template <class Graph, class Property, class Tag>
215 typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;
216 typedef type const_type;
220 struct edge_property_selector<edge_list_ra_tag> {
221 typedef edge_list_ra_edge_property_selector type;
223 template <class G, class EI, class T, class D>
225 typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type
226 get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {
227 typedef typename property_map< edge_list_impl_ra<G,EI,T,D>,
228 edge_index_t>::type EdgeIndexMap;
229 return EdgeIndexMap();
232 template <class G, class EI, class T, class D>
234 get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&,
235 typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {
240 // Some helper classes for determining if the iterators are random access
243 enum { RET = false };
244 typedef false_type type;
247 struct is_random<std::random_access_iterator_tag> {
248 enum { RET = true }; typedef true_type type;
251 // The edge_list class conditionally inherits from one of the
252 // above two classes.
254 template <class EdgeIter,
255 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
256 class T = typename std::iterator_traits<EdgeIter>::value_type,
257 class D = typename std::iterator_traits<EdgeIter>::difference_type,
258 class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>
265 : public ct_if_t< typename is_random<Cat>::type,
266 edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,
267 edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>
271 typedef directed_tag directed_category;
272 typedef allow_parallel_edge_tag edge_parallel_category;
273 typedef edge_list_graph_tag traversal_category;
274 typedef std::size_t edges_size_type;
275 typedef std::size_t vertices_size_type;
276 typedef std::size_t degree_size_type;
277 edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) {
278 m_num_edges = std::distance(first, last);
280 edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
281 : _first(first), _last(last), m_num_edges(E) { }
283 EdgeIter _first, _last;
284 edges_size_type m_num_edges;
287 template <class EdgeIter, class T, class D, class Cat>
288 std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {
289 return el.m_num_edges;
292 #ifndef BOOST_NO_STD_ITERATOR_TRAITS
293 template <class EdgeIter>
294 inline edge_list<EdgeIter>
295 make_edge_list(EdgeIter first, EdgeIter last)
297 return edge_list<EdgeIter>(first, last);
301 } /* namespace boost */
303 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */