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
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2
     3
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2
     4
//
williamr@2
     5
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     6
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     7
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     8
//=======================================================================
williamr@2
     9
//
williamr@2
    10
williamr@2
    11
#ifndef BOOST_GRAPH_EDGE_LIST_HPP
williamr@2
    12
#define BOOST_GRAPH_EDGE_LIST_HPP
williamr@2
    13
williamr@2
    14
#include <iterator>
williamr@2
    15
#include <boost/config.hpp>
williamr@2
    16
#include <boost/pending/ct_if.hpp>
williamr@2
    17
#include <boost/pending/integer_range.hpp>
williamr@2
    18
#include <boost/graph/graph_traits.hpp>
williamr@2
    19
#include <boost/graph/properties.hpp>
williamr@2
    20
williamr@2
    21
namespace boost {
williamr@2
    22
williamr@2
    23
  //
williamr@2
    24
  // The edge_list class is an EdgeListGraph module that is constructed
williamr@2
    25
  // from a pair of iterators whose value type is a pair of vertex
williamr@2
    26
  // descriptors.
williamr@2
    27
  //
williamr@2
    28
  // For example:
williamr@2
    29
  //
williamr@2
    30
  //  typedef std::pair<int,int> E;
williamr@2
    31
  //  list<E> elist;
williamr@2
    32
  //  ...
williamr@2
    33
  //  typedef edge_list<list<E>::iterator> Graph;
williamr@2
    34
  //  Graph g(elist.begin(), elist.end());
williamr@2
    35
  //
williamr@2
    36
  // If the iterators are random access, then Graph::edge_descriptor
williamr@2
    37
  // is of Integral type, otherwise it is a struct, though it is
williamr@2
    38
  // convertible to an Integral type.
williamr@2
    39
  // 
williamr@2
    40
williamr@2
    41
  struct edge_list_tag { };
williamr@2
    42
williamr@2
    43
  // The implementation class for edge_list.
williamr@2
    44
  template <class G, class EdgeIter, class T, class D>
williamr@2
    45
  class edge_list_impl
williamr@2
    46
  {
williamr@2
    47
  public:
williamr@2
    48
    typedef D edge_id;
williamr@2
    49
    typedef T Vpair;
williamr@2
    50
    typedef typename Vpair::first_type V;
williamr@2
    51
    typedef V vertex_descriptor;
williamr@2
    52
    typedef edge_list_tag graph_tag;
williamr@2
    53
    typedef void edge_property_type;
williamr@2
    54
williamr@2
    55
    struct edge_descriptor
williamr@2
    56
    {
williamr@2
    57
      edge_descriptor() { }
williamr@2
    58
      edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
williamr@2
    59
      operator edge_id() { return _id; }
williamr@2
    60
      EdgeIter _ptr;
williamr@2
    61
      edge_id _id;
williamr@2
    62
    };
williamr@2
    63
    typedef edge_descriptor E;
williamr@2
    64
williamr@2
    65
    struct edge_iterator
williamr@2
    66
    {
williamr@2
    67
      typedef edge_iterator self;
williamr@2
    68
      typedef E value_type;
williamr@2
    69
      typedef E& reference;
williamr@2
    70
      typedef E* pointer;
williamr@2
    71
      typedef std::ptrdiff_t difference_type;
williamr@2
    72
      typedef std::input_iterator_tag iterator_category;
williamr@2
    73
      edge_iterator() { }
williamr@2
    74
      edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
williamr@2
    75
      E operator*() { return E(_iter, _i); }
williamr@2
    76
      self& operator++() { ++_iter; ++_i; return *this; }
williamr@2
    77
      self operator++(int) { self t = *this; ++(*this); return t; }
williamr@2
    78
      bool operator==(const self& x) { return _iter == x._iter; }
williamr@2
    79
      bool operator!=(const self& x) { return _iter != x._iter; }
williamr@2
    80
      EdgeIter _iter;
williamr@2
    81
      edge_id _i;
williamr@2
    82
    };
williamr@2
    83
    typedef void out_edge_iterator;
williamr@2
    84
    typedef void in_edge_iterator;
williamr@2
    85
    typedef void adjacency_iterator;
williamr@2
    86
    typedef void vertex_iterator;
williamr@2
    87
  };
williamr@2
    88
williamr@2
    89
  template <class G, class EI, class T, class D>
williamr@2
    90
  std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,
williamr@2
    91
            typename edge_list_impl<G,EI,T,D>::edge_iterator>
williamr@2
    92
  edges(const edge_list_impl<G,EI,T,D>& g_) {
williamr@2
    93
    const G& g = static_cast<const G&>(g_);
williamr@2
    94
    typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;
williamr@2
    95
    return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
williamr@2
    96
  }
williamr@2
    97
  template <class G, class EI, class T, class D>
williamr@2
    98
  typename edge_list_impl<G,EI,T,D>::vertex_descriptor
williamr@2
    99
  source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
williamr@2
   100
         const edge_list_impl<G,EI,T,D>&) {
williamr@2
   101
    return (*e._ptr).first;
williamr@2
   102
  }
williamr@2
   103
  template <class G, class EI, class T, class D>
williamr@2
   104
  typename edge_list_impl<G,EI,T,D>::vertex_descriptor
williamr@2
   105
  target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
williamr@2
   106
           const edge_list_impl<G,EI,T,D>&) {
williamr@2
   107
    return (*e._ptr).second;
williamr@2
   108
  }
williamr@2
   109
williamr@2
   110
  template <class D, class E>
williamr@2
   111
  class el_edge_property_map
williamr@2
   112
    : public put_get_helper<D, el_edge_property_map<D,E> >{
williamr@2
   113
  public:
williamr@2
   114
    typedef E key_type;
williamr@2
   115
    typedef D value_type;
williamr@2
   116
    typedef D reference;
williamr@2
   117
    typedef readable_property_map_tag category;
williamr@2
   118
williamr@2
   119
    value_type operator[](key_type e) const {
williamr@2
   120
      return e._i;
williamr@2
   121
    }
williamr@2
   122
  };
williamr@2
   123
  struct edge_list_edge_property_selector {
williamr@2
   124
    template <class Graph, class Property, class Tag>
williamr@2
   125
    struct bind_ {
williamr@2
   126
      typedef el_edge_property_map<typename Graph::edge_id,
williamr@2
   127
          typename Graph::edge_descriptor> type;
williamr@2
   128
      typedef type const_type;
williamr@2
   129
    };
williamr@2
   130
  };
williamr@2
   131
  template <>  
williamr@2
   132
  struct edge_property_selector<edge_list_tag> {
williamr@2
   133
    typedef edge_list_edge_property_selector type;
williamr@2
   134
  };
williamr@2
   135
williamr@2
   136
  template <class G, class EI, class T, class D>
williamr@2
   137
  typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type
williamr@2
   138
  get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {
williamr@2
   139
    typedef typename property_map< edge_list_impl<G,EI,T,D>, 
williamr@2
   140
      edge_index_t>::type EdgeIndexMap;
williamr@2
   141
    return EdgeIndexMap();
williamr@2
   142
  }
williamr@2
   143
williamr@2
   144
  template <class G, class EI, class T, class D>
williamr@2
   145
  inline D
williamr@2
   146
  get(edge_index_t, const edge_list_impl<G,EI,T,D>&,
williamr@2
   147
      typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {
williamr@2
   148
    return e._i;
williamr@2
   149
  }
williamr@2
   150
williamr@2
   151
  // A specialized implementation for when the iterators are random access.
williamr@2
   152
williamr@2
   153
  struct edge_list_ra_tag { };
williamr@2
   154
williamr@2
   155
  template <class G, class EdgeIter, class T, class D>
williamr@2
   156
  class edge_list_impl_ra
williamr@2
   157
  {
williamr@2
   158
  public:
williamr@2
   159
    typedef D edge_id;
williamr@2
   160
    typedef T Vpair;
williamr@2
   161
    typedef typename Vpair::first_type V;
williamr@2
   162
    typedef edge_list_ra_tag graph_tag;
williamr@2
   163
    typedef void edge_property_type;
williamr@2
   164
williamr@2
   165
    typedef edge_id edge_descriptor;
williamr@2
   166
    typedef V vertex_descriptor;
williamr@2
   167
    typedef typename boost::integer_range<edge_id>::iterator edge_iterator;
williamr@2
   168
    typedef void out_edge_iterator;
williamr@2
   169
    typedef void in_edge_iterator;
williamr@2
   170
    typedef void adjacency_iterator;
williamr@2
   171
    typedef void vertex_iterator;
williamr@2
   172
  };
williamr@2
   173
williamr@2
   174
  template <class G, class EI, class T, class D>
williamr@2
   175
  std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,
williamr@2
   176
            typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>
williamr@2
   177
  edges(const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2
   178
  {
williamr@2
   179
    const G& g = static_cast<const G&>(g_);
williamr@2
   180
    typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;
williamr@2
   181
    return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
williamr@2
   182
  }    
williamr@2
   183
  template <class G, class EI, class T, class D>
williamr@2
   184
  typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
williamr@2
   185
  source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
williamr@2
   186
         const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2
   187
  {
williamr@2
   188
    const G& g = static_cast<const G&>(g_);
williamr@2
   189
    return g._first[e].first;
williamr@2
   190
  }
williamr@2
   191
  template <class G, class EI, class T, class D>
williamr@2
   192
  typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
williamr@2
   193
  target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor  e,
williamr@2
   194
         const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2
   195
  {
williamr@2
   196
    const G& g = static_cast<const G&>(g_);
williamr@2
   197
    return g._first[e].second;
williamr@2
   198
  }
williamr@2
   199
  template <class E>
williamr@2
   200
  class el_ra_edge_property_map
williamr@2
   201
    : public put_get_helper<E, el_ra_edge_property_map<E> >{
williamr@2
   202
  public:
williamr@2
   203
    typedef E key_type;
williamr@2
   204
    typedef E value_type;
williamr@2
   205
    typedef E reference;
williamr@2
   206
    typedef readable_property_map_tag category;
williamr@2
   207
williamr@2
   208
    value_type operator[](key_type e) const {
williamr@2
   209
      return e;
williamr@2
   210
    }
williamr@2
   211
  };
williamr@2
   212
  struct edge_list_ra_edge_property_selector {
williamr@2
   213
    template <class Graph, class Property, class Tag>
williamr@2
   214
    struct bind_ {
williamr@2
   215
      typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;
williamr@2
   216
      typedef type const_type;
williamr@2
   217
    };
williamr@2
   218
  };
williamr@2
   219
  template <>  
williamr@2
   220
  struct edge_property_selector<edge_list_ra_tag> {
williamr@2
   221
    typedef edge_list_ra_edge_property_selector type;
williamr@2
   222
  };
williamr@2
   223
  template <class G, class EI, class T, class D>
williamr@2
   224
  inline 
williamr@2
   225
  typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type
williamr@2
   226
  get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {
williamr@2
   227
    typedef typename property_map< edge_list_impl_ra<G,EI,T,D>, 
williamr@2
   228
      edge_index_t>::type EdgeIndexMap;
williamr@2
   229
    return EdgeIndexMap();
williamr@2
   230
  }
williamr@2
   231
williamr@2
   232
  template <class G, class EI, class T, class D>
williamr@2
   233
  inline D
williamr@2
   234
  get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&, 
williamr@2
   235
      typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {
williamr@2
   236
    return e;
williamr@2
   237
  }
williamr@2
   238
williamr@2
   239
williamr@2
   240
  // Some helper classes for determining if the iterators are random access
williamr@2
   241
  template <class Cat>
williamr@2
   242
  struct is_random {
williamr@2
   243
    enum { RET = false }; 
williamr@2
   244
    typedef false_type type; 
williamr@2
   245
  };
williamr@2
   246
  template <>
williamr@2
   247
  struct is_random<std::random_access_iterator_tag> { 
williamr@2
   248
    enum { RET = true }; typedef true_type type; 
williamr@2
   249
  };
williamr@2
   250
williamr@2
   251
  // The edge_list class conditionally inherits from one of the
williamr@2
   252
  // above two classes.
williamr@2
   253
williamr@2
   254
  template <class EdgeIter, 
williamr@2
   255
#if !defined BOOST_NO_STD_ITERATOR_TRAITS
williamr@2
   256
            class T = typename std::iterator_traits<EdgeIter>::value_type,
williamr@2
   257
            class D = typename std::iterator_traits<EdgeIter>::difference_type,
williamr@2
   258
            class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>
williamr@2
   259
#else
williamr@2
   260
            class T,
williamr@2
   261
            class D, 
williamr@2
   262
            class Cat>
williamr@2
   263
#endif
williamr@2
   264
  class edge_list
williamr@2
   265
    : public ct_if_t< typename is_random<Cat>::type,
williamr@2
   266
                    edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,
williamr@2
   267
                    edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D> 
williamr@2
   268
             >::type
williamr@2
   269
  {
williamr@2
   270
  public:
williamr@2
   271
    typedef directed_tag directed_category;
williamr@2
   272
    typedef allow_parallel_edge_tag edge_parallel_category;
williamr@2
   273
    typedef edge_list_graph_tag traversal_category;
williamr@2
   274
    typedef std::size_t edges_size_type;
williamr@2
   275
    typedef std::size_t vertices_size_type;
williamr@2
   276
    typedef std::size_t degree_size_type;
williamr@2
   277
    edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { 
williamr@2
   278
      m_num_edges = std::distance(first, last);
williamr@2
   279
    }
williamr@2
   280
    edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
williamr@2
   281
      : _first(first), _last(last), m_num_edges(E) { }  
williamr@2
   282
    
williamr@2
   283
    EdgeIter _first, _last;
williamr@2
   284
    edges_size_type m_num_edges;
williamr@2
   285
  };
williamr@2
   286
williamr@2
   287
  template <class EdgeIter, class T, class D, class Cat>
williamr@2
   288
  std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {
williamr@2
   289
    return el.m_num_edges;
williamr@2
   290
  }
williamr@2
   291
williamr@2
   292
#ifndef BOOST_NO_STD_ITERATOR_TRAITS
williamr@2
   293
  template <class EdgeIter>
williamr@2
   294
  inline edge_list<EdgeIter>
williamr@2
   295
  make_edge_list(EdgeIter first, EdgeIter last)
williamr@2
   296
  {
williamr@2
   297
    return edge_list<EdgeIter>(first, last);
williamr@2
   298
  }
williamr@2
   299
#endif
williamr@2
   300
  
williamr@2
   301
} /* namespace boost */
williamr@2
   302
williamr@2
   303
#endif /* BOOST_GRAPH_EDGE_LIST_HPP */