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

в 22:34, , рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: , , , , , ,

Маскируем класс под граф 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> >();

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

Автор: vadim_ig

Источник

Поделиться

* - обязательные к заполнению поля