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