1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #ifndef BOOST_GRAPH_ARCHETYPES_HPP
11 #define BOOST_GRAPH_ARCHETYPES_HPP
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/concept_archetype.hpp>
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/graph/properties.hpp>
18 namespace boost { // should use a different namespace for this
21 struct null_graph_archetype : public null_archetype<> {
22 struct traversal_category { };
26 //===========================================================================
27 template <typename Vertex, typename Directed, typename ParallelCategory,
28 typename Base = detail::null_graph_archetype >
29 struct incidence_graph_archetype : public Base
31 typedef typename Base::traversal_category base_trav_cat;
32 struct traversal_category
33 : public incidence_graph_tag, public base_trav_cat { };
35 typedef immutable_graph_tag mutability_category;
37 typedef Vertex vertex_descriptor;
38 typedef unsigned int degree_size_type;
39 typedef unsigned int vertices_size_type;
40 typedef unsigned int edges_size_type;
41 struct edge_descriptor {
43 edge_descriptor(const detail::dummy_constructor&) { }
44 bool operator==(const edge_descriptor&) const { return false; }
45 bool operator!=(const edge_descriptor&) const { return false; }
47 typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
49 typedef Directed directed_category;
50 typedef ParallelCategory edge_parallel_category;
52 typedef void adjacency_iterator;
53 typedef void in_edge_iterator;
54 typedef void vertex_iterator;
55 typedef void edge_iterator;
57 static vertex_descriptor null_vertex() {return vertex_descriptor();}
59 template <typename V, typename D, typename P, typename B>
60 V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
61 const incidence_graph_archetype<V,D,P,B>& )
63 return V(static_object<detail::dummy_constructor>::get());
65 template <typename V, typename D, typename P, typename B>
66 V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
67 const incidence_graph_archetype<V,D,P,B>& )
69 return V(static_object<detail::dummy_constructor>::get());
72 template <typename V, typename D, typename P, typename B>
73 std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
74 typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
75 out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
77 typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
78 return std::make_pair(Iter(), Iter());
81 template <typename V, typename D, typename P, typename B>
82 typename incidence_graph_archetype<V,D,P,B>::degree_size_type
83 out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
88 //===========================================================================
89 template <typename Vertex, typename Directed, typename ParallelCategory,
90 typename Base = detail::null_graph_archetype >
91 struct adjacency_graph_archetype : public Base
93 typedef typename Base::traversal_category base_trav_cat;
94 struct traversal_category
95 : public adjacency_graph_tag, public base_trav_cat { };
96 typedef Vertex vertex_descriptor;
97 typedef unsigned int degree_size_type;
98 typedef unsigned int vertices_size_type;
99 typedef unsigned int edges_size_type;
100 typedef void edge_descriptor;
101 typedef input_iterator_archetype<Vertex> adjacency_iterator;
103 typedef Directed directed_category;
104 typedef ParallelCategory edge_parallel_category;
106 typedef void in_edge_iterator;
107 typedef void out_edge_iterator;
108 typedef void vertex_iterator;
109 typedef void edge_iterator;
111 static vertex_descriptor null_vertex() {return vertex_descriptor();}
114 template <typename V, typename D, typename P, typename B>
115 std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
116 typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
117 adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
119 typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
120 return std::make_pair(Iter(), Iter());
123 template <typename V, typename D, typename P, typename B>
124 typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
125 out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
130 //===========================================================================
131 template <typename Vertex, typename Directed, typename ParallelCategory,
132 typename Base = detail::null_graph_archetype >
133 struct vertex_list_graph_archetype : public Base
135 typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
137 typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
140 typedef typename Base::traversal_category base_trav_cat;
141 struct traversal_category
142 : public vertex_list_graph_tag, public base_trav_cat { };
144 typedef immutable_graph_tag mutability_category;
146 typedef Vertex vertex_descriptor;
147 typedef unsigned int degree_size_type;
148 typedef typename Incidence::edge_descriptor edge_descriptor;
149 typedef typename Incidence::out_edge_iterator out_edge_iterator;
150 typedef typename Adjacency::adjacency_iterator adjacency_iterator;
152 typedef input_iterator_archetype<Vertex> vertex_iterator;
153 typedef unsigned int vertices_size_type;
154 typedef unsigned int edges_size_type;
156 typedef Directed directed_category;
157 typedef ParallelCategory edge_parallel_category;
159 typedef void in_edge_iterator;
160 typedef void edge_iterator;
162 static vertex_descriptor null_vertex() {return vertex_descriptor();}
165 template <typename V, typename D, typename P, typename B>
166 std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
167 typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
168 vertices(const vertex_list_graph_archetype<V,D,P,B>& )
170 typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
171 return std::make_pair(Iter(), Iter());
174 template <typename V, typename D, typename P, typename B>
175 typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
176 num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
181 // ambiguously inherited from incidence graph and adjacency graph
182 template <typename V, typename D, typename P, typename B>
183 typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
184 out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
189 //===========================================================================
191 struct property_graph_archetype_tag { };
193 template <typename GraphArchetype, typename Property, typename ValueArch>
194 struct property_graph_archetype : public GraphArchetype
196 typedef property_graph_archetype_tag graph_tag;
197 typedef ValueArch vertex_property_type;
198 typedef ValueArch edge_property_type;
201 struct choose_edge_property_map_archetype {
202 template <typename Graph, typename Property, typename Tag>
204 typedef mutable_lvalue_property_map_archetype
205 <typename Graph::edge_descriptor, Property> type;
206 typedef lvalue_property_map_archetype
207 <typename Graph::edge_descriptor, Property> const_type;
211 struct edge_property_selector<property_graph_archetype_tag> {
212 typedef choose_edge_property_map_archetype type;
215 struct choose_vertex_property_map_archetype {
216 template <typename Graph, typename Property, typename Tag>
218 typedef mutable_lvalue_property_map_archetype
219 <typename Graph::vertex_descriptor, Property> type;
220 typedef lvalue_property_map_archetype
221 <typename Graph::vertex_descriptor, Property> const_type;
226 struct vertex_property_selector<property_graph_archetype_tag> {
227 typedef choose_vertex_property_map_archetype type;
230 template <typename G, typename P, typename V>
231 typename property_map<property_graph_archetype<G, P, V>, P>::type
232 get(P, property_graph_archetype<G, P, V>&) {
233 typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
237 template <typename G, typename P, typename V>
238 typename property_map<property_graph_archetype<G, P, V>, P>::const_type
239 get(P, const property_graph_archetype<G, P, V>&) {
240 typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
244 template <typename G, typename P, typename K, typename V>
245 typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
246 get(P p, const property_graph_archetype<G, P, V>& g, K k) {
247 return get( get(p, g), k);
250 template <typename G, typename P, typename V, typename Key>
252 put(P p, property_graph_archetype<G, P, V>& g,
253 const Key& key, const V& value)
255 typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
256 Map pmap = get(p, g);
257 put(pmap, key, value);
260 struct color_value_archetype {
261 color_value_archetype() { }
262 color_value_archetype(detail::dummy_constructor) { }
263 bool operator==(const color_value_archetype& ) const { return true; }
264 bool operator!=(const color_value_archetype& ) const { return true; }
267 struct color_traits<color_value_archetype> {
268 static color_value_archetype white()
270 return color_value_archetype
271 (static_object<detail::dummy_constructor>::get());
273 static color_value_archetype gray()
275 return color_value_archetype
276 (static_object<detail::dummy_constructor>::get());
278 static color_value_archetype black()
280 return color_value_archetype
281 (static_object<detail::dummy_constructor>::get());
285 template <typename T>
286 class buffer_archetype {
288 void push(const T&) {}
290 T& top() { return static_object<T>::get(); }
291 const T& top() const { return static_object<T>::get(); }
292 bool empty() const { return true; }
298 #endif // BOOST_GRAPH_ARCHETYPES_HPP