epoc32/include/stdapis/boost/graph/edge_list.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
     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 */