Маскируем класс под граф Boost. Часть 2: Завершаем реализацию поддержки концепций

Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса

Кратко напомню задачу. Есть двумерное игровое поле из клеток, часть из которых свободна, а часть занята. Требуется найти путь по свободным клеткам из одной позиции поля в другую. Алгоритм поиска пути реализован в Boost. Но он требует, чтобы наше поле подходило под определение графа. Точнее класс должен удовлетворять двум концепциям — boost::VertexListGraph и boost:: IncidenceGraph. При этом интерфейс игрового поля менять не хочется — для всего остального проекта это не граф и графом никогда не станет.

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

Начнем с функции num_vertices, которая, как можно догадаться из названия, должна возвращать количество вершин графа. Для нашего случая это длинна игрового поля умноженная на ширину. Тип VerticesSizeType определен в первой части статьи (на самом деле это int).

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

Теперь можно перейти к реализации первого итератора. Он будет отвечать за перебор всех вершин графа. Ранее мы условились, что вершины будем обозначать целыми числами от нуля до num_vertices. Чтобы избежать написания итератора с нуля, воспользуемся вспомогательным классом boost::forward_iterator_helper. Он позволяет получить полноценный итератор, определив лишь несколько базовых операторов: инкремента (++), сравнения (==) и разыменования (*). Кроме того, алгоритм поиска требует, чтобы для итератора существовал конструктор по умолчанию. Естественно в таком виде использование объекта невозможно — перед применением библиотека присвоит итератору корректное значение.

Для начала посмотрим на интерфейс класса

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; }; 

Итератор хранит номер текущей вершины и указатель на игровое поле. Явный конструктор по умолчанию просто должен быть — «рабочего» объекта он не создает:

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

Второй конструктор позволяет создать полнофункциональный объект

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

isValid — вспомогательная функция, которая проверяет, находится ли итератор в корректном состоянии (игровое поле задано, индекс имеет допустимое значение)

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

Учитывая, что вершина — это число, реализация операторов предельно проста, и сводится к работе с полем mIndex. Вот проверка на равенство

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

Так осуществляется приращение итератора — нужно только проверить, не превысил ли индекс число вершин графа

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

Разыменование сводится к возврату номера вершины

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

После этого появляется возможность создать еще одну функцию, требуемую концепциями графов — vertices. Возвращать она должна два итератора вершин — начальный и следующий за последним (аналог end() в стандартных коллекциях).

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

Тип VertexIterator определен в первой части статьи (это псевдоним VertexIteratorImpl). Теперь зададим ребра. Для начала нужно определить пару функций, которые, получив ребро, будут возвращать его начальную и конечную вершину.

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

Вторым параметром им должен передаваться граф, даже если для работы он не нужен (в нашем случае ребро — это пара вершин). Остается создать итератор исходящих из заданной вершины ребер. Он немного сложнее в реализации, но все равно достаточно примитивен. Алгоритм работы: проверить 8 вершин вокруг заданной, если они свободны, значит, ребра есть, если заняты, то пути в этом направлении не существует. Начнем с интерфейса

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 и sShiftsY — это массивы со смещениями по осям x и y для перебора соседних вершин.

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}; 

С конструкторами та же ситуация, которая была для итератора вершин — конструктор по умолчанию создает объект-пустышку (нужен для работы библиотеки), вторым конструктором будем пользоваться сами.

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(); } 

В отличие от обхода вершин, здесь не получится возвращать все ребра подряд — часть из них может не существовать. Поэтому оператор приращения будет содержать метод updateShift, задача которого — проверить допустимость текущего положения итератора и при необходимости «прокрутить» его дальше.

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

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

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); } 

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

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

Оператор разыменования возвращает эту пару вершин:

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

Сравнение итераторов ребер, как и для случая с вершинами, сводится к сравнению числовых индексов

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

И остается последний шаг — определить функции перебора ребер, работающие на основе созданных итераторов. Так будет выглядеть функция перебора исходящих ребер для заданной вершины

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

В качестве итератора окончания передается объекта с индексом 8, так как ребра с таким номером быть не может (допустимые значения от 0 до 7). Функция определения количества исходящих ребер также использует итератор OutEdgeIterator — она сосчитывает ребра перебором

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; } 

Все. Теперь можно написать функции проверки концепций и насладиться результатом — наше игровое поле одновременно удовлетворяет требованиям к графам двух типов:

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

На этом реализация концепций завершается. Для работы алгоритмов поиска пути потребуется еще несколько доработок — о них я расскажу в заключительной статье цикла.