|
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 |