Masking the class under the Boost graph. Part 2: Completing the implementation of concept support

Prologue: Boost Concepts
Part 1: Connection of associated types without interfering with the source class interface

Briefly recall the task. There is a two-dimensional playing field of cells, some of which are free, and some are occupied. It is required to find a path through the free cells from one position of the field to another. The pathfinding algorithm is implemented in Boost. But he demands that our field fit the definition of a graph. More precisely, the class must satisfy two concepts - boost :: VertexListGraph and boost :: IncidenceGraph . At the same time, there is no wish to change the interface of the playing field - for the rest of the project this is not a graph and it will never become a graph.

In the last part, we examined the connection of external associated types that are necessary for interpreting a class as a boost graph. Of course, some types are not enough. You also need to implement several functions with a given signature and iterators, with the help of which the library will be able to manipulate the game field as a graph.

Let's start with the function num_vertices , which, as the name suggests, should return the number of graph vertices. For our case, this is the length of the playing field multiplied by the width. The VerticesSizeType type is defined in the first part of the article (in fact, it is an int).
')

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

Now you can go to the implementation of the first iterator. He will be responsible for enumerating all the vertices of the graph. Earlier we agreed that vertices will be denoted by integers from zero to num_vertices . To avoid writing an iterator from scratch, we use the auxiliary class boost :: forward_iterator_helper . It allows you to get a full-fledged iterator, defining only a few basic operators: increment (++), comparisons (==) and dereferencing (*). In addition, the search algorithm requires that a default constructor exist for the iterator. Naturally, in this form, using an object is impossible - before applying, the library will assign the correct value to the iterator.

First, look at the class interface

 class VertexIteratorImpl : public boost::forward_iterator_helper<VertexIteratorImpl, Vertex, std::ptrdiff_t, Vertex*, Vertex> { 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 current vertex number and a pointer to the playing field. The explicit default constructor simply has to be - it does not create a “working” object:

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

The second constructor allows you to create a full-featured object.

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

isValid - an auxiliary function that checks whether the iterator is in the correct state (the playing field is set, the index has a valid value)

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

Given that a vertex is a number, the implementation of operators is extremely simple, and it comes down to working with the mIndex field. Here is a test for equality

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

This is the increment of the iterator - you only need to check if the index does not exceed the number of graph vertices

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

Dereferencing is reduced to returning the vertex number

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

After that, it becomes possible to create another function required by graph concepts - vertices . It must return two iterators of vertices - the initial one and the next after the last (analogous to end () in standard collections).

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

The VertexIterator type is defined in the first part of the article (this is an alias VertexIteratorImpl). Now let's set the edges. First you need to define a couple of functions that, having received an edge, will return its initial and final vertices.

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

The second parameter is to transfer the graph to them, even if it is not needed for work (in our case, the edge is a pair of vertices). It remains to create an iterator outgoing edges from a given vertex. It is a little more difficult to implement, but still quite primitive. Algorithm of work: check 8 vertices around a given one, if they are free, then there are edges, if busy, there is no way in this direction. Let's start with the interface

 class OutEdgeIteratorImpl : public boost::forward_iterator_helper<OutEdgeIterator, Edge, std::ptrdiff_t, Edge*, Edge> { 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 offsets along the x and y axes to iterate over adjacent 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}; 

With constructors, the same situation as for the vertex iterator - the default constructor creates a dummy object (needed for the library to work), we will use the second constructor 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(); } 

Unlike bypassing the vertices, it will not be possible to return all the edges in a row - some of them may not exist. Therefore, the increment operator will contain the updateShift method, whose task is to check the validity of the current position of the iterator and, if necessary, “scroll” it further.

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

The check is performed using the GameField :: canPass (int x, int y) game field method, if it returns false (there is no path to the specified cell), the next neighboring cell will be checked. Outgoing edges can be 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 < 8) && (mShift >=0); } 

The iterator also contains two auxiliary methods that return the initial vertex (which was passed to the constructor) and outgoing (calculated based on the mShift offset).

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

The dereference operator returns this pair of vertices:

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

Comparison of edge iterators, as well as for the case with vertices, reduces to comparing the numerical indices

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

And the last step remains - to determine the edge search functions, which work on the basis of the created iterators. This is how the search function for outgoing edges for a given vertex will look like.

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

As an iterator, the end is passed to an object with index 8, since there can be no edges with this number (valid values ​​are from 0 to 7). The function of determining the number of outgoing edges also uses an OutEdgeIterator iterator - it counts the edges by search.

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

Everything. Now you can write concept validation functions and enjoy the result - our playing field simultaneously satisfies the requirements for two types of columns:

  boost::function_requires<boost::VertexListGraphConcept<GameField> >(); boost::function_requires<boost::IncidenceGraphConcept<GameField> >(); 

This completes the implementation of the concepts. For the path finding algorithms to work, a few more improvements will be needed - I will tell about them in the final article of the cycle.