Monthly Archives: Март 2011

Графы-3: эйлеровы и гамильтоновы циклы

Цель

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

Код

Для удобства будем считать, что часть кода из поста «Графы-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. Какие существуют методы оптимизации поиска гамильтонова цикла минимального веса?

Графы-2: минимизация на матрице весов

Цель

Рассмотреть работу с графом, представленном матрицей весов рёбер, на примере алгоритмов построения минимального остова и нахождения кратчайших путей.

Код

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

  1. Индексы/количества вершин. Используется тип unsigned.
  2. Матрица весов/расстояний (параметр шаблона WeightMatrix), доступ к элементам осуществляется с помощью operator()(unsigned, unsigned), иными словами, a(i, j) — ij-элемент матрицы a. Для простоты полагается представление весов в виде double.
  3. Матрица предшественников (параметр шаблона PreviousMatrix), например, Pr. Тогда Pr(i, j) хранит индекс вершины, предшествующей j на пути из вершины i. Таким образом, элементы имеют тип unsigned.
  4. Массив («вектор») весов/расстояний (параметр шаблона WeightVector), доступ к элементам осуществляется с помощью operator[](unsigned), иными словами, d[i] — i-элемент массива d.
  5. Массив предшественников (параметр шаблона Previous). Аналог матрицы предшественников и массива весов.

По ссылке приведён код, где реализованы алгоритмы Ярника-Прима-Дейкстры построения минимального остова («minimal spanning tree»), Дейкстры поиска кратчайших путей от одной вершины до всех остальных, Флойда-Уоршелла поиска кратчайших путей между всеми парами вершин графа, а также приведён пример их использования.

Дополнительная ссылка на код.

Тест

Кроме того, данный код включает тест времени выполнения приведённых алгоритмов, который можно использовать, например, для тестирования различных реализаций матриц. Его точность не очень высока, однако результаты могут представлять определённый интерес. Далее приведён усреднённый (на 4 запусках) результат для двух машин (компилятор Visual C++ 2010):

  1. AMD Phenom2 955 @ 3.2GHz, 880G, 2x 2Gb DDR3-1333 9-9-9-24 — 512Mb IGP UMA.
  2. Intel Celeron U3400 @ 1.07GHz, H55, 4Gb DDR3-800.
Вариант Остов Дейкстра Флойд
AMD 32-bit 23.054с 23.167с 17.873с
AMD 64-bit 21.239с 20.137с 12.822с
Intel 32-bit 34.538с 68.543с 44.223с
Intel 64-bit 28.860с 62.888с 29.882с

Задания

  1. Прочитать и понять приведённый код. Из шести выводимых программой чисел три выводятся без поясняющего текста. Что означают эти три числа? Почему два последних совпадают?
  2. Реализовать алгоритм построения минимального остова Борувки-Краскала.
  3. Модифицировать алгоритм Флойда-Уоршелла для построения матрицы достижимости из матрицы смежности.
  4. Подумать об оптимизации рассмотренных алгоритмов для работы с разряжёнными графами. Разряжёнными называют графы, у которых число рёбер сопоставимо с числом вершин (например, планарные или графы с ограниченной степенью вершин).

Графы-1: списки смежности, поиск в ширину

Цель

Понять, что такое представление графа, называемое «списки смежности». Научиться его реализовывать на 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 в качестве реализации «списка смежности».