c++ - Is it possible to apply breadth-first search algorithm of boost library to matrix? -

c++ - Is it possible to apply breadth-first search algorithm of boost library to matrix? -

my task find shortest way in matrix 1 point other. possible move in such direction (up, down, left, right).

0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 f 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 s 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0

s - start point

f - destination place (finish)

0 - free cells (we can move through them)

1 - "walls" (we can't move through them)

it obvious breadth first search solves problem in optimal way. know boost library supplies algorithm, haven't boost before.

how can breadth first search in case using boost? understood, breadth first search algorithm of boost intended graphs. guess isn't thought convert matrix graph m*n vertices , m*(n -1) + (m-1)*n edges.

can apply breadth first search algorithm matrix (without converting graph), or improve implement own function breadth first search?

(apologies in advance length of answer. it's been while since i've used bgl , thought create refresher. total code here.)

the beauty of boost graph library (and generic programming in general) don't need utilize particular info construction in order take advantage of given algorithm. matrix you've provided along rules traversing define graph. that's needed encode rules in traits class can used leverage bgl algorithms.

specifically, want define specialization of boost::graph_traits<t> graph. let's assume matrix single array of int's in row-major format. unfortunately, specializing graph_traits int[n] won't sufficient doesn't provide info dimensions of matrix. let's define graph follows:

namespace matrix { typedef int cell; static const int free = 0; static const int wall = 1; template< size_t rows, size_t cols > struct graph { cell cells[rows*cols]; }; }

i've used composition cell info here utilize pointer if it's managed externally. have type encoded matrix dimensions can used specialize graph_traits. first let's define of functions , types we'll need.

vertex type , helper functions:

namespace matrix { typedef size_t vertex_descriptor; template< size_t rows, size_t cols > size_t get_row( vertex_descriptor vertex, graph< rows, cols > const & ) { homecoming vertex / cols; } template< size_t rows, size_t cols > size_t get_col( vertex_descriptor vertex, graph< rows, cols > const & ) { homecoming vertex % cols; } template< size_t rows, size_t cols > vertex_descriptor make_vertex( size_t row, size_t col, graph< rows, cols > const & ) { homecoming row * cols + col; } }

types , functions traverse vertices:

namespace matrix { typedef const cell * vertex_iterator; template< size_t rows, size_t cols > std::pair< vertex_iterator, vertex_iterator > vertices( graph< rows, cols > const & g ) { homecoming std::make_pair( g.cells, g.cells + rows*cols ); } typedef size_t vertices_size_type; template< size_t rows, size_t cols > vertices_size_type num_vertices( graph< rows, cols > const & g ) { homecoming rows*cols; } }

edge type:

namespace matrix { typedef std::pair< vertex_descriptor, vertex_descriptor > edge_descriptor; bool operator==( edge_descriptor const & lhs, edge_descriptor const & rhs ) { homecoming lhs.first == rhs.first && lhs.second == rhs.second || lhs.first == rhs.second && lhs.second == rhs.first; } bool operator!=( edge_descriptor const & lhs, edge_descriptor const & rhs ) { homecoming !(lhs == rhs); } }

and finally, iterators , functions help traverse incidence relationships exist between vertices , edges:

namespace matrix { template< size_t rows, size_t cols > vertex_descriptor source( edge_descriptor const & edge, graph< rows, cols > const & ) { homecoming edge.first; } template< size_t rows, size_t cols > vertex_descriptor target( edge_descriptor const & edge, graph< rows, cols > const & ) { homecoming edge.second; } typedef boost::shared_container_iterator< std::vector< edge_descriptor > > out_edge_iterator; template< size_t rows, size_t cols > std::pair< out_edge_iterator, out_edge_iterator > out_edges( vertex_descriptor vertex, graph< rows, cols > const & g ) { boost::shared_ptr< std::vector< edge_descriptor > > edges( new std::vector< edge_descriptor >() ); if( g.cells[vertex] == free ) { size_t row = get_row( vertex, g ), col = get_col( vertex, g ); if( row != 0 ) { vertex_descriptor = make_vertex( row - 1, col, g ); if( g.cells[up] == free ) edges->push_back( edge_descriptor( vertex, ) ); } if( row != rows-1 ) { vertex_descriptor downwards = make_vertex( row + 1, col, g ); if( g.cells[down] == free ) edges->push_back( edge_descriptor( vertex, downwards ) ); } if( col != 0 ) { vertex_descriptor left = make_vertex( row, col - 1, g ); if( g.cells[left] == free ) edges->push_back( edge_descriptor( vertex, left ) ); } if( col != cols-1 ) { vertex_descriptor right = make_vertex( row, col + 1, g ); if( g.cells[right] == free ) edges->push_back( edge_descriptor( vertex, right ) ); } } homecoming boost::make_shared_container_range( edges ); } typedef size_t degree_size_type; template< size_t rows, size_t cols > degree_size_type out_degree( vertex_descriptor vertex, graph< rows, cols > const & g ) { std::pair< out_edge_iterator, out_edge_iterator > edges = out_edges( vertex, g ); homecoming std::distance( edges.first, edges.second ); } }

now we're ready define our specialization of boost::graph_traits:

namespace boost { template< size_t rows, size_t cols > struct graph_traits< matrix::graph< rows, cols > > { typedef matrix::vertex_descriptor vertex_descriptor; typedef matrix::edge_descriptor edge_descriptor; typedef matrix::out_edge_iterator out_edge_iterator; typedef matrix::vertex_iterator vertex_iterator; typedef boost::undirected_tag directed_category; typedef boost::disallow_parallel_edge_tag edge_parallel_category; struct traversal_category : virtual boost::vertex_list_graph_tag, virtual boost::incidence_graph_tag {}; typedef matrix::vertices_size_type vertices_size_type; typedef matrix::degree_size_type degree_size_type; static vertex_descriptor null_vertex() { homecoming rows*cols; } }; }

and here's how perform breadth-first search , find shortest paths:

int main() { const size_t rows = 8, cols = 8; using namespace matrix; typedef graph< rows, cols > my_graph; my_graph g = { free, free, free, free, wall, free, free, free, wall, free, free, free, free, free, free, free, free, free, free, wall, free, wall, free, free, free, wall, free, wall, free, free, free, free, free, free, free, wall, free, free, free, free, free, free, free, wall, free, free, wall, free, free, free, free, free, free, free, wall, free, free, free, free, free, free, free, wall, free, }; const vertex_descriptor start_vertex = make_vertex( 5, 1, g ), finish_vertex = make_vertex( 2, 6, g ); vertex_descriptor predecessors[rows*cols] = { 0 }; using namespace boost; breadth_first_search( g, start_vertex, visitor( make_bfs_visitor( record_predecessors( predecessors, on_tree_edge() ) ) ). vertex_index_map( identity_property_map() ) ); typedef std::list< vertex_descriptor > path; path p; for( vertex_descriptor vertex = finish_vertex; vertex != start_vertex; vertex = predecessors[vertex] ) p.push_front( vertex ); p.push_front( start_vertex ); for( path::const_iterator cell = p.begin(); cell != p.end(); ++cell ) std::cout << "[" << get_row( *cell, g ) << ", " << get_col( *cell, g ) << "]\n" ; homecoming 0; }

which outputs cells along shortest path start finish:

[5, 1] [4, 1] [4, 2] [3, 2] [2, 2] [1, 2] [1, 3] [1, 4] [1, 5] [1, 6] [2, 6]

c++ boost matrix breadth-first-search boost-graph