Masking the class under the Boost graph. Part 1: Do not touch the interface

Prologue: Boost Concepts
Part 2: Completing the implementation of concept support

It took recently to alter the path finding algorithm for our game. The past was completely samopisny - step aside, and everything is bad ... I wanted to take it ready from a good source. It was then that I remembered that boost has functionality for working with graphs. Unfortunately, the approach, “find a function, call - and everything will work” did not take place. The emphasis in the library is placed on maximum flexibility of use, which negatively affected simplicity. At the same time, nothing deadly is better than from scratch to do (and then correct). There was no desire to communicate with other libraries either, while the boost in the project has been used for a long time ...

Given - the class of the playing field 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 of square cells. You can go to the neighboring cells, both directly and diagonally. The GameField :: canPass method allows you to check whether it is possible to pass into a given cell (that is, it exists and there is no barrier in it)
')
First of all, it was necessary to get acquainted with the concepts of boost - I wrote about them in the last article . Without this, all the requirements of the library to the graphs would have to be met at random, read eternity. I will not repeat, I will dwell only on a small addition to the previous article. It introduced the following way to test the concept

 BOOST_CONCEPT_ASSERT((SomeFuncAppropriate<SomeClass>)); 

I also complained that double brackets of the eye are cutting. It turns out that they cut not only me, and boost offers a more familiar option.

 boost::function_requires<SomeFuncAppropriate<SomeClass> >(); 

This is the form I will use in the future.

So. There is an initial class which needs to be disguised under the graph in order for boost to accept it. At the same time, the game field class itself (GameField) would not be desirable to change - here I present a simplified version of it, in fact, the interface of the class is already rather big, and changing it for the sake of a task not related to the direct functionality is impractical. To find the path we will use the algorithm A * (AStar) . The documentation states that the function boost :: astar_search requires two concepts from the graph: Vertex List Graph and Incidence Graph .

• VertexListGraph suggests the possibility of effectively traversing all the vertices of the graph. To do this, you will need to provide a means of determining the number of vertices and their search.
• IncidenceGraph must have an interface for iterating over all outgoing edges from a vertex. Also, for graphs of this type, it should be possible to obtain initial and final vertices for a given edge.

In addition, graph concepts require the definition of a number of special types, based on which boost will be able to manipulate our class. Let us dwell on them in more detail.

vertex_descriptor defines the type of vertex. In the GameField class, a vertex is defined by two cell coordinates. The first thought is to repeat this definition with the help of a structure or a pair of values ​​(std :: pair). However, depending on the type of graph, the vertex_descriptor must satisfy different concepts, that is, you will have to implement operators, constructors, etc. Not to say that it is very difficult, but it is easier to think and understand that the two coordinates of the peak are simply a feature of the realization of our playing field. In itself, the representation of the graph does not benefit from this (in our case). So it was decided that in the graph model the vertices would be simply numbered ((0, 0) -> 0, (0, 1) -> 1, and so on). This will allow using the standard int as the vertex type, which already supports all the necessary functionality. Of course, you have to implement two functions - to translate the index of the vertex in the coordinates of the graph

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

and back

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

Where the Vertex type comes from will be explained below.

edge_descriptor is an edge type. The edge is two vertices, and write: std :: pair <vertex_descriptor, vertex_descriptor>

directed_category - must match one of the special tag types (in fact, these are structures without data and methods) that will determine whether the graph is directed. In our case, it is not; therefore, we will use the value of boost :: undirected_tag

edge_parallel_category Another tag type that determines whether parallel edges are allowed in our graph (when there can be more than one edge between two vertices). Not allowed - use boost :: disallow_parallel_edge_tag

traversal_category Also tag. Defines ways to bypass the graph. Everything is a little more complicated here. For VertexListGraph, this should be boost :: vertex_list_graph_tag, and for IncidenceGraph, respectively, boost :: incidence_graph_tag. This is solved by creating a new tag type that would inherit both traversal options.

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

vertex_iterator Iterator for traversing vertices. Its implementation will be considered in the next part of the article.

out_edge_iterator An iterator for traversing outgoing edges from a vertex will also be implemented later.

degree_size_type Type in which the degree of the vertex (the number of outgoing edges) is expressed. Integer.

vertices_size_type A type in which the number of graph vertices is expressed. Also take for integer.

I’ll dwell on tag types (this is called tag dispatching correctly). They are used to overload functions to take advantage of a particular feature of the model. For example, by defining the tag boost :: undirected_tag, we inform the library that the edges of the graph are not directed. As a result, it will use functions that do not require separate assignment of outgoing and incoming edges.

Now you need to match the types of the playing field. The first binding option is to place additional definitions directly in the class.

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

However, I want to leave the GameField interface unchanged. Fortunately, boost provides this opportunity. All necessary types are retrieved by the library not from the class of the graph directly, that is, not so

 GameField::vertex_descriptor 

Instead, use the special template boost :: graph_traits

 boost::graph_traits<GameField>::vertex_iterator 

By default, it simply gets the appropriate type from the parameter class, i.e. does the following

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

You can write your own graph_traits specialization for the GameField class, which will work with it as we like, i.e. Do not try to look for the necessary types in the playing field. Above, the choice of types was described by words; now we consider the final implementation. Do not forget to put it in the namespace boost.

 namespace boost { template <> struct graph_traits<GameField> { typedef int vertex_descriptor; typedef std::pair <vertex_descriptor, vertex_descriptor> 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; }; } 

Please note that the structure contains several types that were not previously mentioned: in_edge_iterator, edge_iterator, edges_size_type. They are not needed to implement the concepts of VertexListGraph and IncidenceGraph, respectively, they can not specify (make void ).

In further work, it is advisable to refer to types in graph_traits (i.e., use vertex_descriptor instead of int, if we are talking about a vertex), so that you can leave yourself the opportunity to change if necessary in one place. Since the construction of the type boost :: graph_traits <GameField> :: vertex_descriptor is too heavy for writing and reading, we will introduce simple type names that we will use in the future

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

All the necessary types are defined. In graph_traits <GameField> , VertexIteratorImpl and OutEdgeIteratorImpl were used - we will consider the implementation of these iterators in the next part of the article . Also, the necessary functions for working with graphs will be implemented.