boost/graph/edge_list.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 //
0010
0011 #ifndef BOOST_GRAPH_EDGE_LIST_HPP
0012 #define BOOST_GRAPH_EDGE_LIST_HPP
0013
0014 #include <iterator>
0015 #include <boost/config.hpp>
0016 #include <boost/mpl/if.hpp>
0017 #include <boost/mpl/bool.hpp>
0018 #include <boost/range/irange.hpp>
0019 #include <boost/graph/graph_traits.hpp>
0020 #include <boost/graph/properties.hpp>
0021
0022 namespace boost
0023 {
0024
0025 //
0026 // The edge_list class is an EdgeListGraph module that is constructed
0027 // from a pair of iterators whose value type is a pair of vertex
0028 // descriptors.
0029 //
0030 // For example:
0031 //
0032 //  typedef std::pair<int,int> E;
0033 //  list<E> elist;
0034 //  ...
0035 //  typedef edge_list<list<E>::iterator> Graph;
0036 //  Graph g(elist.begin(), elist.end());
0037 //
0038 // If the iterators are random access, then Graph::edge_descriptor
0039 // is of Integral type, otherwise it is a struct, though it is
0040 // convertible to an Integral type.
0041 //
0042
0043 struct edge_list_tag
0044 {
0045 };
0046
0047 // The implementation class for edge_list.
0048 template < class G, class EdgeIter, class T, class D > class edge_list_impl
0049 {
0050 public:
0051     typedef D edge_id;
0052     typedef T Vpair;
0053     typedef typename Vpair::first_type V;
0054     typedef V vertex_descriptor;
0055     typedef edge_list_tag graph_tag;
0056     typedef void edge_property_type;
0057
0058     struct edge_descriptor
0059     {
0060         edge_descriptor() {}
0061         edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) {}
0062         operator edge_id() { return _id; }
0063         EdgeIter _ptr;
0064         edge_id _id;
0065     };
0066     typedef edge_descriptor E;
0067
0068     struct edge_iterator
0069     {
0070         typedef edge_iterator self;
0071         typedef E value_type;
0072         typedef E& reference;
0073         typedef E* pointer;
0074         typedef std::ptrdiff_t difference_type;
0075         typedef std::input_iterator_tag iterator_category;
0076         edge_iterator() {}
0077         edge_iterator(EdgeIter iter) : _iter(iter), _i(0) {}
0078         E operator*() { return E(_iter, _i); }
0079         self& operator++()
0080         {
0081             ++_iter;
0082             ++_i;
0083             return *this;
0084         }
0085         self operator++(int)
0086         {
0087             self t = *this;
0088             ++(*this);
0089             return t;
0090         }
0091         bool operator==(const self& x) { return _iter == x._iter; }
0092         bool operator!=(const self& x) { return _iter != x._iter; }
0093         EdgeIter _iter;
0094         edge_id _i;
0095     };
0096     typedef void out_edge_iterator;
0097     typedef void in_edge_iterator;
0098     typedef void adjacency_iterator;
0099     typedef void vertex_iterator;
0100 };
0101
0102 template < class G, class EI, class T, class D >
0103 std::pair< typename edge_list_impl< G, EI, T, D >::edge_iterator,
0104     typename edge_list_impl< G, EI, T, D >::edge_iterator >
0105 edges(const edge_list_impl< G, EI, T, D >& g_)
0106 {
0107     const G& g = static_cast< const G& >(g_);
0108     typedef typename edge_list_impl< G, EI, T, D >::edge_iterator edge_iterator;
0109     return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
0110 }
0111 template < class G, class EI, class T, class D >
0112 typename edge_list_impl< G, EI, T, D >::vertex_descriptor source(
0113     typename edge_list_impl< G, EI, T, D >::edge_descriptor e,
0114     const edge_list_impl< G, EI, T, D >&)
0115 {
0116     return (*e._ptr).first;
0117 }
0118 template < class G, class EI, class T, class D >
0119 typename edge_list_impl< G, EI, T, D >::vertex_descriptor target(
0120     typename edge_list_impl< G, EI, T, D >::edge_descriptor e,
0121     const edge_list_impl< G, EI, T, D >&)
0122 {
0123     return (*e._ptr).second;
0124 }
0125
0126 template < class D, class E >
0127 class el_edge_property_map
0128 : public put_get_helper< D, el_edge_property_map< D, E > >
0129 {
0130 public:
0131     typedef E key_type;
0132     typedef D value_type;
0133     typedef D reference;
0134     typedef readable_property_map_tag category;
0135
0136     value_type operator[](key_type e) const { return e._i; }
0137 };
0138 struct edge_list_edge_property_selector
0139 {
0140     template < class Graph, class Property, class Tag > struct bind_
0141     {
0142         typedef el_edge_property_map< typename Graph::edge_id,
0143             typename Graph::edge_descriptor >
0144             type;
0145         typedef type const_type;
0146     };
0147 };
0148 template <> struct edge_property_selector< edge_list_tag >
0149 {
0150     typedef edge_list_edge_property_selector type;
0151 };
0152
0153 template < class G, class EI, class T, class D >
0154 typename property_map< edge_list_impl< G, EI, T, D >, edge_index_t >::type get(
0155     edge_index_t, const edge_list_impl< G, EI, T, D >&)
0156 {
0157     typedef typename property_map< edge_list_impl< G, EI, T, D >,
0158         edge_index_t >::type EdgeIndexMap;
0159     return EdgeIndexMap();
0160 }
0161
0162 template < class G, class EI, class T, class D >
0163 inline D get(edge_index_t, const edge_list_impl< G, EI, T, D >&,
0164     typename edge_list_impl< G, EI, T, D >::edge_descriptor e)
0165 {
0166     return e._i;
0167 }
0168
0169 // A specialized implementation for when the iterators are random access.
0170
0171 struct edge_list_ra_tag
0172 {
0173 };
0174
0175 template < class G, class EdgeIter, class T, class D > class edge_list_impl_ra
0176 {
0177 public:
0178     typedef D edge_id;
0179     typedef T Vpair;
0180     typedef typename Vpair::first_type V;
0181     typedef edge_list_ra_tag graph_tag;
0182     typedef void edge_property_type;
0183
0184     typedef edge_id edge_descriptor;
0185     typedef V vertex_descriptor;
0186     typedef typename boost::integer_range< edge_id >::iterator edge_iterator;
0187     typedef void out_edge_iterator;
0188     typedef void in_edge_iterator;
0189     typedef void adjacency_iterator;
0190     typedef void vertex_iterator;
0191 };
0192
0193 template < class G, class EI, class T, class D >
0194 std::pair< typename edge_list_impl_ra< G, EI, T, D >::edge_iterator,
0195     typename edge_list_impl_ra< G, EI, T, D >::edge_iterator >
0196 edges(const edge_list_impl_ra< G, EI, T, D >& g_)
0197 {
0198     const G& g = static_cast< const G& >(g_);
0199     typedef
0200         typename edge_list_impl_ra< G, EI, T, D >::edge_iterator edge_iterator;
0201     return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
0202 }
0203 template < class G, class EI, class T, class D >
0204 typename edge_list_impl_ra< G, EI, T, D >::vertex_descriptor source(
0205     typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e,
0206     const edge_list_impl_ra< G, EI, T, D >& g_)
0207 {
0208     const G& g = static_cast< const G& >(g_);
0209     return g._first[e].first;
0210 }
0211 template < class G, class EI, class T, class D >
0212 typename edge_list_impl_ra< G, EI, T, D >::vertex_descriptor target(
0213     typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e,
0214     const edge_list_impl_ra< G, EI, T, D >& g_)
0215 {
0216     const G& g = static_cast< const G& >(g_);
0217     return g._first[e].second;
0218 }
0219 template < class E >
0220 class el_ra_edge_property_map
0221 : public put_get_helper< E, el_ra_edge_property_map< E > >
0222 {
0223 public:
0224     typedef E key_type;
0225     typedef E value_type;
0226     typedef E reference;
0227     typedef readable_property_map_tag category;
0228
0229     value_type operator[](key_type e) const { return e; }
0230 };
0231 struct edge_list_ra_edge_property_selector
0232 {
0233     template < class Graph, class Property, class Tag > struct bind_
0234     {
0235         typedef el_ra_edge_property_map< typename Graph::edge_descriptor > type;
0236         typedef type const_type;
0237     };
0238 };
0239 template <> struct edge_property_selector< edge_list_ra_tag >
0240 {
0241     typedef edge_list_ra_edge_property_selector type;
0242 };
0243 template < class G, class EI, class T, class D >
0244 inline typename property_map< edge_list_impl_ra< G, EI, T, D >,
0245     edge_index_t >::type
0246 get(edge_index_t, const edge_list_impl_ra< G, EI, T, D >&)
0247 {
0248     typedef typename property_map< edge_list_impl_ra< G, EI, T, D >,
0249         edge_index_t >::type EdgeIndexMap;
0250     return EdgeIndexMap();
0251 }
0252
0253 template < class G, class EI, class T, class D >
0254 inline D get(edge_index_t, const edge_list_impl_ra< G, EI, T, D >&,
0255     typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e)
0256 {
0257     return e;
0258 }
0259
0260 // Some helper classes for determining if the iterators are random access
0261 template < class Cat > struct is_random
0262 {
0263     enum
0264     {
0265         RET = false
0266     };
0267     typedef mpl::false_ type;
0268 };
0269 template <> struct is_random< std::random_access_iterator_tag >
0270 {
0271     enum
0272     {
0273         RET = true
0274     };
0275     typedef mpl::true_ type;
0276 };
0277
0278 // The edge_list class conditionally inherits from one of the
0279 // above two classes.
0280
0281 template < class EdgeIter,
0282 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
0283     class T = typename std::iterator_traits< EdgeIter >::value_type,
0284     class D = typename std::iterator_traits< EdgeIter >::difference_type,
0285     class Cat = typename std::iterator_traits< EdgeIter >::iterator_category >
0286 #else
0287     class T, class D, class Cat >
0288 #endif
0289 class edge_list
0290 : public mpl::if_< typename is_random< Cat >::type,
0291       edge_list_impl_ra< edge_list< EdgeIter, T, D, Cat >, EdgeIter, T, D >,
0292       edge_list_impl< edge_list< EdgeIter, T, D, Cat >, EdgeIter, T, D > >::type
0293 {
0294 public:
0295     typedef directed_tag directed_category;
0296     typedef allow_parallel_edge_tag edge_parallel_category;
0297     typedef edge_list_graph_tag traversal_category;
0298     typedef std::size_t edges_size_type;
0299     typedef std::size_t vertices_size_type;
0300     typedef std::size_t degree_size_type;
0301     edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last)
0302     {
0303         m_num_edges = std::distance(first, last);
0304     }
0305     edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
0306     : _first(first), _last(last), m_num_edges(E)
0307     {
0308     }
0309
0310     EdgeIter _first, _last;
0311     edges_size_type m_num_edges;
0312 };
0313
0314 template < class EdgeIter, class T, class D, class Cat >
0315 std::size_t num_edges(const edge_list< EdgeIter, T, D, Cat >& el)
0316 {
0317     return el.m_num_edges;
0318 }
0319
0320 #ifndef BOOST_NO_STD_ITERATOR_TRAITS
0321 template < class EdgeIter >
0322 inline edge_list< EdgeIter > make_edge_list(EdgeIter first, EdgeIter last)
0323 {
0324     return edge_list< EdgeIter >(first, last);
0325 }
0326 #endif
0327
0328 } /* namespace boost */
0329
0330 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */