Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

Пролог: Доктрины 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)
{

}

2-й конструктор разрешает сделать полнофункциональный объект

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

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

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

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

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB