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

Question

My task is to find the shortest way in a matrix from one point to other. It is possible to move only 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 is obvious that a breadth first search solves this problem in the most optimal way. I know that the Boost library supplies this algorithm, but I haven't Boost before.

How can I do a breadth first search in my case using Boost? As I understood, breadth first search algorithm of Boost is intended only for graphs. I guess that it isn't a good idea to convert matrix to graph with m*n vertices and m*(n -1) + (m-1)*n edges.

Can I apply breadth first search algorithm to matrix (without converting it to a graph), or is it better to implement my own function for breadth first search?

Answer 1

(Apologies in advance for the length of this answer. It's been a while since I've used the BGL and I thought this would make a good refresher. Full code is here.)

The beauty of the Boost Graph Library (and generic programming in general) is that you don't need to use any particular data structure in order to take advantage of a given algorithm. The matrix you've provided along with the rules about traversing it already define a graph. All that's needed is to encode those rules in a traits class that can be used to leverage the BGL algorithms.

Specifically, what we want to do is to define a specialization of boost::graph_traits<T> for your graph. Let's assume your matrix is a single array of int's in row-major format. Unfortunately, specializing graph_traits for int[N] won't be sufficient as it doesn't provide any information about the dimensions of the matrix. So let's define your graph 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've used composition for the cell data here but you could just as easily use a pointer if it's to be managed externally. Now we have a type encoded with the matrix dimensions that can be used to specialize graph_traits. But first let's define some of the functions and types we'll 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 to traverse the 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 to help us traverse the incidence relationships that exist between the 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're ready to 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() { return ROWS*COLS; }
  };
}

And here's how to perform the 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 outputs 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 how the algorithms in this library are implemented is to abstract from any graph data structure and instead operate in terms of iterators. For example, to move from one node to another node, the algorithms use an adjacency iterator. You would essentially look and a particular algorithm, e.g. BFS, and find out what concepts this algorithm requires: in this case the graph you used with it needs to be a "Vertex List Graph" and an "Incidence Graph". Note that these are not concrete classes but concepts: they specify how the data structure is to be accessed. The algorithm also takes a number of additional arguments like the start node and a property map to mark (color) the nodes already visited.

To use the algorithm with your matrix you would give a "graph view" of your matrix to the algorithm: a node is adjacent to its direct neighbors unless the respective neighbor is set to 1 (and, obviously, you don't walk off the edges of the matrix). Creating a graph like this isn't entirely trivial but I think it is very useful to understand how the Boost Graph library works: even if you don't want to use this particular library, it is a good example on how algorithms are implemented in abstractions to make the algorithm applicable even in entirely unforeseen situations (OK, I'm biased: long before Jeremy created the Boost Graph library I have written my diploma thesis about roughly the same thing and we came up with essentially identical abstractions).

All that said, I think that using breadth first search may not be worth the effort to learn about the Boost Graph library: it is such a trivial algorithm that you might want to just implement it directly. Also, this looks pretty much like a homework assignment in which case you are probably meant to implement the algorithm yourself. Although it might be quite impressive to have used the Boost Graph library for this, your instructor may not consider it that way. What I would consider even more impressive would be to implement BFS in a style independent from the data structure as the Boost Graph library does and then use this. With the guidance from the Boost Graph library this is definitely doable, even as an exercise (although probably more effort than required). BTW, yes, I could post code but, no, I won't. I'm happy to help with concrete problems being posted, though.