Mercurialtest / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
epoc32/include/stdapis/boost/graph/vector_as_graph.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed. 
     1 //=======================================================================

     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     3 // Copyright 2006 The Trustees of Indiana University.

     4 // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>

     5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor

     6 //

     7 // Distributed under the Boost Software License, Version 1.0. (See

     8 // accompanying file LICENSE_1_0.txt or copy at

     9 // http://www.boost.org/LICENSE_1_0.txt)

    10 //=======================================================================

    11 

    12 // The mutating functions (add_edge, etc.) were added by Vladimir Prus.

    13 

    14 #ifndef BOOST_VECTOR_AS_GRAPH_HPP

    15 #define BOOST_VECTOR_AS_GRAPH_HPP

    16 

    17 #include <cassert>

    18 #include <utility>

    19 #include <vector>

    20 #include <cstddef>

    21 #include <boost/iterator.hpp>

    22 #include <boost/graph/graph_traits.hpp>

    23 #include <boost/pending/integer_range.hpp>

    24 #include <boost/property_map.hpp>

    25 #include <boost/graph/properties.hpp>

    26 #include <algorithm>

    27 

    28 /*

    29   This module implements the VertexListGraph concept using a

    30   std::vector as the "back-bone" of the graph (the vector *is* the

    31   graph object). The edge-lists type of the graph is templated, so the

    32   user can choose any STL container, so long as the value_type of the

    33   container is convertible to the size_type of the vector. For now any

    34   graph properties must be stored seperately.

    35 

    36   This module requires the C++ compiler to support partial

    37   specialization for the graph_traits class, so this is not portable

    38   to VC++.

    39 

    40 */

    41 

    42 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    43 #error The vector-as-graph module requires a compiler that supports partial specialization

    44 #endif

    45 

    46 

    47 namespace boost {

    48   namespace detail {

    49     template <class EdgeList> struct val_out_edge_ret;

    50     template <class EdgeList> struct val_out_edge_iter;

    51     template <class EdgeList> struct val_edge;

    52   }

    53 }

    54 

    55 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    56 namespace boost {

    57 

    58   struct vector_as_graph_traversal_tag

    59     : public vertex_list_graph_tag,

    60       public adjacency_graph_tag,

    61       public incidence_graph_tag { };

    62 

    63   template <class EdgeList>

    64   struct graph_traits< std::vector<EdgeList> >

    65   {

    66     typedef typename EdgeList::value_type V;

    67     typedef V vertex_descriptor;

    68     typedef typename detail::val_edge<EdgeList>::type edge_descriptor;

    69     typedef typename EdgeList::const_iterator adjacency_iterator;

    70     typedef typename detail::val_out_edge_iter<EdgeList>::type

    71       out_edge_iterator;

    72     typedef void in_edge_iterator;

    73     typedef void edge_iterator;

    74     typedef typename integer_range<V>::iterator vertex_iterator;

    75     typedef directed_tag directed_category;

    76     typedef allow_parallel_edge_tag edge_parallel_category;

    77     typedef vector_as_graph_traversal_tag traversal_category;

    78     typedef typename std::vector<EdgeList>::size_type vertices_size_type;

    79     typedef void edges_size_type;

    80     typedef typename EdgeList::size_type degree_size_type;

    81   };

    82   template <class EdgeList>

    83   struct edge_property_type< std::vector<EdgeList> >

    84   {

    85     typedef void type;

    86   };

    87   template <class EdgeList>

    88   struct vertex_property_type< std::vector<EdgeList> >

    89   {

    90     typedef void type;

    91   };

    92   template <class EdgeList>

    93   struct graph_property_type< std::vector<EdgeList> >

    94   {

    95     typedef void type;

    96   };

    97 }

    98 #endif

    99 

   100 namespace boost {

   101 

   102   namespace detail {

   103 

   104     // "val" is short for Vector Adjacency List

   105 

   106     template <class EdgeList>

   107     struct val_edge

   108     {

   109       typedef typename EdgeList::value_type V;

   110       typedef std::pair<V,V> type;

   111     };

   112 

   113     // need rewrite this using boost::iterator_adaptor

   114     template <class V, class Iter>

   115     class val_out_edge_iterator

   116       : public boost::iterator<std::input_iterator_tag, std::pair<V,V>,

   117          std::ptrdiff_t, std::pair<V,V>*, const std::pair<V,V> >

   118     {

   119       typedef val_out_edge_iterator self;

   120       typedef std::pair<V,V> Edge;

   121     public:

   122       val_out_edge_iterator() { }

   123       val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { }

   124       Edge operator*() const { return Edge(_source, *_iter); }

   125       self& operator++() { ++_iter; return *this; }

   126       self operator++(int) { self t = *this; ++_iter; return t; }

   127       bool operator==(const self& x) const { return _iter == x._iter; }

   128       bool operator!=(const self& x) const { return _iter != x._iter; }

   129     protected:

   130       V _source;

   131       Iter _iter;

   132     };

   133 

   134     template <class EdgeList>

   135     struct val_out_edge_iter

   136     {

   137       typedef typename EdgeList::value_type V;

   138       typedef typename EdgeList::const_iterator Iter;

   139       typedef val_out_edge_iterator<V,Iter> type;

   140     };

   141 

   142     template <class EdgeList>

   143     struct val_out_edge_ret

   144     {

   145       typedef typename val_out_edge_iter<EdgeList>::type IncIter;

   146       typedef std::pair<IncIter,IncIter> type;

   147     };

   148 

   149   } // namesapce detail

   150 

   151   template <class EdgeList, class Alloc>

   152   typename detail::val_out_edge_ret<EdgeList>::type

   153   out_edges(typename EdgeList::value_type v,

   154             const std::vector<EdgeList, Alloc>& g)

   155   {

   156     typedef typename detail::val_out_edge_iter<EdgeList>::type Iter;

   157     typedef typename detail::val_out_edge_ret<EdgeList>::type return_type;

   158     return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end()));

   159   }

   160 

   161   template <class EdgeList, class Alloc>

   162   typename EdgeList::size_type

   163   out_degree(typename EdgeList::value_type v,

   164              const std::vector<EdgeList, Alloc>& g)

   165   {

   166     return g[v].size();

   167   }

   168 

   169   template <class EdgeList, class Alloc>

   170   std::pair<typename EdgeList::const_iterator,

   171             typename EdgeList::const_iterator>

   172   adjacent_vertices(typename EdgeList::value_type v,

   173                     const std::vector<EdgeList, Alloc>& g)

   174   {

   175     return std::make_pair(g[v].begin(), g[v].end());

   176   }

   177 

   178   // source() and target() already provided for pairs in graph_traits.hpp

   179 

   180   template <class EdgeList, class Alloc>

   181   std::pair<typename boost::integer_range<typename EdgeList::value_type>

   182               ::iterator,

   183             typename boost::integer_range<typename EdgeList::value_type>

   184               ::iterator >

   185   vertices(const std::vector<EdgeList, Alloc>& v)

   186   {

   187     typedef typename boost::integer_range<typename EdgeList::value_type>

   188       ::iterator Iter;

   189     return std::make_pair(Iter(0), Iter(v.size()));

   190   }

   191 

   192   template <class EdgeList, class Alloc>

   193   typename std::vector<EdgeList, Alloc>::size_type

   194   num_vertices(const std::vector<EdgeList, Alloc>& v)

   195   {

   196     return v.size();

   197   }

   198 

   199   template<class EdgeList, class Allocator>

   200   typename std::pair<typename detail::val_edge<EdgeList>::type, bool>

   201   add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,

   202            std::vector<EdgeList, Allocator>& g)

   203   {

   204     typedef typename detail::val_edge<EdgeList>::type edge_type;

   205     g[u].insert(g[u].end(), v);

   206     return std::make_pair(edge_type(u, v), true);

   207   }

   208 

   209   template<class EdgeList, class Allocator>

   210   typename std::pair<typename detail::val_edge<EdgeList>::type, bool>

   211   edge(typename EdgeList::value_type u, typename EdgeList::value_type v,

   212        std::vector<EdgeList, Allocator>& g)

   213   {

   214     typedef typename detail::val_edge<EdgeList>::type edge_type;

   215     typename EdgeList::iterator i = g[u].begin(), end = g[u].end();

   216     for (; i != end; ++i)

   217       if (*i == v)

   218         return std::make_pair(edge_type(u, v), true);

   219     return std::make_pair(edge_type(), false);

   220   }

   221 

   222   template<class EdgeList, class Allocator>

   223   void

   224   remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,

   225               std::vector<EdgeList, Allocator>& g)

   226   {

   227     typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);

   228     if (i != g[u].end())

   229       g[u].erase(i, g[u].end());

   230   }

   231 

   232   template<class EdgeList, class Allocator>

   233   void

   234   remove_edge(typename detail::val_edge<EdgeList>::type e,

   235               std::vector<EdgeList, Allocator>& g)

   236   {

   237     typename EdgeList::value_type u, v;

   238     u = e.first;

   239     v = e.second;

   240     // FIXME: edge type does not fully specify the edge to be deleted

   241     typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);

   242     if (i != g[u].end())

   243       g[u].erase(i, g[u].end());

   244   }

   245 

   246   template<class EdgeList, class Allocator, class Predicate>

   247   void

   248   remove_edge_if(Predicate p,

   249                  std::vector<EdgeList, Allocator>& g)

   250   {

   251       for (std::size_t u = 0; u < g.size(); ++u) {

   252           // Oops! gcc gets internal compiler error on compose_.......

   253 

   254           typedef typename EdgeList::iterator iterator;

   255           iterator b = g[u].begin(), e = g[u].end();

   256 

   257           if (!g[u].empty()) {

   258 

   259               for(; b != e;) {

   260                   if (p(std::make_pair(u, *b))) {

   261                       --e;

   262                       if (b == e)

   263                           break;

   264                       else

   265                           iter_swap(b, e);

   266                   } else {

   267                       ++b;

   268                   }

   269               }

   270           }

   271 

   272           if (e != g[u].end())

   273               g[u].erase(e, g[u].end());

   274       }

   275   }

   276 

   277   template<class EdgeList, class Allocator>

   278   typename EdgeList::value_type

   279   add_vertex(std::vector<EdgeList, Allocator>& g)

   280   {

   281     g.resize(g.size()+1);

   282     return g.size()-1;

   283   }

   284 

   285   template<class EdgeList, class Allocator>

   286   void

   287   clear_vertex(typename EdgeList::value_type u,

   288                std::vector<EdgeList, Allocator>& g)

   289   {

   290     g[u].clear();

   291     for (std::size_t i = 0; i < g.size(); ++i)

   292       remove_edge(i, u, g);

   293   }

   294 

   295   template<class EdgeList, class Allocator>

   296   void

   297   remove_vertex(typename EdgeList::value_type u,

   298                 std::vector<EdgeList, Allocator>& g)

   299   {

   300     typedef typename EdgeList::iterator iterator;

   301     clear_vertex(u, g);

   302     g.erase(g.begin() + u);

   303     for (std::size_t i = 0; i < g.size(); ++i)

   304       for ( iterator it = g[i].begin(); it != g[i].end(); ++it )

   305         // after clear_vertex *it is never equal to u

   306         if ( *it > u )

   307           --*it;

   308   }

   309 

   310   template<typename EdgeList, typename Allocator>

   311   struct property_map<std::vector<EdgeList, Allocator>, vertex_index_t>

   312   {

   313     typedef identity_property_map type;

   314     typedef type const_type;

   315   };

   316 

   317   template<typename EdgeList, typename Allocator>

   318   identity_property_map 

   319   get(vertex_index_t, const std::vector<EdgeList, Allocator>&)

   320   {

   321     return identity_property_map();

   322   }

   323 

   324   template<typename EdgeList, typename Allocator>

   325   identity_property_map 

   326   get(vertex_index_t, std::vector<EdgeList, Allocator>&)

   327   {

   328     return identity_property_map();

   329   }

   330 } // namespace boost

   331 

   332 #endif // BOOST_VECTOR_AS_GRAPH_HPP
test