source: NonGTP/Boost/boost/graph/graph_traits.hpp @ 857

Revision 857, 5.3 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]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
22namespace 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).
147namespace 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.
162namespace boost {
163  using std::source;
164  using std::target;
165}
166#endif
167
168#endif // BOOST_GRAPH_TRAITS_HPP
Note: See TracBrowser for help on using the repository browser.