Masking a Class in Boost Graph. Part 2: Completing the Implementation of Concept Support

I’ll briefly remind you of the task. There’s a two-dimensional game field consisting of squares. Some of them are vacant and others are occupied. We should find a path through vacant squares from one field position to another one. We implemented the search algorithm in Boost. But it requires our field to fit the graph definition. Or rather the class should meet the requirements of two concepts: boost::VertexListGraph and boost::IncidenceGraph. We don't want to change the interface of game field, as it’s not a graph for the remaining project and will never be one.

In the previous part we’ve reviewed attaching the external associative types that are necessary for interpreting the class as boost graph. Of course types only are not enough. We should also implement several functions with the assigned signature, and iterators which will help the library to handle the game field as a graph.

Let’s begin with num_vertices function, which should return the number of graph vertices. In our case it’s the game field length multiplied by the width. We defined VerticesSizeType type in the first part of the article (it’s int actually).

VerticesSizeType num_vertices(const GameField& graph)
{
    return graph.getWidth() * graph.getHeight();
}

Now we can get down to implementing the first iterator. It will be in charge of traversing all graph vertices. We’ve settled earlier that we’d indicate vertices as integer numbers from zero to num_vertices. In order to avoid writing an iterator from scratch we’ll use boost::forward_iterator_helper helper class. It helps to get a full-blown iterator by defining just several basic iterators: increment (++), comparison (==) and dereferencing (*). Besides, the search algorithm requires a constructor for the iterator by default. Of course it’s impossible to use the object in such form. The library will assign a correct meaning for the iterator before use.

Let’s take a look at the class interface at first.

class VertexIteratorImpl : public boost::forward_iterator_helper
{
public:
    VertexIteratorImpl();
    VertexIteratorImpl(const GameField& field, int index);
    
    void operator++ ();
    bool operator== (const VertexIteratorImpl& anotherIterator) const;
    Vertex operator*() const;
    
private:
    bool isValid();
    
    int mIndex;
    const GameField* mField;
};

The iterator stores the number of the current vertex and the pointer to the game field. An explicit constructor should just be there by default, it doesn’t create any “working” object:

VertexIteratorImpl::VertexIteratorImpl()
: mField(NULL)
, mIndex(0)
{
    
}

The second constructor allows creating a full-featured object.

VertexIteratorImpl::VertexIteratorImpl(const GameField& field, int index)
: mField(&field)
, mIndex(index)
{
    
}

isValid — is a helper function that checks up whether the iterator is in the proper state.

bool VertexIteratorImpl::isValid()
{
    return (mField != NULL) && (mIndex =0);
}

Considering the fact that the vertex is a number, the implementation of iterators is quite easy and comes just to work with mIndex field. Here’s the check for equality:

bool VertexIteratorImpl::operator== (const VertexIteratorImpl& anotherIterator) const
{
    return mIndex == anotherIterator.mIndex;
}

That’s how the iterator increment is carried out. We should just check whether the index has exceeded the number of graph vertices

void VertexIteratorImpl::operator++ ()
{
    if (isValid()) {
        ++mIndex;
    }
}

Dereferencing comes to returning the vertex number

Vertex VertexIteratorImpl::operator*() const
{
    return mIndex;
}

After that we have another ability to create another function required by graph concepts — vertices. It should return two iterators of vertices – the initial one and the one following the last (analogue of end() in standard collections).

std::pair vertices(const GameField& graph)
{
    return std::make_pair(VertexIterator(graph, 0), VertexIterator(graph, num_vertices(graph)));
}

We defined VertexIterator type in the first part of the article (it’s an alias of VertexIteratorImpl). Now we’ll define edges. First of all, we should define a pair of functions that will return its initial and final vertex.

Vertex source(Edge edge, const GameField &graph)
{
    return edge.first;
}

Vertex target(Edge edge, const GameField &graph)
{
    return edge.second;
}

We should pass the graph as the second parameter, even if we don’t need it for operation (an edge is a pair of vertices in our case). We should just create an iterator of edges coming out from the specified vertex. It’s a bit more complex as for implementation, but still quite primitive. Procedure is the following: first of all, examine 8 vertices around the given one. If they are vacant, then there are edges, if they’re occupied, then there’s no path in this direction.
Let’s begin with the interface.

class OutEdgeIteratorImpl : public boost::forward_iterator_helper
{
public:
    
    OutEdgeIteratorImpl(const GameField& field, Vertex cellPosition, int index = 0);
    OutEdgeIteratorImpl();
    
    Edge operator*() const;
    void operator++ ();
    bool operator== (const OutEdgeIterator& other) const;
    
private:
    
    Vertex getCurrentPosition() const;
    Vertex getTargetPosition() const;
    void updateShift();
    bool isValid();
    
    int mShift;
    Vertex mCellPosition;
    const GameField* mField;
    
    static const int sShiftsX[8];
    static const int sShiftsY[8];
};

sShiftsX and sShiftsY — are arrays with displacement along x and y axis to traverse the neighboring vertices.

const int OutEdgeIteratorImpl::sShiftsX[8] = {
    -1, 0, 1,
    -1,    1,
    -1, 0, 1 };
const int OutEdgeIteratorImpl::sShiftsY[8] = {
    1,  1,  1,
    0,      0,
    -1, -1, -1};

It’s the same with the constructors. The first one creates a dummy object (we’ll need it for the library operation). We are going to use the second one ourselves.

OutEdgeIteratorImpl::OutEdgeIteratorImpl()
: mField(NULL)
, mCellPosition(0)
, mShift(0)
{
    
}

OutEdgeIteratorImpl::OutEdgeIteratorImpl(const GameField& field, Vertex cellPosition, int index/* = 0*/)
: mField(&field)
, mCellPosition(cellPosition)
, mShift(index)
{
    updateShift();
}

In contrast to vertices bypass, we won’t be able to return all edges in a row, as some of them can be nonexistent. Therefore, the increment iterator will contain updateShift method. Its task is to verify the validity of the current position of the iterator and “twist” it further.

void OutEdgeIteratorImpl::operator++ ()
{
    ++mShift;
    updateShift();
}

Verification is carried out using GameField::canPass(int x, int y) game field method. If it returns false (there’s no path to the given cell), then it will check the next available cell. There can be up to eight outgoing edges (from zero to eight).

void OutEdgeIteratorImpl::updateShift()
{
    if (isValid()) {
        int x, y;
        std::tie(x, y) = getCoordinates(mCellPosition, *mField);
        int dx = sShiftsX[mShift];
        int dy = sShiftsY[mShift];
        if (!mField->canPass(x + dx, y + dy)) {
            ++mShift;
            updateShift();
        }
    }
}

bool OutEdgeIteratorImpl::isValid()
{
    return (mField != NULL) && (mShift =0);
}

The iterator also contains two helper methods returning the initial (the one passed to the constructor) and outgoing (calculated on the basis of mShift shifting) vertex.

Vertex OutEdgeIteratorImpl::getCurrentPosition() const
{
    return mCellPosition;
}

Vertex OutEdgeIteratorImpl::getTargetPosition() const
{
    return getCurrentPosition() + sShiftsX[mShift] + mField->getWidth() * sShiftsY[mShift];
}

Dereferencing operator returns the following pair of vertices:

Edge OutEdgeIteratorImpl::operator*() const
{
    return std::make_pair(getCurrentPosition(), getTargetPosition());
}

Comparing edge iterators, as well as in case with vertices, comes to comparing index numbers

bool OutEdgeIteratorImpl::operator== (const OutEdgeIteratorImpl& other) const
{
    return mShift == other.mShift;
}

The last step is to define the function for traversing the edges, operating on the basis of created iterators. That’s how the traverse function of outgoing edges will look like for the given vertex:

std::pair out_edges(Vertex v, const GameField& graph)
{
    return std::make_pair(OutEdgeIterator(graph, v, 0), OutEdgeIterator(graph, v, 8));
}

We pass an object with index 8 as an iterator of completion, as there’s no edge with such number (permitted values from 0 to 7). The function of determining the number of outgoing edges also uses OutEdgeIterator iterator as the function calculates edges by traversing.

DegreeSizeType out_degree(Vertex v, const GameField& graph)
{
    DegreeSizeType result = 0;
    
    std::pair edges = out_edges(v, graph);
    for (OutEdgeIterator i = edges.first; i != edges.second; ++i) {
        ++result;
    }
    
    return result;
}

That’s it. Now we can write functions to verify concepts and enjoy the result. Our game field concurrently meets requirements of graphs of the two following types:

boost::function_requires<:vertexlistgraphconcept> >();
    boost::function_requires<:incidencegraphconcept> >();

That’s where we complete implementing the concepts. We are going to need some reworks for the operation of pathfinding algorithms. I can tell you more about them, are you interested in this series of articles?

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