1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
2 
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 
7 //  Authors: Douglas Gregor
8 //           Andrew Lumsdaine
9 
10 //
11 // Distributed graph concepts and helpers
12 //
13 
14 #ifndef BOOST_GRAPH_DISTRIBUTED_CONCEPTS_HPP
15 #define BOOST_GRAPH_DISTRIBUTED_CONCEPTS_HPP
16 
17 #ifndef BOOST_GRAPH_USE_MPI
18 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
19 #endif
20 
21 #include <boost/version.hpp>
22 #include <boost/graph/graph_traits.hpp>
23 #include <boost/graph/graph_concepts.hpp>
24 #include <boost/concept/assert.hpp>
25 
26 #if BOOST_VERSION >= 103500
27 #  include <boost/concept/detail/concept_def.hpp>
28 #endif
29 
30 namespace boost {
31 
32 #if BOOST_VERSION >= 103500
33   namespace concepts {
34 #endif
35 
36 #if BOOST_VERSION < 103500
37 
38 template <class G>
39 struct DistributedVertexListGraphConcept
40 {
41   typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
42   typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
43   typedef typename graph_traits<G>::traversal_category
44     traversal_category;
constraintsboost::concepts::DistributedVertexListGraphConcept45   void constraints() {
46     BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
47     BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<vertex_iterator> ));
48     BOOST_CONCEPT_ASSERT(( ConvertibleConcept<traversal_category,
49       distributed_vertex_list_graph_tag> ));
50 
51 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
52     // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
53     // you want to use vector_as_graph, it is!  I'm sure the graph
54     // library leaves these out all over the place.  Probably a
55     // redesign involving specializing a template with a static
56     // member function is in order :(
57     using boost::vertices;
58 #endif
59     p = vertices(g);
60     v = *p.first;
61     const_constraints(g);
62   }
const_constraintsboost::concepts::DistributedVertexListGraphConcept63   void const_constraints(const G& cg) {
64 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
65     // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
66     // you want to use vector_as_graph, it is!  I'm sure the graph
67     // library leaves these out all over the place.  Probably a
68     // redesign involving specializing a template with a static
69     // member function is in order :(
70     using boost::vertices;
71 #endif
72 
73     p = vertices(cg);
74     v = *p.first;
75     V = num_vertices(cg);
76   }
77   std::pair<vertex_iterator,vertex_iterator> p;
78   typename graph_traits<G>::vertex_descriptor v;
79   G g;
80   vertices_size_type V;
81 };
82 
83 template <class G>
84 struct DistributedEdgeListGraphConcept
85 {
86   typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
87   typedef typename graph_traits<G>::edge_iterator edge_iterator;
88   typedef typename graph_traits<G>::edges_size_type edges_size_type;
89   typedef typename graph_traits<G>::traversal_category
90     traversal_category;
constraintsboost::concepts::DistributedEdgeListGraphConcept91   void constraints() {
92     BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
93     BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<edge_iterator> ));
94     BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<edge_descriptor> ));
95     BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<edge_descriptor> ));
96     BOOST_CONCEPT_ASSERT(( AssignableConcept<edge_descriptor> ));
97     BOOST_CONCEPT_ASSERT(( ConvertibleConcept<traversal_category,
98       distributed_edge_list_graph_tag> ));
99 
100     p = edges(g);
101     e = *p.first;
102     u = source(e, g);
103     v = target(e, g);
104     const_constraints(g);
105   }
const_constraintsboost::concepts::DistributedEdgeListGraphConcept106   void const_constraints(const G& cg) {
107     p = edges(cg);
108     E = num_edges(cg);
109     e = *p.first;
110     u = source(e, cg);
111     v = target(e, cg);
112   }
113   std::pair<edge_iterator,edge_iterator> p;
114   typename graph_traits<G>::vertex_descriptor u, v;
115   typename graph_traits<G>::edge_descriptor e;
116   edges_size_type E;
117   G g;
118 };
119 #else
120   BOOST_concept(DistributedVertexListGraph,(G))
121     : Graph<G>
122   {
123     typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
124     typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
125     typedef typename graph_traits<G>::traversal_category
126       traversal_category;
127     ~DistributedVertexListGraph() {
128       BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>));
129       BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
130         distributed_vertex_list_graph_tag>));
131 
132 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
133       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
134       // you want to use vector_as_graph, it is!  I'm sure the graph
135       // library leaves these out all over the place.  Probably a
136       // redesign involving specializing a template with a static
137       // member function is in order :(
138       using boost::vertices;
139 #endif
140       p = vertices(g);
141       v = *p.first;
142       const_constraints(g);
143     }
144     void const_constraints(const G& cg) {
145 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
146       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
147       // you want to use vector_as_graph, it is!  I'm sure the graph
148       // library leaves these out all over the place.  Probably a
149       // redesign involving specializing a template with a static
150       // member function is in order :(
151       using boost::vertices;
152 #endif
153 
154       p = vertices(cg);
155       v = *p.first;
156       V = num_vertices(cg);
157     }
158     std::pair<vertex_iterator,vertex_iterator> p;
159     typename graph_traits<G>::vertex_descriptor v;
160     G g;
161     vertices_size_type V;
162   };
163 
164   BOOST_concept(DistributedEdgeListGraph,(G))
165     : Graph<G>
166   {
167     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
168     typedef typename graph_traits<G>::edge_iterator edge_iterator;
169     typedef typename graph_traits<G>::edges_size_type edges_size_type;
170     typedef typename graph_traits<G>::traversal_category
171       traversal_category;
172     ~DistributedEdgeListGraph() {
173       BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>));
174       BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
175       BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
176       BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
177       BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
178         distributed_edge_list_graph_tag>));
179 
180       p = edges(g);
181       e = *p.first;
182       u = source(e, g);
183       v = target(e, g);
184       const_constraints(g);
185     }
186     void const_constraints(const G& cg) {
187       p = edges(cg);
188       E = num_edges(cg);
189       e = *p.first;
190       u = source(e, cg);
191       v = target(e, cg);
192     }
193     std::pair<edge_iterator,edge_iterator> p;
194     typename graph_traits<G>::vertex_descriptor u, v;
195     typename graph_traits<G>::edge_descriptor e;
196     edges_size_type E;
197     G g;
198   };
199 #endif
200 
201 #if BOOST_VERSION >= 103500
202   } // end namespace concepts
203 
204   using concepts::DistributedVertexListGraphConcept;
205   using concepts::DistributedEdgeListGraphConcept;
206 #endif
207 } // end namespace boost
208 
209 #if BOOST_VERSION >= 103500
210 #  include <boost/concept/detail/concept_undef.hpp>
211 #endif
212 
213 #endif // BOOST_GRAPH_DISTRIBUTED_CONCEPTS_HPP
214