Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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 <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