Random paths with random_spanning_tree()














































Random paths with random_spanning_tree()



CODE


#include <boost/graph/adjacency_list.hpp> #include <boost/graph/random_spanning_tree.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/array.hpp> #include <array> #include <utility> #include <random> #include <iostream> #include <ctime> #include <cstdint> int main() { enum { topLeft, topRight, bottomRight, bottomLeft }; std::array<std::pair<int, int>, 4> edges{{ std::make_pair(topLeft, topRight), std::make_pair(topRight, bottomRight), std::make_pair(bottomRight, bottomLeft), std::make_pair(bottomLeft, topLeft) }}; struct edge_properties { int weight; }; typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> graph; graph g{edges.begin(), edges.end(), 4}; boost::array<int, 4> predecessors; std::mt19937 gen{static_cast<uint32_t>(std::time(0))}; boost::random_spanning_tree(g, gen, boost::predecessor_map(predecessors.begin()). root_vertex(bottomLeft)); int p = topRight; while (p != -1) { std::cout << p << '\n'; p = predecessors[p]; } }

OUTPUT




The algorithm introduced in the above example finds random paths. boost::random_spanning_tree() is similar to boost::dijkstra_shortest_paths(). It returns the predecessors of points in a container that is passed with boost::predecessor_map. In contrast to boost::dijkstra_shortest_paths(), the starting point isn’t passed directly as a parameter to boost::random_spanning_tree(). It must be passed as a named parameter. That’s why root_vertex() is called on the object of type boost::predecessor_map. The example finds random paths to the bottom left field.

Because boost::random_spanning_tree() is looking for a random path, a random number generator has to be passed as the second parameter. The example uses std::mt19937, which has been part of the standard library since C++11. You could also use a random number generator from Boost.Random.

It displays either 1, 0, and 3 or 1, 2, and 3. 1 is the top right field, 3 the bottom left field. There are only two possible paths from the top right field to the bottom left field: through the top left field or through the bottom right field. boost::random_spanning_tree() must return one of these two paths.




More Articles of Vinisha Kingrani:

Name Views Likes
C++ :: boost :: BOOST_FOREACH and BOOST_REVERSE_FOREACH 130 0
C++ boost::system::Creating error categories 110 0
C++ Boost.fusion :: A heterogeneous map with boost::fusion::map 307 0
C++ Boost.fusion :: A heterogeneous vector with boost::fusion::vector 232 0
C++ Boost.fusion :: Accessing elements in Fusion containers with iterators 121 0
C++ phrase_parse() with boost::spirit::qi::skip_flag::dont_postskip 167 0
Boost.MPI 119 2
Boost.Accumulators : : fcalculating weighted variance 124 0
Boost.Accumulators : : mean and variance 122 0
boost::accumulators::tag::count 130 0
boost : : boost.accumulators 111 0
Random paths with random_spanning_tree() 187 0
User-defined properties with dijkstra_shortest_paths() 163 0
Finding paths with dijkstra_shortest_paths() 292 0
Finding distances and paths with breadth_first_search() 137 0
Finding paths with breadth_first_search() 195 0
boost::breadth_first_search() 159 0
Initializing boost::adjacency_list with lines 128 0
boost::adjacent_vertices() and boost::out_edges() 262 1
Creating indexes automatically with boost::add_edge() 158 0
boost::adjacency_list with selectors 140 1
Accessing edges with boost : : edges 133 0
boost : : vertices() 180 1
boost :: add_vertex() 361 0
boost : : boost.graph : : adjacency_list 313 3

Comments