Random paths with random_spanning_tree()

Random paths with random_spanning_tree()


#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]; } }


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.