Определения

Паросочетанием называется подмножество рёбер графа, содержащее только взаимонеинцидентные рёбра. Любая вершина графа инцидентна не более, чем одному из рёбер паросочетания. Рёбра, входящие в паросочетания, и вершины, инцидентные этим рёбрам, называются насыщенными.

Максимальным называется паросочетание, к которому нельзя добавить ни одного ребра из множества рёбер графа, или, что то же самое, максимальное паросочетание не является подмножеством никакого другого паросочетания.

Наибольшим называется паросочетание, содержащее наибольшее число рёбер. Наибольшее паросочетание является максимальным, обратное неверно.

Полным называется паросочетание, насыщающее все вершины графа. Если полное паросочетание существует, то любое наибольшее паросочетание будет также полным паросочетанием.

Оптимальным называется наибольшее паросочетание в графе с заданными весами рёбер, минимизирующее суммарный вес входящих в паросочетание рёбер.

Алгоритмы

Введённые определения позволяют поставить следующие задачи.

1. Построить некоторое наибольшее паросочетание.
2. Проверить, существует ли полное паросочетание.
3. Построить оптимальное паросочетание для заданных весов рёбер.

Для простоты ограничимся рассмотрением двудольных графов.

Двудольным графом называется граф, вершины которого можно разделить на два непересекающихся множества X и Y таких, что все рёбра графа будут иметь вид (x, y), где x принадлежит X, а y — Y. Множества X и Y называются долями графа.

Добавим к графу две вспомогательные вершины s и t. Соединим s с каждой вершиной из X, и каждую вершину из Y соединим с вершиной t. Зададим всем рёбрам единичную пропускную способность и будем искать целочисленный максимальный поток (максимальный 0-1-поток) из s в t на построенной таким образом сети. Рёбра с единичным потоком составят некоторое из наибольших паросочетаний. Поэтому задачу 1 можно решить с помощью алгоритма построения максимального потока. Построив же некоторое наибольшее паросочетание не сложно проверить его на полноту, решив и задачу 2.

Кроме алгоритмов построения максимального потока существует адаптация алгоритма Форда-Фалкерсона к задаче построения наибольшего паросочетания, известная как алгоритм Хопкрофта-Карпа. Для решения задачи 2, а именно определения отсутствия полного паросочетания без построения наибольшего паросочетания, также существуют специальные алгоритмы (например, алгоритм Куна). Для решения задачи 3 существует алгоритм Куна-Манкреса, также известный как венгерский алгоритм.

Пример реализации

Возьмём часть кода до строки 506 и поместим её в файл Graph4.h. Для использования алгоритмов построения максимального потока в качестве алгоритмов поиска наибольшего паросочетания нам понадобится три элемента: а) функция, формирующая матрицу пропускных способностей, б) функция-обёртка алгоритма построения максимального потока, в) функция, «извлекающая» паросочетание из матрицы потока.

Первая и третья функции названы prepareBipartiteForMaxFlow и matchingFromFlow соответственно. Размеры долей графа передаются как константы X и Y. Для представления паросочетания используется вектор индексов, отображающий индекс вершины из доли X (от 0 до X — 1) в индекс вершины из доли Y (от 0 до Y), при этом фиктивное значение Y используется, чтобы показать, что вершина не насыщена.

Собственно привязка осуществляется тривиальной функцией fullMatching, которая использует вспомогательную структуру-шаблон FullMatching<class MaxFlowWrapper>, функцию-член find которого и вызывает (так сделано из-за того, что в C++ нельзя определять специализации функций-шаблонов).

Класс, переданный в качестве параметра MaxFlowWrapper, уже «переадресует» вызов конкретному алгоритму построения максимального потока или решает задачу самостоятельно.

Определены следующие классы, подходящие в качестве параметра MaxFlowWrapper: три обёртки алгоритмов из Graph4.h EdmondsKarpMaxFlow, PreflowPushingMaxFlow и PushRelabelMaxFlow, а также реализация алгоритма Хопкрофта-Карпа HopcroftKarp.

Итак, код реализации и теста: codepad.

Введение

Ранее приводился алгоритм Дейкстры поиска кратчайших путей от заданной вершины до всех остальных вершин графа с неотрицательными весами рёбер. Существует алгоритм (алгоритм A*), развивающий идею алгоритма Дейкстры для ускорения поиска пути между двумя заданными вершинами графа, если известна оценка длины кратчайшего пути между любыми двумя вершинами, называемая «эвристикой». Алгоритм этот довольно популярен и используется в робототехнике и играх.

Реализация

Была написана реализация, отталкивающаяся от тех же принципов, что и ранее созданная реализация алгоритма Дейкстры. Итак, функция-шаблон, реализующая алгоритм А*, принимает следующие параметры (слова в кавычках, описывают поведение объектов, а не реальное представление их в памяти):

• (вывод) ссылку на «массив» предшественников Pr, после выполнения алгоритма Pr[v] == u, если вершина с индексом v стоит сразу за вершиной с индексом u на искомом пути;
• (ввод) ссылку на «матрицу» весов рёбер графа;
• (ввод) ссылку на «массив» наборов смежности, каждый набор должен представлять собой STL-последовательность с input-итератором;
• (ввод) индексы начальной и конечной (целевой) вершин искомого пути;
• (ввод) количество вершин графа;
• (ввод) эвристика, реализованная как бинарный функтор, принимающий два индекса вершин графа и возвращающий оценку расстояния;
• (ввод, опционально) политика демонстрации работы алгоритма, предназначенная для визуализации (подробнее в AV-2).

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

Основное отличие алгоритма поиска A* от алгоритма Дейкстры состоит в том, что при выборе ещё не пройденных вершин приоритет отдаётся тем вершинам, которые минимизируют сумму веса уже известного на момент пути (хранится в массиве gscore) и оценки остатка пути до целевой вершины. Эти суммы хранятся в массиве fscore, который используется компаратором ByArrayComparator при сравнении индексов вершин, помещаемых в объект openset (имеющий тип std::set<unsigned, ByArrayComparator<(…)>>).

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

Эта очередь называется «открытым множеством» (openset). Вершины, извлечённые из открытого множества, попадают в «закрытое множество» (closedset), после чего они уже не могут попасть в открытое множество.

Известно, что если эвристика даёт оценку кратчайшего пути снизу ( такая эвристика называется «допустимой» ), то алгоритм поиска A* находит кратчайший путь. В частности, эвристика может всегда возвращать 0, в этом случае алгоритм А* будет эквивалентен алгоритму Дейкстры с остановом при достижении целевой вершины.

С другой стороны, алгоритм А* позволяет ускорить процесс поиска с возможной потерей оптимальности результирующего пути. Известно, что если эвристика даёт оценку кратчайшего пути, которая не больше, чем в q раз превосходит вес реального кратчайшего пути, то алгоритм А* находит путь веса не более, чем в q раз большего, чем кратчайший путь (субоптимальное решение).

Если между заданными вершинами в графе существует хотя бы один путь, то алгоритм А* всегда (независимо от свойств эвристики) находит некоторый путь, так как является обобщением алгоритма поиска в ширину.

Введение

Рассматривается ориентированный граф («сеть»), в котором есть две выделенные вершины: исток s и сток t. Исток не имеет входящих рёбер, сток — исходящих рёбер. Кроме того, если в сети существует ребро (u, v), то не существует ребра (v, u). Для каждого ребра (u, v) задана пропускная способность («capacity»), обозначаемая обычно c(u, v) или A(u, v). Ниже она задаётся матрицей, так же как и сам граф: пропускная способность несуществующих рёбер равна нулю.

Требуется найти максимальный поток F, который может пропустить сеть в силу заданных пропускных способностей. Поток в сети задаётся матрицей потоков, проходящих по рёбрам. Должно выполняться условие F(u, v) ≤ A(u, v).

Алгоритмы

Известно два основных класса алгоритмов, решающих задачу максимизации потока на сети:

1. Класс алгоритмов Форда-Фалкерсона (Ford-Fulkerson algorithm), строящих дополняющие цепи.
2. Алгоритмы проталкивания предпотока (preflow pushing algorithm, push-relabel algorithm), пытающихся максимально заполнить сеть, оперируя избытком «жидкости» в вершинах.

Алгоритмы Форда-Фалкерсона

Алгоритмы основаны на теореме Форда-Фалкерсона. Общий принцип работы:

1. Устанавливается F(u, v) = 0, для всех пар u, v.
2. Пока можно построить новую дополняющую цепь на остаточном графе, дополняем F(u, v) в силу построенной цепи.

Остаточный граф (residual graph) — граф с пропускными способностями рёбер равными A(u, v) — F(u, v), если A(u, v) > 0 (прямая дуга), или F(v, u), если A(u, v) = 0 (обратная дуга).

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

Разные реализации общей идеи по-разному решают вопрос поиска очередной дополняющей цепи. Существует два классических алгоритма 1970-х: алгоритм Эдмондса-Карпа (реализован в BGL) сложности O(N M²) ≤ O(N⁵) и алгоритм Ефима Диница сложности O(N² M) ≤ O(N⁴). К новым алгоритмам этого семейства можно отнести алгоритм Бойкова-Колмогорова (описание из BGL, статья).

Алгоритмы проталкивания предпотока

В 1980-х появилось новое семейство алгоритмов построения максимального потока типа, отличного от ранее известных алгоритмов Форда-Фалкерсона. В данном контексте будем называть F предпотоком. Для предпотока выполняются следующие условия: F(u, v) ≤ A(u, v) и F(u, v) = —F(v, u).

Пусть для каждой вершины v задана высота h[v]  ≥ 0 и избыток e[v] ≥ 0. Вершины, в которых избыток больше нуля, называются активными. Для любых вершин u, v, кроме стока и истока, должно быть выполнено условие: если (u, v) принадлежит остаточному графу, то h[u] ≤ h[v] + 1. Обычно полагают h[s] = N, h[t] = 0. Избыток в вершине равен разностью между суммой потоков на исходящих рёбрах и суммой потоков на входящих рёбрах.

Основная идея алгоритма состоит в первоначальном максимальном заполнении исходящих рёбер истока и «проталкивании» избытка из активных вершин по рёбрам остаточного графа в вершины, имеющими высоту, меньшую на 1. Если весь избыток вывести не удалось, то высота вершины увеличивается. Алгоритм останавливается, когда не остаётся активных вершин.

Базовая версия алгоритма (реализация на e-maxx.ru) без упорядочивания активных вершин имеет оценку сложности O(N² M) ≤ O(N⁴). Вариант, «прогоняющий» вершины через очередь имеет оценку сложности O(N³). Вариант, поднимающий в начало очереди активных вершин вершину, в случае увеличения её высоты (реализация на e-maxx.ru, описание реализации BGL), имеет оценку O(N² sqrt(M)) ≤ O(N³).

Реализация

Была написана реализация алгоритмов Эдмондса-Карпа и проталкивания предпотока с переупорядочиванием поднятых вершин (maxFlowPushRelabel) и с обработкой активных вершин в порядке очереди («базовый», maxFlowPushing).

Алгоритмы реализованы как функции-шаблоны и имеют параметр шаблона WeightMatrix, задающий тип матрицы пропускных способностей.

Кроме того, алгоритм Форда-Фалкерсона принимает тип-параметр Augmentor, который считается классом, определяющим статическую функцию augment, строящую следующую дополняющую цепь. Имеется одна реализация: EdmondsKarp, строящая цепь поиском в ширину. Таким образом, функция maxFlowFordFulkerson<EdmondsKarp> реализует алгоритм Эдмондса-Карпа.

Аналогично, алгоритмы проталкивания предпотока принимают тип-параметр Heights, который считается классом, определяющим статическую функцию heights, инициализирующую массив высот вершин. Определён один такой класс: HeightsBFS, который вычисляет высоты поиском в ширину в обратном направлении (против направления рёбер), начиная со стока. Впрочем, эксперименты не обнаружили существенного влияния способа инициализации высот на скорость работы алгоритмов.

Задания

1. Прочитать и понять код, почему первое выводимое число всегда 1, а последнее — 0?
2. Каким ещё образом можно реализовать выборку наивысшей активной вершины?
3. Можно ли объединить код maxFlowPushing и maxFlowPushRelabel в одну функцию-шаблон?

Цель

Рассмотреть задачу поиска циклов: один раз проходящих по каждому ребру («эйлеров») и один раз проходящих через каждую вершину («гамильтонов»).

Код

Для удобства будем считать, что часть кода из поста «Графы-2» до комментария

// тесты

выделена в отдельный заголовочный файл «Graph2.h».

1. Функция-шаблон findEulerLoop<AdjVec, OutIt> реализует алгоритм, строящий некоторый эйлеров цикл путём отбрасывания рёбер. Принимаемый граф представлен вектором наборов соседей AdjVec (первый параметр; например, в качестве него подходит объект std::vector<std::set<unsigned>>, тж. см. «Графы-1» ), результат в виде последовательности вершин (отождествляемых с индексами в объекте AdjVec) возвращается через объект итератора вывода OutIt (второй параметр).

Для корректной работы алгоритма требуется, чтобы исходный граф был связным, неориентированным,  с чётными степенями всех вершин. Пример использования этой функции дан в TestCase3::testEulerLoop.

2. Класс-шаблон HamiltonianLoopEnumerator<AdjVec> реализует перебор всех гамильтоновых циклов в связном неориентированном графе, заданном вектором наборов соседей (AdjVec, аналогично функции findEulerLoop). Конструктор осуществляет «привязку» к исходному графу и инициализацию внутренних структур данных.

Функция-член next() находит следующий (или первый, если это первый вызов next() после создания объекта HamiltonianLoopEnumerator<AdjVec>) цикл, если таковой существует (в этом случае возвращает true). Если же искомый цикл не существует, то функция возвращает false. Алгоритм поиска основан на рекурсивном переборе с возвратом, переменная k отражает глубину рекурсии — количество вершин в строимой цепи (ещё не замкнутой в цикл).

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

Для удобства восприятия часть кода вынесена в закрытые функции rollback() (возврат с уменьшением k) и nextK() (увеличение k с инициализаций соответствующих структур данных).

3. Класс-шаблон MinimalHamiltonianLoop<AdjVec> использует класс HamiltonianLoopEnumerator<AdjVec> для перебора гамильтоновых циклов с выбором среди них цикла минимального веса (задаётся матрицей весов). Для запуска перебора всех циклов предназначена функция-член-шаблон run(const WeightMatrix &W), где W(i, j) задаёт вес ребра (i, j).

Есть также «ограниченный» вариант run(const WeightMatrix &W, std::size_t maxloops), перебирающий не больше, чем maxloops, гамильтоновых циклов. Её можно использовать, чтобы перебирать все циклы «пачками». После каждого вызова ограниченного варианта run, текущий цикл (доступный через диапазон итераторов begin(), end()) будет минимальным среди всех циклов, перебранных после создания объекта MinimalHamiltonianLoop<AdjVec>.

Итак, код целиком: codepad.org, paste.org.

Задания и вопросы

1. Прочитать и понять приведённый код. Почему последние два цикла, выведенные на экран, совпадают?
2. Что общего у эйлерова и гамильтонова циклов? Пусть дан граф G = (V, E), построим его рёберный граф Г = (V’, E’), такой, что |E| = |V’|, существует взаимно-однозначное отображение p из V’ в E, и E’ = {(a, b) из V’ x V’ | рёбра pa и pb инцидентны в G}. Написать функцию, строящую рёберный граф заданного графа. Реализуема ли обратная операция?
3. Какие существуют методы оптимизации поиска гамильтонова цикла минимального веса?

Цель

Понять, что такое представление графа, называемое «списки смежности». Научиться его реализовывать на C++, использовать его для организации поиска.

Код

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

Пока будем считать, что вершина – это просто номер. Список смежности вершины находится в массиве по соответствующему индексу.

/// naive Adjacency Lists implementation
class AdjacencyLists
{
public:
  /// vertex representation, just its index for now
  typedef std::size_t Vertex;

Принято называть набор соседей «списком смежности», однако нетрудно видеть, что в нашем случае удобнее использовать библиотечный класс set, чем list. Собственно «представление» есть массив (vector) «списков смежности».

private:
  typedef std::set<Vertex> Adjacency;
  typedef std::vector<Adjacency> Repr;
  Repr repr; // the representation itself

Элементарный конструктор, позволяющий сразу задать количество вершин в графе (по умолчанию –  ноль).

public:
  /// acquire space for the given amount of vertices
  explicit AdjacencyLists(std::size_t vertices_ = 0u)
    : repr(vertices_) {}

Далее идут простейшие функции, позволяющие управлять представлением. Например, проверка графа на пустоту и запрос количества вершин в графе:

  /// tests if there are any vertices
  bool empty() const
  {
    return repr.empty();
  }

  /// tell us, how many vertices are there
  std::size_t vertices() const
  {
    return repr.size();
  }

Нерекурсивный (использует стандартный класс queue) поиск в ширину. Начинает с вершины start. Для каждой найденной вершины вызывает функтор visit.

  /// breadth-first search
  /**
   * @param visit the functor to be called for each vertex
   * @param start the vertex to start search from
   * @return how many vertices have been visited 
   */
  template<class Visitor>
  std::size_t bfs(Visitor visit, Vertex start) const
  {
    if (vertices() <= start)
      return 0u;

    std::vector<bool> visited(vertices(), false);
    std::queue<Vertex> Q;
    Q.push(start);

    std::size_t res = 1u;
    visit(start);
    visited[start] = true;

    while (!Q.empty())
    {
      const Vertex v = Q.front();
      Q.pop();
      for (const Vertex w : repr[v]) // C++11
      {
        if (!visited[w])
        {
          Q.push(w);
          visit(w);
          visited[w] = true;
          ++res;
        }
      }
    }

    return res;
  }
};

Возможный код небольшого теста поиска в ширину. Должны быть
последовательно выведены числа от 0 до 12.

template <class T>
void println(const T &what)
{
  std::cout << what << "\n";
}

void test1()
{
  // 12 vertices
  Graphs::AdjacencyLists G(12);

  // add edges
  G.biconnect(0, 1);
  G.biconnect(0, 2);
  G.biconnect(0, 3);
  G.biconnect(1, 4);
  G.biconnect(1, 5);
  G.biconnect(3, 6);
  G.biconnect(3, 7);
  G.biconnect(4, 8);
  G.biconnect(4, 9);
  G.biconnect(6, 10);
  G.biconnect(6, 11);

  // should result into numbers 0 … 12
  std::cout << G.bfs(println<unsigned>, 0);
}

Этот же код целиком: codepad.

Задания

1. Прочитать и понять приведённый код. Почему в конце выводится число 12?
2. Реализовать поиск в глубину аналогично реализованному поиску в ширину bfs.
3. Как использовать bfs, чтобы определить связность графа?
4. Написать код, использующий bfs для выделения компонент связности.
5. Найти недостатки приведённой выше реализации.
6. Написать тест на скорость работы, позволяющий сравнить std::set и std::unordered_set (C++0x) или boost::unordered_set в качестве реализации «списка смежности».