inference-engine/thirdparty/clDNN/common/boost/1.64.0/include/boost-1_64/boost/graph/graph_traits.hpp

   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 <utility> /* Primarily for std::pair */
  16 #include <boost/tuple/tuple.hpp>
  17 #include <boost/mpl/if.hpp>
  18 #include <boost/mpl/eval_if.hpp>
  19 #include <boost/mpl/bool.hpp>
  20 #include <boost/mpl/not.hpp>
  21 #include <boost/mpl/has_xxx.hpp>
  22 #include <boost/mpl/void.hpp>
  23 #include <boost/mpl/identity.hpp>
  24 #include <boost/type_traits/is_same.hpp>
  25 #include <boost/iterator/iterator_categories.hpp>
  26 #include <boost/iterator/iterator_adaptor.hpp>
  27 #include <boost/pending/property.hpp>
  28 #include <boost/detail/workaround.hpp>
  29
  30 namespace boost {
  31
  32     namespace detail {
  33 #define BOOST_GRAPH_MEMBER_OR_VOID(name) \
  34       BOOST_MPL_HAS_XXX_TRAIT_DEF(name) \
  35       template <typename T> struct BOOST_JOIN(get_member_, name) {typedef typename T::name type;}; \
  36       template <typename T> struct BOOST_JOIN(get_opt_member_, name): \
  37         boost::mpl::eval_if_c< \
  38           BOOST_JOIN(has_, name)<T>::value, \
  39           BOOST_JOIN(get_member_, name)<T>, \
  40           boost::mpl::identity<void> > \
  41         {};
  42       BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)
  43       BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)
  44       BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)
  45       BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)
  46       BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)
  47       BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)
  48       BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)
  49       BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)
  50     }
  51
  52     template <typename G>
  53     struct graph_traits {
  54 #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
  55         typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name;
  56
  57         typedef typename G::vertex_descriptor      vertex_descriptor;
  58         typedef typename G::edge_descriptor        edge_descriptor;
  59         BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)
  60         BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)
  61         BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)
  62         BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)
  63         BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)
  64
  65         typedef typename G::directed_category      directed_category;
  66         typedef typename G::edge_parallel_category edge_parallel_category;
  67         typedef typename G::traversal_category     traversal_category;
  68
  69         BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)
  70         BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)
  71         BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)
  72 #undef BOOST_GRAPH_PULL_OPT_MEMBER
  73
  74         static inline vertex_descriptor null_vertex();
  75     };
  76
  77     template <typename G>
  78     inline typename graph_traits<G>::vertex_descriptor
  79     graph_traits<G>::null_vertex()
  80     { return G::null_vertex(); }
  81
  82     // directed_category tags
  83     struct directed_tag { };
  84     struct undirected_tag { };
  85     struct bidirectional_tag : public directed_tag { };
  86
  87     namespace detail {
  88         inline bool is_directed(directed_tag) { return true; }
  89         inline bool is_directed(undirected_tag) { return false; }
  90     }
  91
  92     /** Return true if the given graph is directed. */
  93     template <typename Graph>
  94     bool is_directed(const Graph&) {
  95         typedef typename graph_traits<Graph>::directed_category Cat;
  96         return detail::is_directed(Cat());
  97     }
  98
  99     /** Return true if the given graph is undirected. */
 100     template <typename Graph>
 101     bool is_undirected(const Graph& g) {
 102         return !is_directed(g);
 103     }
 104
 105     /** @name Directed/Undirected Graph Traits */
 106     //@{
 107     namespace graph_detail {
 108         template <typename Tag>
 109         struct is_directed_tag
 110             : mpl::bool_<is_convertible<Tag, directed_tag>::value>
 111         { };
 112     } // namespace graph_detail
 113
 114     template <typename Graph>
 115     struct is_directed_graph
 116         : graph_detail::is_directed_tag<
 117             typename graph_traits<Graph>::directed_category
 118         >
 119     { };
 120
 121     template <typename Graph>
 122     struct is_undirected_graph
 123         : mpl::not_< is_directed_graph<Graph> >
 124     { };
 125     //@}
 126
 127     // edge_parallel_category tags
 128     struct allow_parallel_edge_tag { };
 129     struct disallow_parallel_edge_tag { };
 130
 131     namespace detail {
 132         inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
 133         inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
 134     }
 135
 136     template <typename Graph>
 137     bool allows_parallel_edges(const Graph&) {
 138         typedef typename graph_traits<Graph>::edge_parallel_category Cat;
 139         return detail::allows_parallel(Cat());
 140     }
 141
 142     /** @name Parallel Edges Traits */
 143     //@{
 144     /**
 145      * The is_multigraph metafunction returns true if the graph allows
 146      * parallel edges. Technically, a multigraph is a simple graph that
 147      * allows parallel edges, but since there are no traits for the allowance
 148      * or disallowance of loops, this is a moot point.
 149      */
 150     template <typename Graph>
 151     struct is_multigraph
 152         : mpl::bool_<
 153             is_same<
 154                 typename graph_traits<Graph>::edge_parallel_category,
 155                 allow_parallel_edge_tag
 156             >::value
 157         >
 158     { };
 159     //@}
 160
 161     // traversal_category tags
 162     struct incidence_graph_tag { };
 163     struct adjacency_graph_tag { };
 164     struct bidirectional_graph_tag : virtual incidence_graph_tag { };
 165     struct vertex_list_graph_tag { };
 166     struct edge_list_graph_tag { };
 167     struct adjacency_matrix_tag { };
 168
 169     // Parallel traversal_category tags
 170     struct distributed_graph_tag { };
 171     struct distributed_vertex_list_graph_tag { };
 172     struct distributed_edge_list_graph_tag { };
 173 #define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these from external versions of PBGL
 174
 175     /** @name Traversal Category Traits
 176      * These traits classify graph types by their supported methods of
 177      * vertex and edge traversal.
 178      */
 179     //@{
 180     template <typename Graph>
 181     struct is_incidence_graph
 182         : mpl::bool_<
 183             is_convertible<
 184                 typename graph_traits<Graph>::traversal_category,
 185                 incidence_graph_tag
 186             >::value
 187         >
 188     { };
 189
 190     template <typename Graph>
 191     struct is_bidirectional_graph
 192         : mpl::bool_<
 193             is_convertible<
 194                 typename graph_traits<Graph>::traversal_category,
 195                 bidirectional_graph_tag
 196             >::value
 197         >
 198     { };
 199
 200     template <typename Graph>
 201     struct is_vertex_list_graph
 202         : mpl::bool_<
 203             is_convertible<
 204                 typename graph_traits<Graph>::traversal_category,
 205                 vertex_list_graph_tag
 206             >::value
 207         >
 208     { };
 209
 210     template <typename Graph>
 211     struct is_edge_list_graph
 212         : mpl::bool_<
 213             is_convertible<
 214                 typename graph_traits<Graph>::traversal_category,
 215                 edge_list_graph_tag
 216             >::value
 217         >
 218     { };
 219
 220     template <typename Graph>
 221     struct is_adjacency_matrix
 222         : mpl::bool_<
 223             is_convertible<
 224                 typename graph_traits<Graph>::traversal_category,
 225                 adjacency_matrix_tag
 226             >::value
 227         >
 228     { };
 229     //@}
 230
 231     /** @name Directed Graph Traits
 232      * These metafunctions are used to fully classify directed vs. undirected
 233      * graphs. Recall that an undirected graph is also bidirectional, but it
 234      * cannot be both undirected and directed at the same time.
 235      */
 236     //@{
 237     template <typename Graph>
 238     struct is_directed_unidirectional_graph
 239         : mpl::and_<
 240             is_directed_graph<Graph>, mpl::not_< is_bidirectional_graph<Graph> >
 241         >
 242     { };
 243
 244     template <typename Graph>
 245     struct is_directed_bidirectional_graph
 246         : mpl::and_<
 247             is_directed_graph<Graph>, is_bidirectional_graph<Graph>
 248         >
 249     { };
 250     //@}
 251
 252     //?? not the right place ?? Lee
 253     typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
 254
 255     namespace detail {
 256       BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type)
 257       BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type)
 258       BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type)
 259
 260       template <typename G> struct get_graph_property_type {typedef typename G::graph_property_type type;};
 261       template <typename G> struct get_edge_property_type {typedef typename G::edge_property_type type;};
 262       template <typename G> struct get_vertex_property_type {typedef typename G::vertex_property_type type;};
 263     }
 264
 265     template <typename G>
 266     struct graph_property_type
 267       : boost::mpl::eval_if<detail::has_graph_property_type<G>,
 268                             detail::get_graph_property_type<G>,
 269                             no_property> {};
 270     template <typename G>
 271     struct edge_property_type
 272       : boost::mpl::eval_if<detail::has_edge_property_type<G>,
 273                             detail::get_edge_property_type<G>,
 274                             no_property> {};
 275     template <typename G>
 276     struct vertex_property_type
 277       : boost::mpl::eval_if<detail::has_vertex_property_type<G>,
 278                             detail::get_vertex_property_type<G>,
 279                             no_property> {};
 280
 281     template<typename G>
 282     struct graph_bundle_type {
 283       typedef typename G::graph_bundled type;
 284     };
 285
 286     template<typename G>
 287     struct vertex_bundle_type {
 288       typedef typename G::vertex_bundled type;
 289     };
 290
 291     template<typename G>
 292     struct edge_bundle_type {
 293       typedef typename G::edge_bundled type;
 294     };
 295
 296     namespace graph { namespace detail {
 297         template<typename Graph, typename Descriptor>
 298         class bundled_result {
 299             typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 300             typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
 301                                         vertex_bundle_type<Graph>,
 302                                         edge_bundle_type<Graph> >::type bundler;
 303         public:
 304             typedef typename bundler::type type;
 305         };
 306
 307         template<typename Graph>
 308         class bundled_result<Graph, graph_bundle_t> {
 309             typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 310             typedef graph_bundle_type<Graph> bundler;
 311         public:
 312             typedef typename bundler::type type;
 313         };
 314
 315     } } // namespace graph::detail
 316
 317     namespace graph_detail {
 318       // A helper metafunction for determining whether or not a type is
 319       // bundled.
 320       template <typename T>
 321       struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value>
 322       { };
 323     } // namespace graph_detail
 324
 325     /** @name Graph Property Traits
 326      * These metafunctions (along with those above), can be used to access the
 327      * vertex and edge properties (bundled or otherwise) of vertices and
 328      * edges.
 329      */
 330     //@{
 331     template<typename Graph>
 332     struct has_graph_property
 333       : mpl::not_<
 334         typename detail::is_no_property<
 335           typename graph_property_type<Graph>::type
 336         >::type
 337       >::type
 338     { };
 339
 340     template<typename Graph>
 341     struct has_bundled_graph_property
 342       : mpl::not_<
 343         graph_detail::is_no_bundle<typename graph_bundle_type<Graph>::type>
 344       >
 345     { };
 346
 347     template <typename Graph>
 348     struct has_vertex_property
 349         : mpl::not_<
 350             typename detail::is_no_property<typename vertex_property_type<Graph>::type>
 351         >::type
 352     { };
 353
 354     template <typename Graph>
 355     struct has_bundled_vertex_property
 356         : mpl::not_<
 357             graph_detail::is_no_bundle<typename vertex_bundle_type<Graph>::type>
 358         >
 359     { };
 360
 361     template <typename Graph>
 362     struct has_edge_property
 363         : mpl::not_<
 364             typename detail::is_no_property<typename edge_property_type<Graph>::type>
 365         >::type
 366     { };
 367
 368     template <typename Graph>
 369     struct has_bundled_edge_property
 370         : mpl::not_<
 371             graph_detail::is_no_bundle<typename edge_bundle_type<Graph>::type>
 372         >
 373     { };
 374     //@}
 375
 376 } // namespace boost
 377
 378 // Since pair is in namespace std, Koenig lookup will find source and
 379 // target if they are also defined in namespace std.  This is illegal,
 380 // but the alternative is to put source and target in the global
 381 // namespace which causes name conflicts with other libraries (like
 382 // SUIF).
 383 namespace std {
 384
 385   /* Some helper functions for dealing with pairs as edges */
 386   template <class T, class G>
 387   T source(pair<T,T> p, const G&) { return p.first; }
 388
 389   template <class T, class G>
 390   T target(pair<T,T> p, const G&) { return p.second; }
 391
 392 }
 393
 394 #if defined(__GNUC__) && defined(__SGI_STL_PORT)
 395 // For some reason g++ with STLport does not see the above definition
 396 // of source() and target() unless we bring them into the boost
 397 // namespace.
 398 namespace boost {
 399   using std::source;
 400   using std::target;
 401 }
 402 #endif
 403
 404 #endif // BOOST_GRAPH_TRAITS_HPP