1 //=======================================================================
2 // Copyright 2002 Indiana University.
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_ARCHETYPES_HPP
11 #define BOOST_GRAPH_ARCHETYPES_HPP
12 
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>
17 
18 namespace boost { // should use a different namespace for this
19 
20   namespace detail {
21     struct null_graph_archetype : public null_archetype<> {
22       struct traversal_category { };
23     };
24   }
25 
26   //===========================================================================
27   template <typename Vertex, typename Directed, typename ParallelCategory,
28     typename Base = detail::null_graph_archetype >
29   struct incidence_graph_archetype : public Base
30   {
31     typedef typename Base::traversal_category base_trav_cat;
32     struct traversal_category
33       : public incidence_graph_tag, public base_trav_cat { };
34 #if 0
35     typedef immutable_graph_tag mutability_category;
36 #endif
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 {
edge_descriptorboost::incidence_graph_archetype::edge_descriptor42       edge_descriptor() { }
edge_descriptorboost::incidence_graph_archetype::edge_descriptor43       edge_descriptor(const detail::dummy_constructor&) { }
operator ==boost::incidence_graph_archetype::edge_descriptor44       bool operator==(const edge_descriptor&) const { return false; }
operator !=boost::incidence_graph_archetype::edge_descriptor45       bool operator!=(const edge_descriptor&) const { return false; }
46     };
47     typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
48 
49     typedef Directed directed_category;
50     typedef ParallelCategory edge_parallel_category;
51 
52     typedef void adjacency_iterator;
53     typedef void in_edge_iterator;
54     typedef void vertex_iterator;
55     typedef void edge_iterator;
56 
null_vertexboost::incidence_graph_archetype57     static vertex_descriptor null_vertex() {return vertex_descriptor();}
58   };
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>& )
62   {
63     return V(static_object<detail::dummy_constructor>::get());
64   }
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>& )
68   {
69     return V(static_object<detail::dummy_constructor>::get());
70   }
71 
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>
out_edges(const V &,const incidence_graph_archetype<V,D,P,B> &)75   out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
76   {
77     typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
78     return std::make_pair(Iter(), Iter());
79   }
80 
81   template <typename V, typename D, typename P, typename B>
82   typename incidence_graph_archetype<V,D,P,B>::degree_size_type
out_degree(const V &,const incidence_graph_archetype<V,D,P,B> &)83   out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
84   {
85     return 0;
86   }
87 
88   //===========================================================================
89   template <typename Vertex, typename Directed, typename ParallelCategory,
90     typename Base = detail::null_graph_archetype >
91   struct adjacency_graph_archetype : public Base
92   {
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;
102 
103     typedef Directed directed_category;
104     typedef ParallelCategory edge_parallel_category;
105 
106     typedef void in_edge_iterator;
107     typedef void out_edge_iterator;
108     typedef void vertex_iterator;
109     typedef void edge_iterator;
110 
null_vertexboost::adjacency_graph_archetype111     static vertex_descriptor null_vertex() {return vertex_descriptor();}
112   };
113 
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>
adjacent_vertices(const V &,const adjacency_graph_archetype<V,D,P,B> &)117   adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
118   {
119     typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
120     return std::make_pair(Iter(), Iter());
121   }
122 
123   template <typename V, typename D, typename P, typename B>
124   typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
out_degree(const V &,const adjacency_graph_archetype<V,D,P,B> &)125   out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
126   {
127     return 0;
128   }
129 
130   //===========================================================================
131   template <typename Vertex, typename Directed, typename ParallelCategory,
132     typename Base = detail::null_graph_archetype >
133   struct vertex_list_graph_archetype : public Base
134   {
135     typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
136       Incidence;
137     typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
138       Adjacency;
139 
140     typedef typename Base::traversal_category base_trav_cat;
141     struct traversal_category
142       : public vertex_list_graph_tag, public base_trav_cat { };
143 #if 0
144     typedef immutable_graph_tag mutability_category;
145 #endif
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;
151 
152     typedef input_iterator_archetype<Vertex> vertex_iterator;
153     typedef unsigned int vertices_size_type;
154     typedef unsigned int edges_size_type;
155 
156     typedef Directed directed_category;
157     typedef ParallelCategory edge_parallel_category;
158 
159     typedef void in_edge_iterator;
160     typedef void edge_iterator;
161 
null_vertexboost::vertex_list_graph_archetype162     static vertex_descriptor null_vertex() {return vertex_descriptor();}
163   };
164 
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>
vertices(const vertex_list_graph_archetype<V,D,P,B> &)168   vertices(const vertex_list_graph_archetype<V,D,P,B>& )
169   {
170     typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
171     return std::make_pair(Iter(), Iter());
172   }
173 
174   template <typename V, typename D, typename P, typename B>
175   typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
num_vertices(const vertex_list_graph_archetype<V,D,P,B> &)176   num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
177   {
178     return 0;
179   }
180 
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
out_degree(const V &,const vertex_list_graph_archetype<V,D,P,B> &)184   out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
185   {
186     return 0;
187   }
188 
189   //===========================================================================
190 
191   struct property_graph_archetype_tag { };
192 
193   template <typename GraphArchetype, typename Property, typename ValueArch>
194   struct property_graph_archetype : public GraphArchetype
195   {
196     typedef property_graph_archetype_tag graph_tag;
197     typedef ValueArch vertex_property_type;
198     typedef ValueArch edge_property_type;
199   };
200 
201   struct choose_edge_property_map_archetype {
202     template <typename Graph, typename Property, typename Tag>
203     struct bind_ {
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;
208     };
209   };
210   template <>
211   struct edge_property_selector<property_graph_archetype_tag> {
212     typedef choose_edge_property_map_archetype type;
213   };
214 
215   struct choose_vertex_property_map_archetype {
216     template <typename Graph, typename Property, typename Tag>
217     struct bind_ {
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;
222     };
223   };
224 
225   template <>
226   struct vertex_property_selector<property_graph_archetype_tag> {
227     typedef choose_vertex_property_map_archetype type;
228   };
229 
230   template <typename G, typename P, typename V>
231   typename property_map<property_graph_archetype<G, P, V>, P>::type
get(P,property_graph_archetype<G,P,V> &)232   get(P, property_graph_archetype<G, P, V>&) {
233     typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
234     return pmap;
235   }
236 
237   template <typename G, typename P, typename V>
238   typename property_map<property_graph_archetype<G, P, V>, P>::const_type
get(P,const property_graph_archetype<G,P,V> &)239   get(P, const property_graph_archetype<G, P, V>&) {
240     typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
241     return pmap;
242   }
243 
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
get(P p,const property_graph_archetype<G,P,V> & g,K k)246   get(P p, const property_graph_archetype<G, P, V>& g, K k) {
247     return get( get(p, g), k);
248   }
249 
250   template <typename G, typename P, typename V, typename Key>
251   void
put(P p,property_graph_archetype<G,P,V> & g,const Key & key,const V & value)252   put(P p, property_graph_archetype<G, P, V>& g,
253       const Key& key, const V& value)
254   {
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);
258   }
259 
260   struct color_value_archetype {
color_value_archetypeboost::color_value_archetype261     color_value_archetype() { }
color_value_archetypeboost::color_value_archetype262     color_value_archetype(detail::dummy_constructor) { }
operator ==boost::color_value_archetype263     bool operator==(const color_value_archetype& ) const { return true; }
operator !=boost::color_value_archetype264     bool operator!=(const color_value_archetype& ) const { return true; }
265   };
266   template <>
267   struct color_traits<color_value_archetype> {
whiteboost::color_traits268     static color_value_archetype white()
269     {
270       return color_value_archetype
271         (static_object<detail::dummy_constructor>::get());
272     }
grayboost::color_traits273     static color_value_archetype gray()
274     {
275       return color_value_archetype
276         (static_object<detail::dummy_constructor>::get());
277     }
blackboost::color_traits278     static color_value_archetype black()
279     {
280       return color_value_archetype
281         (static_object<detail::dummy_constructor>::get());
282     }
283   };
284 
285   template <typename T>
286   class buffer_archetype {
287   public:
push(const T &)288     void push(const T&) {}
pop()289     void pop() {}
top()290     T& top() { return static_object<T>::get(); }
top() const291     const T& top() const { return static_object<T>::get(); }
empty() const292     bool empty() const { return true; }
293   };
294 
295 } // namespace boost
296 
297 
298 #endif // BOOST_GRAPH_ARCHETYPES_HPP
299