Компоненты сильной связности
Также: Strongly connected components · SCC · алгоритм Тарьяна · Tarjan's algorithm · алгоритм Косараю · Kosaraju's algorithm · конденсация графа · condensation
Группы вершин ориентированного графа, внутри которых из любой можно дойти до любой. Один обход в глубину Тарьяна или два обхода Косараю находят их все за линейное время, а граф самих групп всегда без циклов. На улицах Алматы с односторонним движением это ответ на вопрос, откуда нельзя выехать, не нарушая правил.
В центре Алматы 10 640 участков улиц, и 2597 из них — с односторонним движением. Можно ли, не нарушая правил, доехать от любого перекрёстка до любого? Проверять пары по одной бессмысленно: перекрёстков почти восемь тысяч, пар — десятки миллионов. Ниже настоящий граф улиц из OpenStreetMap, и по нему идёт алгоритм Тарьяна: один обход в глубину делит перекрёстки на группы, внутри которых из любого места можно доехать до любого. Переключайте способ, каким направлены улицы, и нажмите на любой перекрёсток, чтобы увидеть, куда из него можно попасть и откуда — в него.
Город почти в порядке: 7873 перекрёстка из 7883 лежат в одной группе вместе с «остальным миром» за краем карты. Вне её — десять. Пять мест — ловушки: въехать по односторонней улице можно, а выехать по улицам нашего графа нельзя, как на бульваре Мусрепова. В два места, наоборот, нельзя попасть, только уехать — например, на улице Байсеитовой. Часть таких ловушек настоящая: выезд идёт через двор или служебный проезд, которых в графе нет. Часть, возможно, — ошибки разметки.
Теперь переключите на «Двусторонние — наугад»: пусть каждая двусторонняя улица станет односторонней в случайную сторону. Город рассыпается на 5190 групп. В главной остаётся 2110 перекрёстков — 26,8 %, а с площади Республики можно доехать лишь до трёх перекрёстков, хотя приехать на неё можно из 3092. И наконец «Все — по Роббинсу»: те же улицы, направленные с умом, — и город снова одна группа. Как это сделать и почему так получается не всегда, сказано в конце статьи.
Идея
Назовём вершины u и v ориентированного графа сильно связанными, если из u есть путь в v, а из v — в u. Это отношение эквивалентности: каждая вершина связана сама с собой, отношение симметрично, а пути можно склеивать. Поэтому вершины делятся на классы — компоненты сильной связности. Одиночная вершина, через которую не проходит ни один цикл, — тоже компонента, из одной вершины.
Нажмите на перекрёсток в сцене: синим показано всё, куда из него можно доехать, оранжевым — всё, откуда можно приехать в него. Его компонента — ровно пересечение: места, куда можно доехать и откуда можно вернуться. Так одну компоненту находят двумя обходами, а все — за V пар обходов, O(V(V + E)). Для города это сотни миллионов шагов. Алгоритмы этой статьи делают то же за один или два обхода всего графа.
Сожмите каждую компоненту в одну вершину и оставьте стрелку между компонентами, если между их вершинами было ребро. Получится граф без циклов: цикл через две компоненты склеил бы их в одну. У такого графа есть топологический порядок, истоки и стоки. Алгоритм Тарьяна находит компоненты одним поиском в глубину, причём в обратном топологическом порядке — первой закрывается компонента-сток, из которой никуда не уйти. Алгоритм Косараю делает два поиска: первый по графу, второй — по развёрнутым рёбрам.
Сжатый граф называют конденсацией. В сцене цвета так и устроены: зелёные компоненты — истоки, из них можно уехать, но в них нельзя попасть; красные — стоки; главная — серая. С конденсацией можно делать всё, что делают с графами без циклов: упорядочить, искать в ней самый длинный путь, считать по ней динамику. Многие задачи на графах с циклами так и решают: склеить компоненты и решить задачу на сжатом графе.
Тарьян: один обход
Поиск в глубину заходит в каждую компоненту через какую-то первую вершину — назовём её корнем компоненты. По лемме о белом пути все остальные вершины компоненты станут её потомками в дереве поиска: в момент входа в корень до каждой из них ведёт путь по ещё не тронутым вершинам. Значит, компонента — это поддерево корня без кусков, которые принадлежат компонентам, закрытым раньше. Остаётся узнать, какая вершина — корень.
Для этого Тарьян нумерует вершины в порядке входа и считает для каждой low — наименьший номер, до которого можно добраться из её поддерева, пройдя в конце одно ребро в вершину, которая ещё лежит в стеке. Стек здесь свой: вершина кладётся в него при входе и снимается только вместе со всей своей компонентой. Вершина v — корень, если low(v) равен её номеру: из её поддерева не подняться выше неё. Тогда всё, что лежит в стеке над v, вместе с v — её компонента.
Пройдите по шагам. Поиск начинает с A и идёт в B и C. Ребро C → A ведёт в вершину стека, и low(C) опускается до нуля — номера A. Дальше по C → H поиск идёт в H и G, и ребро G → H снова ведёт в стек: low(G) становится 3 — номером H. Из G выходят, low(G) не равен её номеру, и она остаётся в стеке. А у H low равен номеру: компонента {G H} закрыта первой. Это сток — из неё действительно никуда не уйти. Затем из B поиск идёт в D, E, F; ребро E → G ведёт в уже закрытую компоненту, и его пропускают: из закрытой компоненты в стек не вернуться. Второй закрывается {D E F}, последней — {A B C}, исток.
Почему корни угаданы верно
В момент выхода из вершины v равенство low(v) = номер(v) выполнено тогда и только тогда, когда v — корень своей компоненты, то есть первая её вершина, в которую вошёл поиск. В этот момент вершины стека выше v — ровно остальные вершины её компоненты.
Индукция по порядку выхода: для всех вершин, из которых вышли раньше, утверждение уже верно, так что компонента снимается со стека ровно при выходе из своего корня.
Пусть v не корень, и r — корень её компоненты; r — предок v. Из v есть путь в r. Он начинается в поддереве v и когда-то из него выходит — по ребру (x, y), где x в поддереве, а y нет. Вершина y лежит на пути к r, значит, в той же компоненте, а компонента ещё не закрыта — её корень r открыт. Поэтому y в стеке. Вошли в y раньше, чем в v: всё, во что поиск входит, пока v открыта, становится потомком v. Ребро (x, y) опускает low(x) ниже номера v, low передаётся от потомков к предкам, и low(v) < номер(v).
Пусть v — корень, но low(v) < номер(v): из вершины x её поддерева ребро ведёт в вершину y стека, в которую вошли раньше v. Компонента y не закрыта, значит, её корень ещё открыт, то есть он предок v. Тогда из y можно дойти до этого корня и по дереву — до v, а из v по дереву — до x и по ребру до y. Вершины y и v в одной компоненте, и y вошла раньше — v не корень. Противоречие. Наконец, над v в стеке лежат её потомки, чьи компоненты не закрыты. Корень такой компоненты открыт, а из открытых вершин в поддереве v осталась только сама v; если бы корень был выше v, v оказалась бы в его компоненте. Значит, все они в компоненте v.
Отсюда и порядок. Когда компоненту закрывают, все рёбра из неё ведут либо внутрь, либо в компоненты, закрытые раньше. Значит, каждая следующая компонента может вести только в предыдущие: Тарьян выдаёт конденсацию в обратном топологическом порядке. В сцене города первыми загораются стоки.
Косараю: два обхода
Второй способ проще объяснить и проще написать без ошибок. Первый проход — обычный поиск в глубину по всему графу, вершины записываются в порядке выхода. Второй проход идёт по развёрнутым рёбрам и берёт стартовые вершины в обратном порядке выхода: каждый запуск обходит ровно одну компоненту.
Если в конденсации есть стрелка из компоненты C в компоненту D, то самое позднее время выхода в C больше самого позднего времени выхода в D.
Если поиск раньше вошёл в C — в вершину c, — то в этот момент из c по нетронутым вершинам можно дойти до всех вершин C и D; по лемме о белом пути все они станут потомками c, и выход из c — позже всех. Если раньше вошёл в D, то из D в C пути нет — иначе компоненты слились бы, — и обход D закончится, не тронув C: вся C получит времена выхода позже.
Значит, вершина, из которой вышли последней, лежит в компоненте-истоке. В развёрнутом графе эта компонента — сток: развёрнутые рёбра из неё ведут только внутрь, и обход из неё соберёт ровно её. Вычеркнем её и повторим рассуждение для оставшихся. Косараю выдаёт компоненты в топологическом порядке, от истоков к стокам, — наоборот, чем Тарьян.
Код
Тарьян без рекурсии: свой стек кадров «вершина и итератор по её соседям», как в статье о поиске в глубину, и отдельный стек вершин незакрытых компонент. Демо — восемь перекрёстков из сцены выше.
Косараю на том же графе. Второй проход может быть и поиском в ширину, и любым обходом: порядок внутри компоненты ни на что не влияет.
А это город из сцены. Программа читает граф улиц с направлениями, считает компоненты, истоки и стоки при трёх способах направить улицы, проверяет, куда можно уехать с площади Республики, и строит направления по Роббинсу.
as mapped components: 9, the one with the world outside: 7873 crossings (99.9%) sources (can leave, cannot enter): 2, sinks (can enter, cannot leave): 5 deepest depth-first search: 1808 crossings on the stack
Сколько это стоит
Тарьян входит в каждую вершину один раз и смотрит каждое ребро один раз; каждая вершина один раз ложится в стек компонент и один раз из него снимается. Итого O(V + E) времени и O(V) памяти на номера, low и стеки. Косараю тоже линеен, но проходит граф дважды и хранит его второй раз — развёрнутым. Замер на случайных графах с тремя рёбрами на вершину:
Оба растут почти линейно. Наклон чуть больше единицы, потому что на больших графах соседи случайной вершины разбросаны по памяти и каждое обращение к ней дорожает. На ста тысячах вершин Косараю медленнее Тарьяна в 1,3 раза на Python, на трёхстах тысячах — в 2 раза на Go. На практике выбирают по удобству: Косараю короче и легче проверить, Тарьян экономнее и сразу даёт обратный топологический порядок.
Рекурсивный вариант на настоящих данных падает. Поиск в глубину по улицам Алматы уходит на глубину 1808 перекрёстков, а предел рекурсии в Python по умолчанию — тысяча вызовов. Либо поднимите предел, либо держите свой стек кадров, как в листингах; подробнее о глубине стека — в статье о поиске в глубину.
Когда все улицы можно сделать односторонними
В 1939 году Герберт Роббинс опубликовал теорему «с применением к задаче управления движением»: когда улицы города можно сделать односторонними так, чтобы из любого места по-прежнему можно было доехать до любого? Ясно, что не всегда: если улица — мост, единственная связь между двумя частями города, по ней нужно ездить в обе стороны. Оказывается, это единственное препятствие.
Связный граф без мостов можно ориентировать так, что из любой вершины можно дойти до любой.
Пустим поиск в глубину из любой вершины. Рёбра дерева направим от родителя к ребёнку, все остальные — от потомка к предку: в неориентированном графе поиск в глубину других рёбер не оставляет. По рёбрам дерева из корня можно дойти до всех. Осталось вернуться в корень из любой вершины v. Ребро от её родителя не мост, значит, из поддерева v есть ещё одно ребро наружу, и оно ведёт к предку v — иначе удаление ребра дерева отрезало бы поддерево. Из v можно спуститься по дереву к началу этого ребра и подняться по нему в вершину, в которую вошли раньше, чем в v. Повторяя, доберёмся до корня.
Так и устроен режим «Все — по Роббинсу». В графе центра Алматы мостов 1369, и 1090 из них — участки, ведущие в тупик: в тупик можно заехать только по одной улице, и она обязана остаться двусторонней. Остальные 9271 участок становятся односторонними, и все 7883 перекрёстка образуют одну компоненту. Это упражнение, а не план реформы: такой город был бы сильно связным, но пути в нём стали бы куда длиннее. Если часть улиц уже односторонние, работает обобщение Бёша и Тинделла 1980 года: в сильно связном городе любую двустороннюю улицу, которая не мост, можно сделать односторонней, не потеряв связности.
Где работает
Навигаторы. Маршрутизатор не должен ставить начало маршрута туда, откуда нет выезда. В исходном коде GraphHopper так и сказано: бывают «подсети», куда можно попасть из основной сети, но нельзя вернуться, — например, парковка, к которой ведёт единственная односторонняя дорога, ошибка разметки; чтобы их найти, нужно искать компоненты сильной связности на ориентированном графе, а не просто проверять связность. При импорте карты он помечает такие подсети как непроезжие, если они меньше порога, — по умолчанию 200.
2-SAT. Набор условий вида «a или b» на логических переменных превращается в граф следствий: «не a → b» и «не b → a». Условия выполнимы ровно тогда, когда ни одна переменная не лежит в одной компоненте со своим отрицанием, а порядок компонент даёт ответ. Подробно — в статье о 2-SAT и во второй задаче ниже, где так расставляют подписи на карте.
Циклы зависимостей. Петли в зависимостях пакетов Debian из статьи о топологической сортировке — компоненты сильной связности. Склеив их, получаем граф без циклов, и порядок установки снова существует.
Структура веба. В 2000 году Андрей Бродер и соавторы разобрали обход AltaVista мая 1999 года — 203 миллиона страниц и 1466 миллионов ссылок. Ядро, внутри которого со страницы на страницу можно дойти по ссылкам, оказалось неожиданно небольшим: около 56 миллионов страниц, 28 %. Ещё примерно по 44 миллиона страниц вели только в ядро, были достижимы только из ядра или не были связаны с ним ни так, ни так. Положение страницы определяли так же, как в нашей сцене: обходами по ссылкам вперёд и назад.
История
Линейный алгоритм для компонент сильной связности на поиске в глубину Роберт Тарьян опубликовал в 1972 году — в той же статье, что сделала поиск в глубину инструментом для алгоритмов; о ней — в статье о поиске в глубину. Алгоритм с двумя проходами С. Рао Косараю придумал в 1978 году, но не напечатал; Ахо, Хопкрофт и Ульман привели его в книге «Структуры данных и алгоритмы» (1983) со ссылкой на неопубликованную работу. Независимо тот же способ нашёл и в 1981 году опубликовал Миха Шарир, поэтому алгоритм называют ещё алгоритмом Косараю — Шарира.
Задачи
В первой задаче нужно сосчитать, сколько новых односторонних улиц сделают город сильно связным, — ответ дают истоки и стоки конденсации, и среди тестов улицы Алматы. Во второй подписи сёл Южной Моравии расставляют через 2-SAT, и при букве в 98 метров одна тройка сёл делает задачу невыполнимой.
Недостающие улицы Подписи сёл на картеДанные: Дороги Алматы © участники OpenStreetMap, ODbL Населённые пункты: GeoNames, CC BY 4.0