epoc32/include/stdapis/boost/graph/graph_traits.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 // 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 #ifndef BOOST_GRAPH_TRAITS_HPP
    11 #define BOOST_GRAPH_TRAITS_HPP
    12 
    13 #include <boost/config.hpp>
    14 #include <iterator>
    15 #include <boost/tuple/tuple.hpp>
    16 #include <boost/mpl/if.hpp>
    17 #include <boost/type_traits/is_same.hpp>
    18 #include <boost/iterator/iterator_categories.hpp>
    19 #include <boost/iterator/iterator_adaptor.hpp>
    20 #include <boost/detail/workaround.hpp>
    21 
    22 namespace boost {
    23 
    24   template <typename G>
    25   struct graph_traits {
    26     typedef typename G::vertex_descriptor      vertex_descriptor;
    27     typedef typename G::edge_descriptor        edge_descriptor;
    28     typedef typename G::adjacency_iterator     adjacency_iterator;
    29     typedef typename G::out_edge_iterator      out_edge_iterator;
    30     typedef typename G::in_edge_iterator       in_edge_iterator;
    31     typedef typename G::vertex_iterator        vertex_iterator;
    32     typedef typename G::edge_iterator          edge_iterator;
    33 
    34     typedef typename G::directed_category      directed_category;
    35     typedef typename G::edge_parallel_category edge_parallel_category;
    36     typedef typename G::traversal_category     traversal_category;
    37 
    38     typedef typename G::vertices_size_type     vertices_size_type;
    39     typedef typename G::edges_size_type        edges_size_type;
    40     typedef typename G::degree_size_type       degree_size_type;
    41 
    42     static inline vertex_descriptor null_vertex();
    43   };
    44 
    45   template <typename G>
    46   inline typename graph_traits<G>::vertex_descriptor
    47   graph_traits<G>::null_vertex()
    48   {
    49     return G::null_vertex();
    50   }
    51 
    52   // directed_category tags
    53   struct directed_tag { };
    54   struct undirected_tag { };
    55   struct bidirectional_tag : public directed_tag { };
    56 
    57   namespace detail {
    58     inline bool is_directed(directed_tag) { return true; }
    59     inline bool is_directed(undirected_tag) { return false; }
    60   }
    61 
    62   template <typename Graph>
    63   bool is_directed(const Graph&) { 
    64     typedef typename graph_traits<Graph>::directed_category Cat;
    65     return detail::is_directed(Cat());
    66   }
    67   template <typename Graph>
    68   bool is_undirected(const Graph& g) { 
    69     return ! is_directed(g);
    70   }
    71 
    72   // edge_parallel_category tags
    73   struct allow_parallel_edge_tag {};
    74   struct disallow_parallel_edge_tag {};
    75 
    76   namespace detail {
    77     inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
    78     inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
    79   }
    80 
    81   template <typename Graph>
    82   bool allows_parallel_edges(const Graph&) { 
    83     typedef typename graph_traits<Graph>::edge_parallel_category Cat;
    84     return detail::allows_parallel(Cat());
    85   }
    86 
    87   // traversal_category tags
    88   struct incidence_graph_tag { };
    89   struct adjacency_graph_tag { };
    90   struct bidirectional_graph_tag : 
    91     public virtual incidence_graph_tag { };
    92   struct vertex_list_graph_tag { };
    93   struct edge_list_graph_tag { };
    94   struct adjacency_matrix_tag { };
    95 
    96   //?? not the right place ?? Lee
    97   typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
    98 
    99   template <typename G>
   100   struct edge_property_type {
   101     typedef typename G::edge_property_type type;
   102   };
   103   template <typename G>
   104   struct vertex_property_type {
   105     typedef typename G::vertex_property_type type;
   106   };
   107   template <typename G>
   108   struct graph_property_type {
   109     typedef typename G::graph_property_type type;
   110   };
   111 
   112   struct no_vertex_bundle {};
   113   struct no_edge_bundle {};
   114 
   115   template<typename G>
   116   struct vertex_bundle_type
   117   {
   118     typedef typename G::vertex_bundled type;
   119   };
   120 
   121   template<typename G>
   122   struct edge_bundle_type
   123   {
   124     typedef typename G::edge_bundled type;
   125   };
   126 
   127   namespace graph { namespace detail {
   128     template<typename Graph, typename Descriptor>
   129     class bundled_result
   130     {
   131       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
   132       typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
   133                                  vertex_bundle_type<Graph>,
   134                                  edge_bundle_type<Graph> >::type bundler;
   135 
   136     public:
   137       typedef typename bundler::type type;
   138     };
   139   } } // end namespace graph::detail
   140 } // namespace boost
   141 
   142 // Since pair is in namespace std, Koenig lookup will find source and
   143 // target if they are also defined in namespace std.  This is illegal,
   144 // but the alternative is to put source and target in the global
   145 // namespace which causes name conflicts with other libraries (like
   146 // SUIF).
   147 namespace std {
   148 
   149   /* Some helper functions for dealing with pairs as edges */
   150   template <class T, class G>
   151   T source(pair<T,T> p, const G&) { return p.first; }
   152 
   153   template <class T, class G>
   154   T target(pair<T,T> p, const G&) { return p.second; }
   155 
   156 }
   157 
   158 #if defined(__GNUC__) && defined(__SGI_STL_PORT)
   159 // For some reason g++ with STLport does not see the above definition
   160 // of source() and target() unless we bring them into the boost
   161 // namespace.
   162 namespace boost {
   163   using std::source;
   164   using std::target;
   165 }
   166 #endif
   167 
   168 #endif // BOOST_GRAPH_TRAITS_HPP