Маскируем класс под граф Boost. Часть 1: Не трогаем интерфейс

Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «найди функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную гибкость использования, что негативно сказалось на простоте. В то же время и ничего смертельного — все лучше, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться желания не было, в то время как boost в проекте используется давно…

Дано — класс игрового поля со следующим (значимым для данной статьи) интерфейсом

class GameField
{
public:

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

Поле представляет собой обычную сетку из квадратных клеток. Ходить можно в соседние ячейки как прямо, так и по диагонали. Метод GameField::canPass позволяет проверить, можно ли пройти в заданную клетку (т.е. она существует и в ней не расположена преграда)

Первым делом потребовалось познакомиться с концепциями boost — о них я писал в прошлой статье ^[1]. Без этого выполнять все требования библиотеки к графам пришлось бы наугад, читай вечность. Повторяться не буду, остановлюсь лишь на небольшом дополнении предыдущей статьи. В ней был приведен следующий способ проверки концепции

BOOST_CONCEPT_ASSERT((SomeFuncAppropriate<SomeClass>));

Я еще жаловался, что двойные скобки глаза режут. Оказывается, резали не только мне, и boost предлагает более привычный вариант

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

Именно такой формой записи я буду пользоваться в дальнейшем.

Итак. Есть исходный класс, который нужно замаскировать под граф, чтобы boost его принял. При этом сам класс игрового поля (GameField) менять не хочется — здесь я привожу его упрощенный вариант, на самом деле интерфейс класса и без того немаленький, менять его ради не относящейся к прямой функциональности задачи нецелесообразно. Для поиска пути будем использовать алгоритм A* (AStar) ^[2]. В документации ^[3] говорится, что функция boost::astar_search требует от графа соответствия двум концепциям: Vertex List Graph ^[4] и Incidence Graph ^[5].

• VertexListGraph предполагает возможность эффективного обхода всех вершин графа. Для этого нужно будет предоставить средства определения количества вершин и их перебора.
• IncidenceGraph должен иметь интерфейс для перебора всех исходящих из вершины ребер. Также для графов этого типа должна существовать возможность получения начальной и конечной вершины для заданного ребра.

Кроме того, концепции графов требуют определения ряда специальных типов, опираясь на которые boost сможет манипулировать нашим классом. Остановимся на них подробнее.

vertex_descriptor определяет тип вершины. В классе GameField вершина определяется двумя координатами ячейки. Первая мысль — повторить это определение с помощью структуры или пары значений (std::pair). Однако vertex_descriptor в зависимости от типа графа должна удовлетворять разным концепциям, т.е придется реализовывать операторы, конструкторы и т.д. Не сказать, что очень сложно, но проще задуматься и понять, что две координаты вершины — это просто особенность реализации нашего игрового поля. Само по себе представление графа от этого (в нашем случае) не выигрывает. Так что было решено, что в модели графа вершины будут просто пронумерованы ((0, 0) -> 0, (0, 1) -> 1 и так далее). Это позволит использовать в качестве типа вершин стандартный int, который уже поддерживает всю необходимую функциональность. Конечно, придется реализовать две функции — для перевода индекса вершины в координаты графа

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

и обратно

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

Откуда взялся тип Vertex будет объяснено ниже.

edge_descriptor — тип ребра. Ребро — это две вершины, так и запишем: std::pair <vertex_descriptor, vertex_descriptor>

directed_category — должен соответствовать одному из специальных типов-тегов (по сути это структуры без данных и методов), котрые определят, является ли граф направленным. В нашем случае не является, поэтому использовать будем значение boost::undirected_tag

edge_parallel_category Еще один тип-тег, определяющий, допустимы ли в нашем графе параллельные ребра (когда между двумя вершинами может существовать больше одного ребра). Не допустимы — используем значение boost::disallow_parallel_edge_tag

traversal_category Тоже тег. Определяет способы обхода графа. Здесь все немного сложнее. Для VertexListGraph это должен быть boost::vertex_list_graph_tag, а для IncidenceGraph соответственно boost::incidence_graph_tag. Решается это созданием нового типа-тега, который наследовал бы оба варианта обхода

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

vertex_iterator Итератор для обхода вершин. Его реализацию рассмотрим в следующей части статьи.

out_edge_iterator Итератор для обхода исходящих из вершины ребер, также будет реализован в дальнейшем.

degree_size_type Тип, в котором выражается степень вершины (количество исходящих ребер). Целое число.

vertices_size_type Тип, в котором выражено количество вершин графа. Также примем за целое число.

Подробнее остановлюсь на типах-тегах (правильно это называется диспетчеризация тегов ^[6]). Они используются для перегрузки функций, чтобы воспользоваться той или иной особенностью модели. Например, определив тег boost::undirected_tag, мы сообщаем библиотеке, что ребра графа не являются направленными. В результате она будет использовать функции, не требующие отдельного задания исходящих и входящих ребер.

Теперь нужно сопоставить типы игровому полю. Первый вариант привязки — размещение дополнительных определений непосредственно в классе.

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

Однако интерфейс GameField хочется оставить без изменений. К счастью, boost предоставляет такую возможность. Все необходимые типы извлекаются библиотекой не из класса графа напрямую, то есть не так

GameField::vertex_descriptor

Вместо этого используется специальный шаблон boost::graph_traits

boost::graph_traits<GameField>::vertex_iterator

По умолчанию он просто получает соответствующий тип из класса-параметра, т.е. делает следующее

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

Можно написать свою специализацию graph_traits для класса GameField, которая будет работать с ним, как нам удобно, т.е. не пытаться искать необходимые типы в игровом поле. Выше был описан выбор типов словами, теперь рассмотрим окончательную реализацию. Не забываем поместить ее в пространство имен 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;
    };
}

Обратите внимание, что структура содержит несколько типов, которые ранее не упоминались: in_edge_iterator, edge_iterator, edges_size_type. Они не нужны для реализации концепций VertexListGraph и IncidenceGraph, соответственно их можно не уточнять (сделать void).

В дальнейшей работе желательно ссылаться на типы в graph_traits (т.е. использовать vertex_descriptor вместо int, если речь идет о вершине), чтобы оставить себе возможность менять при необходимости определения в одном месте. Поскольку конструкция вида boost::graph_traits&ltGameField&gt::vertex_descriptor тяжеловата как для написания, так и для прочтения, введем простые имена типов, которыми будем пользоваться в дальнейшем

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;

Всё, необходимые типы определены. В graph_traits&ltGameField&gt были использованы VertexIteratorImpl и OutEdgeIteratorImpl — реализацию этих итераторов рассмотрим в следующей части статьи. Также будут реализованы необходимые для поддерживаемых концепций функции работы с графами.

Автор: vadim_ig

Источник ^[7]