00001 00028 #ifndef MSMAZES_CORE_GRAPH_PATH_UTILITY_HPP 00029 #define MSMAZES_CORE_GRAPH_PATH_UTILITY_HPP 00030 00031 // std::vector 00032 #include <vector> 00033 // boost::function_requires and basic concept check templates 00034 #include <boost/concept_check.hpp> 00035 // BOOST_PP_LESS 00036 #include <boost/preprocessor/comparison/less.hpp> 00037 // boost::tie 00038 #include <boost/utility.hpp> 00039 // boost::iterator_property_map, boost::property_traits, 00040 // boost::get and boost::put 00041 #include <boost/property_map.hpp> 00042 // BGL concept check templates 00043 #include <boost/graph/graph_concepts.hpp> 00044 // boost::graph_traits and BGL directed category tags 00045 #include <boost/graph/graph_traits.hpp> 00046 // boost::vertex_index_t 00047 #include <boost/graph/properties.hpp> 00048 //#include <boost/graph/adjacency_list.hpp> must be included before this file. 00049 // Boost.Parameter keyword objects used by the Core Graph algorithms 00050 #include <msmazes/core/graph/keywords.hpp> 00051 00052 #if BOOST_PP_LESS(BOOST_PARAMETER_MAX_ARITY, 5) 00053 #error Set BOOST_PARAMETER_MAX_ARITY to 5 or higher, please. 00054 #endif 00055 00056 namespace msmazes { 00057 00119 template < 00120 typename PredecessorMap 00121 , typename FrontInsertionSequence 00122 > 00123 inline bool 00124 makePath( 00125 typename boost::property_traits<PredecessorMap>::key_type source 00126 , typename boost::property_traits<PredecessorMap>::key_type target 00127 , const PredecessorMap p_map 00128 , FrontInsertionSequence& path 00129 ) 00130 { 00131 boost::function_requires< 00132 boost::FrontInsertionSequenceConcept< 00133 FrontInsertionSequence 00134 > 00135 >(); 00136 boost::function_requires< 00137 boost::ReadablePropertyMapConcept< 00138 PredecessorMap 00139 , typename FrontInsertionSequence::value_type 00140 > 00141 >(); 00142 00143 while (target != boost::get(p_map, target)) 00144 { 00145 path.push_front(target); 00146 target = boost::get(p_map, target); 00147 } 00148 00149 path.push_front(target); 00150 00151 return source == target; 00152 } 00153 00163 class DefaultRandomPathEdgePredicate 00164 { 00165 public: 00176 template <typename Edge, typename Graph> 00177 bool operator()(Edge e, Graph& g) const 00178 { 00179 return true; 00180 } 00181 }; 00182 00183 namespace _makeRandomPaths { 00184 00185 /* 00186 * The undirected-graph RandomSuccessor() function. 00187 */ 00192 template < 00193 typename InputGraph 00194 , typename Shuffler 00195 , typename UtilColorMap 00196 , typename RandomPathEdgePredicate 00197 > 00198 typename boost::graph_traits<InputGraph>::vertex_descriptor 00199 getRandomPredecessor( 00200 typename boost::graph_traits<InputGraph>::vertex_descriptor src_v 00201 , InputGraph& in_g 00202 , Shuffler& shuffler 00203 , UtilColorMap util_color_map 00204 , RandomPathEdgePredicate canBeRandomPathEdge 00205 , boost::undirected_tag 00206 ) 00207 { 00208 typedef boost::graph_traits<InputGraph> 00209 InputGraphTraits; 00210 typedef typename InputGraphTraits::vertex_descriptor 00211 InputVertex; 00212 typedef typename boost::property_traits<UtilColorMap>::value_type 00213 UtilColorValue; 00214 typedef boost::color_traits<UtilColorValue> 00215 UtilColor; 00216 00217 std::vector<InputVertex> prev; 00218 InputVertex v; 00219 typename InputGraphTraits::out_edge_iterator ei, ei_end; 00220 00221 /* 00222 * In an undirected graph, there is no difference between the in-edges 00223 * and the out-edges of a vertex. 00224 */ 00225 for ( 00226 boost::tie(ei, ei_end) = boost::out_edges(src_v, in_g); 00227 ei != ei_end; 00228 ++ei 00229 ) 00230 { 00231 v = boost::target(*ei, in_g); 00232 00233 if ( 00234 (boost::get(util_color_map, v) == UtilColor::white()) 00235 && canBeRandomPathEdge(*ei, in_g) 00236 ) 00237 { 00238 prev.push_back(v); 00239 } 00240 } 00241 00242 if (prev.empty()) 00243 { 00244 return src_v; 00245 } 00246 00247 return prev[shuffler(prev.size())]; 00248 } 00249 00250 /* 00251 * The bidirectional-graph RandomSuccessor() function. 00252 */ 00257 template < 00258 typename InputGraph 00259 , typename Shuffler 00260 , typename UtilColorMap 00261 , typename RandomPathEdgePredicate 00262 > 00263 typename boost::graph_traits<InputGraph>::vertex_descriptor 00264 getRandomPredecessor( 00265 typename boost::graph_traits<InputGraph>::vertex_descriptor src_v 00266 , InputGraph& in_g 00267 , Shuffler& shuffler 00268 , UtilColorMap util_color_map 00269 , RandomPathEdgePredicate canBeRandomPathEdge 00270 , boost::bidirectional_tag 00271 ) 00272 { 00273 typedef boost::graph_traits<InputGraph> 00274 InputGraphTraits; 00275 typedef typename InputGraphTraits::vertex_descriptor 00276 InputVertex; 00277 typedef typename boost::property_traits<UtilColorMap>::value_type 00278 UtilColorValue; 00279 typedef boost::color_traits<UtilColorValue> 00280 UtilColor; 00281 00282 std::vector<InputVertex> prev; 00283 InputVertex u; 00284 typename InputGraphTraits::in_edge_iterator ei, ei_end; 00285 00286 for ( 00287 boost::tie(ei, ei_end) = boost::in_edges(src_v, in_g); 00288 ei != ei_end; 00289 ++ei 00290 ) 00291 { 00292 u = boost::source(*ei, in_g); 00293 00294 if ( 00295 (boost::get(util_color_map, u) == UtilColor::white()) 00296 && canBeRandomPathEdge(*ei, in_g) 00297 ) 00298 { 00299 prev.push_back(u); 00300 } 00301 } 00302 00303 00304 if (prev.empty()) 00305 { 00306 return src_v; 00307 } 00308 00309 return prev[shuffler(prev.size())]; 00310 } 00311 00312 /* 00313 * The implementation. 00314 */ 00319 template < 00320 typename InputGraph 00321 , typename Shuffler 00322 , typename OutputPredecessorMap 00323 , typename RandomPathEdgePredicate 00324 > 00325 bool 00326 impl( 00327 InputGraph& in_g 00328 , typename boost::graph_traits<InputGraph>::vertex_descriptor source 00329 , Shuffler& shuffler 00330 , OutputPredecessorMap out_pred_map 00331 , RandomPathEdgePredicate canBeRandomPathEdge 00332 ) 00333 { 00334 boost::function_requires< 00335 boost::BidirectionalGraphConcept<InputGraph> 00336 >(); 00337 typedef boost::graph_traits<InputGraph> 00338 InputGraphTraits; 00339 typedef typename InputGraphTraits::vertex_descriptor 00340 InputVertex; 00341 typedef typename InputGraphTraits::vertex_iterator 00342 InputVertexIterator; 00343 boost::function_requires< 00344 boost::ReadWritePropertyMapConcept<OutputPredecessorMap,InputVertex> 00345 >(); 00346 typedef std::vector<boost::default_color_type> 00347 UtilColorVector; 00348 typedef typename boost::property_map< 00349 InputGraph 00350 , boost::vertex_index_t 00351 >::type 00352 VertexIndexMap; 00353 typedef boost::iterator_property_map< 00354 typename UtilColorVector::iterator 00355 , VertexIndexMap 00356 , boost::default_color_type 00357 , boost::default_color_type& 00358 > 00359 UtilColorMap; 00360 typedef typename boost::property_traits<UtilColorMap>::value_type 00361 UtilColorValue; 00362 typedef boost::color_traits<UtilColorValue> 00363 UtilColor; 00364 00365 VertexIndexMap 00366 util_index_map = boost::get(boost::vertex_index_t(), in_g); 00367 UtilColorVector 00368 util_color_vec_1(boost::num_vertices(in_g)); 00369 UtilColorMap 00370 util_color_map_1(util_color_vec_1.begin(), util_index_map); 00371 UtilColorVector 00372 util_color_vec_2(boost::num_vertices(in_g)); 00373 UtilColorMap 00374 util_color_map_2(util_color_vec_2.begin(), util_index_map); 00375 00376 InputVertexIterator vi, vend; 00377 00378 for (boost::tie(vi, vend) = boost::vertices(in_g); vi != vend; ++vi) 00379 { 00380 boost::put(out_pred_map, *vi, *vi); 00381 boost::put(util_color_map_1, *vi, UtilColor::white()); 00382 } 00383 00384 boost::put(util_color_map_1, source, UtilColor::black()); 00385 00386 InputVertexIterator ui, uend; 00387 InputVertex u, v; 00388 bool is_tree = true; 00389 00390 for (boost::tie(vi, vend) = boost::vertices(in_g); vi != vend; ++vi) 00391 { 00392 for (boost::tie(ui, uend) = boost::vertices(in_g); ui != uend; ++ui) 00393 { 00394 boost::put(util_color_map_2, *ui, UtilColor::white()); 00395 } 00396 00397 for ( 00398 v = *vi; 00399 boost::get(util_color_map_1, v) == UtilColor::white(); 00400 v = u 00401 ) 00402 { 00403 boost::put(util_color_map_2, v, UtilColor::black()); 00404 u = getRandomPredecessor( 00405 v 00406 , in_g 00407 , shuffler 00408 , util_color_map_2 00409 , canBeRandomPathEdge 00410 , typename InputGraphTraits::directed_category() 00411 ); 00412 00413 if (u == v) 00414 { 00415 is_tree = false; 00416 } 00417 00418 boost::put(out_pred_map, v, u); 00419 boost::put(util_color_map_1, v, UtilColor::black()); 00420 } 00421 } 00422 00423 return is_tree; 00424 } 00425 00430 struct parameters 00431 : boost::parameter::parameters< 00432 boost::parameter::required<keyword_tag::input_graph_arg> 00433 , boost::parameter::required<keyword_tag::source_vertex_arg> 00434 , boost::parameter::required<keyword_tag::shuffler_arg> 00435 , boost::parameter::required<keyword_tag::output_predecessor_map_arg> 00436 , boost::parameter::optional<keyword_tag::visitor_arg> 00437 > 00438 { 00439 }; 00440 } // namespace _makeRandomPaths 00441 00442 #ifdef MSMAZES_DOX 00443 00602 template < 00603 typename InputGraph 00604 , typename Vertex 00605 , typename Shuffler 00606 , typename OutputPredecessorMap 00607 , typename RandomPathEdgePredicate 00608 > 00609 bool 00610 makeRandomPaths( 00611 InputGraph& input_graph_arg 00612 , Vertex source_vertex_arg 00613 , Shuffler& shuffler_arg 00614 , OutputPredecessorMap output_predecessor_map_arg 00615 , RandomPathEdgePredicate visitor_arg 00616 ); 00617 00628 template <typename Params> 00629 void makeRandomPaths_with_named_params(Params& p) 00630 #else 00631 BOOST_PARAMETER_FUN( 00632 bool 00633 , makeRandomPaths 00634 , 4 00635 , 5 00636 , _makeRandomPaths::parameters 00637 ) 00638 #endif /* MSMAZES_DOX */ 00639 { 00640 return _makeRandomPaths::impl( 00641 p[input_graph_arg] 00642 , p[source_vertex_arg] 00643 , p[shuffler_arg] 00644 , p[output_predecessor_map_arg] 00645 , p[visitor_arg | DefaultRandomPathEdgePredicate()] 00646 ); 00647 } 00648 } // namespace msmazes 00649 00650 #endif /* MSMAZES_CORE_GRAPH_PATH_UTILITY_HPP */
Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.