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/pending/ct_if.hpp> 17 #include <boost/pending/integer_range.hpp> 18 #include <boost/graph/graph_traits.hpp> 19 #include <boost/graph/properties.hpp> 20 21 namespace boost { 22 23 // 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 26 // descriptors. 27 // 28 // For example: 29 // 30 // typedef std::pair<int,int> E; 31 // list<E> elist; 32 // ... 33 // typedef edge_list<list<E>::iterator> Graph; 34 // Graph g(elist.begin(), elist.end()); 35 // 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. 39 // 40 41 struct edge_list_tag { }; 42 43 // The implementation class for edge_list. 44 template <class G, class EdgeIter, class T, class D> 45 class edge_list_impl 46 { 47 public: 48 typedef D edge_id; 49 typedef T Vpair; 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; 54 55 struct edge_descriptor 56 { edge_descriptorboost::edge_list_impl::edge_descriptor57 edge_descriptor() { } edge_descriptorboost::edge_list_impl::edge_descriptor58 edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { } operator edge_idboost::edge_list_impl::edge_descriptor59 operator edge_id() { return _id; } 60 EdgeIter _ptr; 61 edge_id _id; 62 }; 63 typedef edge_descriptor E; 64 65 struct edge_iterator 66 { 67 typedef edge_iterator self; 68 typedef E value_type; 69 typedef E& reference; 70 typedef E* pointer; 71 typedef std::ptrdiff_t difference_type; 72 typedef std::input_iterator_tag iterator_category; edge_iteratorboost::edge_list_impl::edge_iterator73 edge_iterator() { } edge_iteratorboost::edge_list_impl::edge_iterator74 edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { } operator *boost::edge_list_impl::edge_iterator75 E operator*() { return E(_iter, _i); } operator ++boost::edge_list_impl::edge_iterator76 self& operator++() { ++_iter; ++_i; return *this; } operator ++boost::edge_list_impl::edge_iterator77 self operator++(int) { self t = *this; ++(*this); return t; } operator ==boost::edge_list_impl::edge_iterator78 bool operator==(const self& x) { return _iter == x._iter; } operator !=boost::edge_list_impl::edge_iterator79 bool operator!=(const self& x) { return _iter != x._iter; } 80 EdgeIter _iter; 81 edge_id _i; 82 }; 83 typedef void out_edge_iterator; 84 typedef void in_edge_iterator; 85 typedef void adjacency_iterator; 86 typedef void vertex_iterator; 87 }; 88 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> edges(const edge_list_impl<G,EI,T,D> & g_)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)); 96 } 97 template <class G, class EI, class T, class D> 98 typename edge_list_impl<G,EI,T,D>::vertex_descriptor source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,const edge_list_impl<G,EI,T,D> &)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; 102 } 103 template <class G, class EI, class T, class D> 104 typename edge_list_impl<G,EI,T,D>::vertex_descriptor target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,const edge_list_impl<G,EI,T,D> &)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; 108 } 109 110 template <class D, class E> 111 class el_edge_property_map 112 : public put_get_helper<D, el_edge_property_map<D,E> >{ 113 public: 114 typedef E key_type; 115 typedef D value_type; 116 typedef D reference; 117 typedef readable_property_map_tag category; 118 operator [](key_type e) const119 value_type operator[](key_type e) const { 120 return e._i; 121 } 122 }; 123 struct edge_list_edge_property_selector { 124 template <class Graph, class Property, class Tag> 125 struct bind_ { 126 typedef el_edge_property_map<typename Graph::edge_id, 127 typename Graph::edge_descriptor> type; 128 typedef type const_type; 129 }; 130 }; 131 template <> 132 struct edge_property_selector<edge_list_tag> { 133 typedef edge_list_edge_property_selector type; 134 }; 135 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 get(edge_index_t,const edge_list_impl<G,EI,T,D> &)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(); 142 } 143 144 template <class G, class EI, class T, class D> 145 inline D get(edge_index_t,const edge_list_impl<G,EI,T,D> &,typename edge_list_impl<G,EI,T,D>::edge_descriptor e)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) { 148 return e._i; 149 } 150 151 // A specialized implementation for when the iterators are random access. 152 153 struct edge_list_ra_tag { }; 154 155 template <class G, class EdgeIter, class T, class D> 156 class edge_list_impl_ra 157 { 158 public: 159 typedef D edge_id; 160 typedef T Vpair; 161 typedef typename Vpair::first_type V; 162 typedef edge_list_ra_tag graph_tag; 163 typedef void edge_property_type; 164 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; 172 }; 173 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> edges(const edge_list_impl_ra<G,EI,T,D> & g_)177 edges(const edge_list_impl_ra<G,EI,T,D>& g_) 178 { 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)); 182 } 183 template <class G, class EI, class T, class D> 184 typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,const edge_list_impl_ra<G,EI,T,D> & g_)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_) 187 { 188 const G& g = static_cast<const G&>(g_); 189 return g._first[e].first; 190 } 191 template <class G, class EI, class T, class D> 192 typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,const edge_list_impl_ra<G,EI,T,D> & g_)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_) 195 { 196 const G& g = static_cast<const G&>(g_); 197 return g._first[e].second; 198 } 199 template <class E> 200 class el_ra_edge_property_map 201 : public put_get_helper<E, el_ra_edge_property_map<E> >{ 202 public: 203 typedef E key_type; 204 typedef E value_type; 205 typedef E reference; 206 typedef readable_property_map_tag category; 207 operator [](key_type e) const208 value_type operator[](key_type e) const { 209 return e; 210 } 211 }; 212 struct edge_list_ra_edge_property_selector { 213 template <class Graph, class Property, class Tag> 214 struct bind_ { 215 typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type; 216 typedef type const_type; 217 }; 218 }; 219 template <> 220 struct edge_property_selector<edge_list_ra_tag> { 221 typedef edge_list_ra_edge_property_selector type; 222 }; 223 template <class G, class EI, class T, class D> 224 inline 225 typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type get(edge_index_t,const edge_list_impl_ra<G,EI,T,D> &)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(); 230 } 231 232 template <class G, class EI, class T, class D> 233 inline D get(edge_index_t,const edge_list_impl_ra<G,EI,T,D> &,typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e)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) { 236 return e; 237 } 238 239 240 // Some helper classes for determining if the iterators are random access 241 template <class Cat> 242 struct is_random { 243 enum { RET = false }; 244 typedef false_type type; 245 }; 246 template <> 247 struct is_random<std::random_access_iterator_tag> { 248 enum { RET = true }; typedef true_type type; 249 }; 250 251 // The edge_list class conditionally inherits from one of the 252 // above two classes. 253 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> 259 #else 260 class T, 261 class D, 262 class Cat> 263 #endif 264 class edge_list 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> 268 >::type 269 { 270 public: 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; edge_list(EdgeIter first,EdgeIter last)277 edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { 278 m_num_edges = std::distance(first, last); 279 } edge_list(EdgeIter first,EdgeIter last,edges_size_type E)280 edge_list(EdgeIter first, EdgeIter last, edges_size_type E) 281 : _first(first), _last(last), m_num_edges(E) { } 282 283 EdgeIter _first, _last; 284 edges_size_type m_num_edges; 285 }; 286 287 template <class EdgeIter, class T, class D, class Cat> num_edges(const edge_list<EdgeIter,T,D,Cat> & el)288 std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) { 289 return el.m_num_edges; 290 } 291 292 #ifndef BOOST_NO_STD_ITERATOR_TRAITS 293 template <class EdgeIter> 294 inline edge_list<EdgeIter> make_edge_list(EdgeIter first,EdgeIter last)295 make_edge_list(EdgeIter first, EdgeIter last) 296 { 297 return edge_list<EdgeIter>(first, last); 298 } 299 #endif 300 301 } /* namespace boost */ 302 303 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */ 304