Masking a Class in Boost Graph. Part 1: Let the Interface Be

I had to rebuild a pathfinding algorithm for our game recently. The previous one (Boost Concepts) was bad as any sidestep was dangerous. So I wanted to take a ready algorithm from a good source. That’s exactly when I remembered about boost as there’s functionality for working with graphs. Unfortunately “find a function, call it and everything will work” approach wasn’t meant to be realized. The library is focused on the maximum use flexibility which has badly affected its simplicity. But it’s better than creating it from scratch (then fixing it). I didn’t want to bother with other libraries, while boost has already been used in the project.

The following is given: a game field class with the following (significant for this article) interface:

class GameField
{
public:

    GameField();
    
    bool canPass(int x, int y) const;
    int getWidth() const;
    int getHeight() const;
};

The field is a regular grid consisting of squares. It’s possible to go to neighboring cells straight and diagonally.
GameField::canPass method allows to check whether it’s possible to enter the given square (it’s there and has no obstruction).

First of all I had to get familiar with boost concepts. I’ve written about them in the previous article. Without knowing the concepts I would have had to execute all library requirements by guess-work. I won’t repeat myself but will just dwell on some additions to the article. The following way of concept checkup was provided in it:

BOOST_CONCEPT_ASSERT((SomeFuncAppropriate));

I mentioned that double brackets offended the eye. As it turned out, I wasn’t the only one “offended” so now boost suggests the better variant:

boost::function_requires >();

That’s exactly the form of writing I’ll use in future.

So, there’s an initial class to be masked in graph so that boost would accept it. I don’t feel like changing the game field class. I’ll provide its simplified variant here. The class interface is big enough so it’s no use changing it for the task that has nothing to do with direct functionality. We’ll utilize A* (AStar) algorithm for the pathfinding.
It’s mentioned in documentation that boost::astar_search function requires the graph to fit two concepts: Vertex List Graph and Incidence Graph.

• VertexListGraph assumes a possibility of efficient bypass of all graph vertices. For that purpose we’ll have to provide facilities for defining the number of vertices and traversing them.
• IncidenceGraph should have its own interface to traverse all edges coming from the vertex. There should also be a facility for this type graphs to get an initial and final vertices of the given edge.

Besides that, graph concepts require defining a number of special types basing on which boost will be able to handle our class. Let’s review them in details.

vertex_descriptor defines the vertex type. In GameField class the vertex is defined by two cell coordinates. The first idea coming to mind is to repeat this definition using a structure or a pair of values (std::pair). Depending on the graph type vertex_descriptor should satisfy different concepts. So we’ll have to implement operators, constructors, etc. It’s not that difficult but it’s easier to think and understand that two vertex coordinates are just a peculiarity of our game field implementation. So I decided that vertices in the graph model will be just numbered ((0, 0) -> 0, (0, 1) -> 1 etc). This will allow using a standard int as a vertex type. It already supports all the necessary functionality. Of course, we’ll have to implement two functions for converting the vertex index to the graph coordinates.

std::pair getCoordinates(const Vertex position, const GameField& graph)
{
    return std::make_pair(position % graph.getWidth(), position / graph.getWidth());
}

and conversely

Vertex getVertex(int x, int y, const GameField& graph)
{
    return x + y * graph.getWidth();
}

I’ll explain later where Vertex type came from.

edge_descriptor is the edge type. An edge is two vertices. So we’ll write: std::pair

directed_category should correspond to one of special tag types (they are structures without data and methods) that will define whether the graph is directed. In our case it’s not, so we’ll use boost::undirected_tag value
edge_parallel_category is another tag type defining whether there can be parallel edges in our graph (when there can be more than one edge between two vertices). Parallel edges are not acceptable so we’ll use boost::disallow_parallel_edge_tag

traversal_category is also a tag. It defines the ways of bypassing the graph. It’s a bit more complicated here. It should be boost::vertex_list_graph_tag for VertexListGraph and boost::incidence_graph_tag for IncidenceGraph accordingly. We can solve it by creating a new tag type that will inherit both bypass variants

struct game_field_traversal_catetory:
    public boost::vertex_list_graph_tag,
    public boost::incidence_graph_tag
{
};

vertex_iterator is an iterator to bypass the vertices. We’ll consider its implementation in the following part of our article.

out_edge_iterator is an iterator to bypass the edges coming from the vertex. It will also be implemented later on.

degree_size_type is the type defining the degree of vertex (the number of edges coming out). Accept it as an integer number.

vertices_size_type is the type expressing the number of graph vertices. Accept it as an integer number as well.

Now I’ll dwell on tag types (tag dispatching). They’re used to restart functions, use one or other model peculiarity. For example, having defined tag boost::undirected_tag we notify the library that graph edges aren’t directed. As a result, it’ll utilize functions not requiring a separate definition of incoming and outgoing edges.

Now we should confront types to the game field. The first variant of binding is placing additional definitions in the class.

class GameField
{
public:
        typedef int vertex_descriptor;
...

I would like to remain GameField unchanged. Fortunately, boost provides such ability. The library doesn’t extract all the necessary types from the graph class directly. Meaning not the following way:

GameField::vertex_descriptor

A special boost::graph_traits template is used instead of this

boost::graph_traits::vertex_iterator

It just gets a corresponding type from a parameter class, i.e. it does the following:

template 
  struct graph_traits {
    typedef typename Graph::vertex_descriptor vertex_descriptor;
...

We could write our own specialization of graph_traits for GameField class, which will handle it the way we need. It won’t try to look for the necessary types in the game field.
We’ve described the way to choose types. Now let’s review the final implementation. Don’t forget to place it into boost namespace.

namespace boost
{
   template <> struct graph_traits
    {
        typedef int vertex_descriptor;
        typedef std::pair  edge_descriptor;
        typedef boost::undirected_tag directed_category;
        typedef boost::disallow_parallel_edge_tag edge_parallel_category;
        typedef game_field_traversal_catetory traversal_category;
        
        typedef VertexIteratorImpl vertex_iterator;
        typedef OutEdgeIteratorImpl out_edge_iterator;
        typedef int degree_size_type;
        typedef int vertices_size_type;
        
        typedef void in_edge_iterator;
        typedef void edge_iterator;
        typedef void edges_size_type;
    };
}

Pay attention that the structure contains several types that have already been mentioned before: in_edge_iterator, edge_iterator, edges_size_type. We don’t need them to implement VertexListGraph and IncidenceGraph concepts, so we don’t have to specify them (make void).

In order to have a possibility of changing definitions in one place when necessary it’s better to refer to types in graph_traits (i.e. use vertex_descriptor instead of int if it refers to a vertex) in future. Since boost::graph_traits::vertex_descriptor construction is a bit difficult for both writing and reading, let’s introduce simple type names we’re going to use later on:

typedef boost::graph_traits::vertex_descriptor Vertex;
typedef boost::graph_traits::edge_descriptor Edge;
typedef boost::graph_traits::vertex_iterator VertexIterator;
typedef boost::graph_traits::out_edge_iterator OutEdgeIterator;
typedef boost::graph_traits::degree_size_type DegreeSizeType;
typedef boost::graph_traits::vertices_size_type VerticesSizeType;

That’s it. We’ve defined all the necessary types. We used VertexIteratorImpl and OutEdgeIteratorImpl in graph_traits. We’ll review the implementation of these iterators in the following part of the article. We are also going to implement necessary concepts for the supported functions of working with graphs.

1. Boost Concepts
2. Masking a Class in Boost Graph. Part 1: Let the Interface Be
3. Masking a Class in Boost Graph. Part 2: Completing the Implementation of Concept Support
4. Masking a Class in Boost Graph. Part 3: Finding the Path