Как хранить граф

Ниже — улицы центра Алматы в виде матрицы смежности: строка и столбец — перекрёсток, точка — участок улицы между двумя перекрёстками. Перекрёстков 7909, клеток в матрице — 62 552 281, а точек — 20 778: заполнено 0,03 % матрицы. Переключите порядок вершин: от него зависит, где лягут эти точки, хотя граф один и тот же.

В случайном порядке точки рассыпаны по всей матрице. В порядке файла они жмутся к диагонали: OpenStreetMap записывает перекрёстки одной улицы рядом. Если упорядочить перекрёстки вдоль кривой Гильберта, которая обходит карту квадратами, точки сходятся в узкую полосу: соседние на карте перекрёстки получают близкие номера. Для компьютера это не просто красиво — соседи вершины оказываются рядом и в памяти, и обход графа реже промахивается мимо кэша.

Идея

Граф — это вершины и рёбра, но программе нужен не рисунок, а ответы на вопросы: кто соседи вершины v, есть ли ребро между u и v, перебрать все рёбра. Каждая запись графа делает одни вопросы дешёвыми, а другие — дорогими, и тратит на это разную память.

Пусть вершин n, рёбер m. Вот четыре главные записи на маленьком куске той же карты — четырнадцати перекрёстках у площади Республики. Нажимайте на перекрёстки:

• Матрица смежности — таблица n × n, единица там, где есть ребро. «Есть ли ребро u–v» — одно обращение. Но перебрать соседей вершины — значит пройти всю её строку из n клеток, а памяти нужно n² клеток при любом числе рёбер.
• Списки смежности — у каждой вершины список соседей. Перебор соседей стоит столько, сколько их есть, памяти — O(n + m). Проверка ребра — пробежать список меньшей вершины.
• Массив рёбер — просто пары (u, v), как граф лежит в файле. Удобно перебирать все рёбра или сортировать их по весу, как в алгоритме Краскала. Найти соседей вершины — пройти все рёбра.
• CSR (compressed sparse row) — те же списки, но уложенные подряд в один массив targets, и массив start, где начинается список каждой вершины. Два плотных массива вместо тысяч маленьких списков: меньше памяти на служебные поля и соседи лежат подряд. Так хранят графы графовые библиотеки и сцены этого каталога, и так же устроены разреженные матрицы в численных библиотеках.

Код

Все четыре записи для улиц Алматы и сколько они занимают, если номер вершины — четыре байта:

Матрица битов — 7,8 мегабайта, матрица байтов — 62,5 мегабайта, а CSR — 115 килобайт: в 68 раз меньше даже битовой матрицы. Причина в том, что дороги — разреженный граф: у перекрёстка от одного до пяти соседей, и рёбер столько же, сколько вершин, а не n². Таковы почти все настоящие большие графы — дороги, ссылки, зависимости, друзья. Матрица выгодна только для плотных графов, где рёбер порядка n², и для алгоритмов, которые и так смотрят все пары вершин, как Флойд — Уоршелл.

Обход: квадрат против линии

Пройти граф в ширину по матрице — значит для каждой вершины просмотреть всю её строку: n² шагов, сколько бы ни было рёбер. По спискам или CSR — n + m. Замер на кусках того же графа растущего размера:

У матрицы наклон 2: удвоили граф — время выросло вчетверо, и на всех 7909 перекрёстках обход по матрице в Go в десятки раз дольше обхода по спискам. В Go CSR и списки идут почти вровень: граф ещё маловат, чтобы промахи кэша стали заметны, а CSR выигрывает на графах в миллионы вершин, где плотные массивы экономят и память, и походы в неё. В Python CSR, наоборот, почти вдвое медленнее: срез targets[a:b] копирует соседей в новый список, а у списков смежности он уже готов. Ещё один повод мерить на своём языке.

Что сколько стоит

Записи можно и нужно сочетать. Если часто спрашивают «есть ли ребро», а матрица не помещается, рядом со списками держат хеш-множество пар — так решается первая задача статьи. CSR неудобно менять, поэтому граф собирают в списках или массиве рёбер, а потом один раз превращают в CSR и дальше только читают.

И не забывайте про порядок вершин. Нумерация, при которой соседи на карте — соседи и в массиве, делает каждый обход быстрее, хотя асимптотика не меняется. Кривые, которые так нумеруют плоскость, — тема статьи о кривых Гильберта.

Задачи

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