Can I apply the first word width search algorithm to boost library?

Question

My task is to find the shortest path in the matrix from one point to another. You can only move in this 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 - Starting point

F - Destination (Finish)

0 - free cells (we can move them)

1 - "walls" (we cannot move them)

Obviously, the first width search solves this problem in the most optimal way. I know that the Boost library supplies this algorithm, but I did not have Boost before.

How can I do the first search in my case using Boost? As I understand it, the breadth-first search algorithm for latitude Boost is only for graphics. I assume that converting a matrix into a graph with vertices m*n and m*(n -1) + (m-1)*n edges is not recommended.

Is it possible to apply the width search algorithm to the matrix (without converting it to a graph), or is it better to implement my own function for the first width search?

Answer 1

(I apologize in advance for the length of this answer. It has been a while since I used BGL, and I thought it would be a good update. Full code.)

The beauty of the Boost Graph library (and general programming in general) is that you do not need to use any particular data structure to take advantage of this algorithm. The matrix that you provided with the crawl rules already defines the schedule. All that is needed is to encode these rules in a feature class that can be used to use BGL algorithms.

In particular, we want to define the specialization of boost::graph_traits<T> for your chart. Suppose your matrix is ​​a single int array in row format. Unfortunately, the specialization of graph_traits for int[N] will be insufficient, because it does not provide any information about the size of the matrix. So let's define your schedule as 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 used composition for the cell data here, but you could just as easily use a pointer if it is controlled externally. Now we have a type encoded with matrix sizes that can be used to specialize graph_traits . But first, let's define some of the functions and types that we need.

Vertex type and 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 & ) { return vertex / COLS; } template< size_t ROWS, size_t COLS > size_t get_col( vertex_descriptor vertex, graph< ROWS, COLS > const & ) { return vertex % COLS; } template< size_t ROWS, size_t COLS > vertex_descriptor make_vertex( size_t row, size_t col, graph< ROWS, COLS > const & ) { return row * COLS + col; } } 

Types and functions for moving 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 ) { return 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 ) { return 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 ) { return 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 ) { return !(lhs == rhs); } } 

And finally, iterators and functions that help us cross incidence relationships between vertices and edges:

 namespace matrix { template< size_t ROWS, size_t COLS > vertex_descriptor source( edge_descriptor const & edge, graph< ROWS, COLS > const & ) { return edge.first; } template< size_t ROWS, size_t COLS > vertex_descriptor target( edge_descriptor const & edge, graph< ROWS, COLS > const & ) { return 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 up = make_vertex( row - 1, col, g ); if( g.cells[up] == FREE ) edges->push_back( edge_descriptor( vertex, up ) ); } if( row != ROWS-1 ) { vertex_descriptor down = make_vertex( row + 1, col, g ); if( g.cells[down] == FREE ) edges->push_back( edge_descriptor( vertex, down ) ); } 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 ) ); } } return 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 ); return std::distance( edges.first, edges.second ); } } 

Now we are ready to define our specialization 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() { return ROWS*COLS; } }; } 

And here's how to do a breadth-first search and find the 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" ; return 0; } 

Which displays the cells along the shortest path from start to finish:

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

Answer 2

You can definitely use the Boost Graph library for this! The idea of ​​implementing algorithms in this library is to abstract from any graph data structure and instead work in terms of iterators. For example, to move from one node to another node, the algorithms use an adjacency iterator. You essentially look at a specific algorithm, for example. BFS , and find out what concepts this algorithm requires: in this case, the graph that you used with it should be a "Vertex List Graph" and a "Disease Chart". Note that these are not specific classes, but concepts: they determine how to access the data structure. The algorithm also takes a number of additional arguments, such as a start node and a property map for marking (color) already visited nodes.

To use the algorithm with your matrix, you must give the "graphical view" of your matrix to the algorithm: a node is adjacent to its direct neighbors if the corresponding neighbor is not set to 1 (and, obviously, you don’t leave the edges of the matrix). Creating such a graph is not trivial, but I think it’s very useful to understand how the Boost Graph library works: even if you do not want to use this particular library, this is a good example of how algorithms are implemented in abstraction, so that the algorithm is applicable even in completely unforeseen situations (OK, I am biased: long before Jeremy created the Boost Graph library, I wrote a dissertation about the same, and we came to almost identical abstractions).

All that said, I think that using the first width search may not be worth the effort to learn about the Boost Graph library: this is such a trivial algorithm that you can simply implement directly. Furthermore, this is very similar to homework, in which case you probably should implement the algorithm yourself. Although it would be very impressive to use the Boost Graph library for this, your instructor cannot think so. What I find even more impressive is to implement BFS in a style that is independent of the data structure, as the Boost Graph library does, and then use it. Thanks to the guidance of the Boost Graph library, this is definitely doable, even as an exercise (although there is probably more effort than required). By the way, yes, I could send the code, but no, I won’t. I am happy to help with the specific problems that will be sent.