Недавно я освежил свои знания в области CS. В частности, я много думал о графиках. И одна вещь, которая меня всегда беспокоила, - это относительная нехватка ресурсов для изучения их в Ruby. В результате, пока я работаю над различными проблемами, связанными с графами, в Ruby, я решил задокументировать процесс в этом блоге в надежде, что это может быть полезно другим.
В этой первой части моей серии статей о графах в Ruby я просто представлю пару методов представления графов, реализованных в Ruby. Эти реализации являются строительными блоками, которые нам понадобятся, чтобы начать работу над решением проблем в Части 2. Давайте сразу приступим.
Представление # 1: Матрица смежности
Что такое матрица смежности? Что ж, допустим, у нас есть граф с N вершинами. Идея матрицы смежности заключается в том, что мы храним матрицу NxN, где каждый элемент (i,j) равен 0, когда между вершиной i и вершиной j нет ребра, и 1, когда такое ребро есть. Это, вероятно, самый простой способ представить граф в коде. Я хочу немного поговорить о плюсах и минусах этого представления, но сначала я расскажу, что я придумал для реализации на Ruby.
Я начал с выбора базового интерфейса для моего графика. Я хотел иметь возможность выполнять следующие операции:
add_edge- Добавить ребро к графуremove_edge- Удалить ребро из графаedge?(i, j)- Проверить, есть ли ребро, соединяющее две вершины,iиjto_s- Довольно распечатать содержимое графикаelement(i, j)- получить элемент на(i, j)row(i)- получитьiстроку
Я также хотел поддержать реализации undirected и directed и проверить наличие OutOfBounds ошибок.
Давайте посмотрим на некоторые тесты RSpec, которые я создал, чтобы убедиться, что реализация работает правильно. Во-первых, для создания:
По сути, вышеизложенное гарантирует, что мы можем создать пустой MatrixGraph со всеми вершинами, инициализированными равными нулю.
Теперь о тестах по добавлению и удалению краев:
Это базовая функциональность, которую я надеялся получить от моей первоначальной реализации матрицы смежности. Вот код, который у меня получился:
Как видите, сам класс чрезвычайно прост. Он создает граф с заданным количеством вершин, позволяет добавлять и удалять ребра. Он позволяет вам проверить, существуют ли ребра, получить определенные элементы и строки, а также распечатать текущий граф.
Обратите внимание, что я использовал Шаблон стратегии, чтобы разделить разницу в логике между неориентированными и ориентированными графами:
Как видите, этот класс воплощает идею о том, что когда мы добавляем или удаляем ребро, мы также должны добавлять или удалять его соответствующее ребро. Например, если вы делаете graph.add_edge(1, 2), то в неориентированном графе вы также должны делать graph.add_edge(2, 1), поскольку наличие первого подразумевает, что второй также должен быть включен.
Вот соответствующий класс для ориентированных графов, где этот дополнительный шаг не требуется:
Я также использовал метод with_bounds_check, чтобы убедиться, что мы выдаем ошибку, когда любой из наших методов вызывается с недопустимыми индексами вершин. Его реализация выглядит так:
Итак, это наша реализация. Это действительно очень просто, но это все, что вам нужно для представления графа в Ruby.
Визуализация наших графиков
Визуализировать график, основанный исключительно на коде, может быть немного сложно, поэтому я также написал небольшой скрипт на Ruby с использованием Shoes для печати геометрического представления графика на экране компьютера.
Давайте посмотрим на пример того, как мы можем просмотреть одно представление графа, созданного с помощью моего MatrixGraph класса.
Этого однострочника достаточно для создания простого изображения:
Не очень интересно. Но это наш график в его нынешнем виде. Это просто набор из девяти вершин без ребер между ними. А теперь давайте попробуем добавить ребро:
Итак, теперь мы видим, что между первыми двумя вершинами добавлено ребро. Кстати, вот результат graph.to_s (реализация на основе массива):
Как видите, элементы в (0, 1) и (1, 0) установлены в 1, что представляет край, показанный выше.
Добавим еще несколько ребер:
И вот итоговый график:
Плюсы и минусы матрицы смежности
Подход MatrixGraph имеет некоторые преимущества. Во-первых, проверка наличия ребра чрезвычайно проста и выполняется за O(1) время, поскольку все, что вам нужно сделать, это получить elements[i][j]. Кроме того, когда у нас есть плотные графы (где у данного элемента есть ребра для значительной части всех других элементов), это более эффективно, чем другие представления. Операция добавления новых ребер также является простой операцией с постоянным временем.
К сожалению, у подхода с использованием матрицы смежности также есть некоторые недостатки. А именно, имея дело с разреженными графами (такими как показанные выше), мы тратим много памяти, сохраняя нули для каждого возможного местоположения края, когда их всего несколько. И если вы хотите пройти по графу и найти все ребра, эта операция будет O(N^2), что особенно прискорбно, когда у нас есть разреженный граф, где большая часть этого обхода бесполезна.
Есть еще один важный способ представления графиков, который мы сейчас рассмотрим. Это называется Adjacency List.
Представление графа # 2: список смежности
Основная идея Списка смежности заключается в том, что вместо массива массивов NxN у нас есть массив связанных списков. Таким образом, когда у нас есть разреженный граф, общий объем используемой памяти может быть меньше, чем с матрицами смежности (O(N) вместо O(N^2)).
Чтобы посмотреть, как представить эту структуру в Ruby, нам сначала понадобится реализация связанного списка. Итак, я пошел дальше и начал с создания класса для этого.
Прежде всего, вот спецификации, управляющие этим классом ListNode:
По сути, нам нужно иметь возможность добавлять и удалять элементы, печатать элементы в списке и проверять, содержится ли данный элемент в списке.
Вот как это выглядит на самом деле:
Я считаю, что эта реализация довольно проста, поэтому теперь давайте познакомимся с представлением графа в виде списка смежности, в котором используется указанный выше класс. Внешний интерфейс практически такой же (хотя и немного уменьшен), что и интерфейс матрицы смежности, поэтому я не буду показывать тестовые примеры, но вот сам класс:
И снова мы получаем крошечный компактный класс, очень похожий на предыдущий. Основное отличие состоит в том, что мы используем массив связанных списков под капотом. При взгляде на код это не слишком ясно, но это может иметь значение для нашей сложности во время выполнения и в пространстве.
Список смежности: плюсы и минусы
Давайте еще раз подумаем о том, как переход на связанные списки меняет поведение нашего класса. Самым большим преимуществом является тот факт, что теперь, когда у нас есть разреженный граф (например, граф дружбы, дорожная сеть и т. Д.), Мы можем сэкономить много памяти, сохраняя значение в списке только при наличии ребра и предполагая, что это не так. иначе не существует. Это может иметь огромное значение в скорости, когда мы фактически начнем использовать эти графики для запуска алгоритмов. С Матрицей смежности у нас не было выбора, кроме как всегда хранить O(N^2) элементов. Теперь со списком смежности мы часто можем хранить O(N) элементов, которые могут иметь значение, будет ли алгоритм медленным или быстрым.
Однако у этого подхода есть и некоторые недостатки. Во-первых, добавление нового ребра требует обхода связанного списка для данной вершины и, следовательно, составляет O(N) вместо O(1), как было раньше. Проверка включения данного ребра также больше невозможна в постоянном времени, так как мы снова должны пройти по связанному списку и найти данную вершину.
Несмотря на эти недостатки, списки смежности превосходят матрицы смежности в большинстве приложений. Поэтому в следующих статьях этой серии я обычно буду использовать представление списка смежности по умолчанию, если нет особой причины не делать этого. И это подводит итог реализации ruby-графов, которые я буду использовать, продолжая изучать графы и концепции CS в ruby. Это ссылка на весь исходный код этого поста, спасибо за чтение!
