[857] | 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 | {
|
---|
| 57 | edge_descriptor() { }
|
---|
| 58 | edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
|
---|
| 59 | 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;
|
---|
| 73 | edge_iterator() { }
|
---|
| 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; }
|
---|
| 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>
|
---|
| 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
|
---|
| 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
|
---|
| 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 |
|
---|
| 119 | 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
|
---|
| 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
|
---|
| 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>
|
---|
| 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
|
---|
| 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
|
---|
| 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 |
|
---|
| 208 | 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
|
---|
| 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
|
---|
| 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;
|
---|
| 277 | edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) {
|
---|
| 278 | m_num_edges = std::distance(first, last);
|
---|
| 279 | }
|
---|
| 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>
|
---|
| 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>
|
---|
| 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 */
|
---|