Algorithm of the day
Почитал немного just for fun про то, как вычислять в больших графах достижимость; некоторые идеи очень понравились.
Постановка задачи: Есть очень большой граф (миллионы-миллиарды вершин и рёбер); надо научиться быстро отвечать на вопросы
1) достижима ли вершина А из Б?
2) какие вершины достижимы из А?
В обоих случаях первым шагом, если граф циклический, можно посчитать компоненты сильной связности, и он станет ациклическим. Далее граф везде ациклический.
Начнём с задачи 2.
Самый простой способ - просто при запросе сделать BFS. Недостаток - нужно некоторое количество памяти на маркировку вершин; требует заметного количества IO, когда граф лежит не в памяти, а где-то.
Ещё один простой способ - заранее посчитать транзитивное замыкание графа - для каждой вершины запомнить, кто из неё достижим. Отлично ложится на хранение на диске или в какой-нибудь базе; оба запроса работают быстро. Недостаток, понятное дело - транзитивное замыкание может быть очень большим. Но у некоторых графов оно не очень большое, и это может отлично работать.
Есть разные способы сжатия транзитивного замыкания (transitive closure compression). Мне больше всего понравился такой (называется Interval Labeling):
* Построим остовное дерево графа - например, дерево поиска в ширину.
* Разметим каждую вершину дерева индексом входа и выхода в порядке in-order обхода, и положим на диск табличку для доставания вершины по индексу.
* Теперь для любой вершины исходного графа её транзитивное замыкание можно закодировать не просто как список достижимых вершин, а как список достижимых поддеревьев дерева обхода (если достижим корень, то достижимо и всё поддерево). Поддеревьев намного меньше, особенно если в графе много "узких мест".
* Пометим каждую вершину списком достижимых поддеревьев: каждое поддерево будем кодировать как пару (iIn, iOut) для его корня (почему не просто id корня - см. далее).
* Вопрос 1 "есть ли путь A..B" решается так: лежит ли интервал (iIn_B, iOut_B) в одном из интервалов, которым помечена вершина А?
* Вопрос 2 "кто достижим из А" решается так: перечисляем все индексы во всех интервалах, которыми помечена А; всё.
Единственный вопрос остаётся - как выполнить шаг 3 эффективно. Ответ простой: после того, как дерево построено, обойдём исходный DAG снизу вверх в порядке топологической сортировки, и построим метки по индукции: intervals(A) = union {intervals(B) | B <- out(A)} (union берётся с удалением избыточных интервалов).
Очень полезная фишка interval labeling в том, что полученные структуры данных тривиально хранятся и запрашиваются в SQL БД.
Кроме того, если граф уж очень большой, то всё описанное неплохо ложится на MapReduce, Pregel, вот это всё.
Для решения сугубо вопроса 1 есть ещё один интересный класс алгоритмов - "2-hop labeling".
Смысл в следующем: для каждой вершины каким-то образом найдём "остовные (backbone) исходящие" и "остовные входящие" вершины - bOut(A), bIn(A). Они необязательно должны быть прямыми соседями А - имеется в виду достижимость.
Их свойство должно быть таким: "есть путь A .. B" равносильно "bOut(A) пересекает bIn(B)".
В вырожденном случае можно взять за них соответственно прямое и обратное транзитивное замыкание, но цель - уменьшить размер этих меток bIn, bOut.
Минимизировать размер меток - NP-полная задача; и за 10 лет с придумывания подхода пока ещё так и не придумали очень красивых, очень простых или очень быстрых алгоритмов поиска таких меток, но алгоритмов, неплохо работающих на сотнях тысяч или даже миллионах вершин - полно.
Исходная статья про interval labeling
Исходная статья про 2-hop labeling
SCARAB: мета-подход к ускорению алгоритмов reachability
Одна из современных статей на тему ускорения 2-hop
Чумовые слайды про похожий на 2-hop алгоритм поиска кратчайших путей на дорожных сетях из MSR
Постановка задачи: Есть очень большой граф (миллионы-миллиарды вершин и рёбер); надо научиться быстро отвечать на вопросы
1) достижима ли вершина А из Б?
2) какие вершины достижимы из А?
В обоих случаях первым шагом, если граф циклический, можно посчитать компоненты сильной связности, и он станет ациклическим. Далее граф везде ациклический.
Начнём с задачи 2.
Самый простой способ - просто при запросе сделать BFS. Недостаток - нужно некоторое количество памяти на маркировку вершин; требует заметного количества IO, когда граф лежит не в памяти, а где-то.
Ещё один простой способ - заранее посчитать транзитивное замыкание графа - для каждой вершины запомнить, кто из неё достижим. Отлично ложится на хранение на диске или в какой-нибудь базе; оба запроса работают быстро. Недостаток, понятное дело - транзитивное замыкание может быть очень большим. Но у некоторых графов оно не очень большое, и это может отлично работать.
Есть разные способы сжатия транзитивного замыкания (transitive closure compression). Мне больше всего понравился такой (называется Interval Labeling):
* Построим остовное дерево графа - например, дерево поиска в ширину.
* Разметим каждую вершину дерева индексом входа и выхода в порядке in-order обхода, и положим на диск табличку для доставания вершины по индексу.
* Теперь для любой вершины исходного графа её транзитивное замыкание можно закодировать не просто как список достижимых вершин, а как список достижимых поддеревьев дерева обхода (если достижим корень, то достижимо и всё поддерево). Поддеревьев намного меньше, особенно если в графе много "узких мест".
* Пометим каждую вершину списком достижимых поддеревьев: каждое поддерево будем кодировать как пару (iIn, iOut) для его корня (почему не просто id корня - см. далее).
* Вопрос 1 "есть ли путь A..B" решается так: лежит ли интервал (iIn_B, iOut_B) в одном из интервалов, которым помечена вершина А?
* Вопрос 2 "кто достижим из А" решается так: перечисляем все индексы во всех интервалах, которыми помечена А; всё.
Единственный вопрос остаётся - как выполнить шаг 3 эффективно. Ответ простой: после того, как дерево построено, обойдём исходный DAG снизу вверх в порядке топологической сортировки, и построим метки по индукции: intervals(A) = union {intervals(B) | B <- out(A)} (union берётся с удалением избыточных интервалов).
Очень полезная фишка interval labeling в том, что полученные структуры данных тривиально хранятся и запрашиваются в SQL БД.
Кроме того, если граф уж очень большой, то всё описанное неплохо ложится на MapReduce, Pregel, вот это всё.
Для решения сугубо вопроса 1 есть ещё один интересный класс алгоритмов - "2-hop labeling".
Смысл в следующем: для каждой вершины каким-то образом найдём "остовные (backbone) исходящие" и "остовные входящие" вершины - bOut(A), bIn(A). Они необязательно должны быть прямыми соседями А - имеется в виду достижимость.
Их свойство должно быть таким: "есть путь A .. B" равносильно "bOut(A) пересекает bIn(B)".
В вырожденном случае можно взять за них соответственно прямое и обратное транзитивное замыкание, но цель - уменьшить размер этих меток bIn, bOut.
Минимизировать размер меток - NP-полная задача; и за 10 лет с придумывания подхода пока ещё так и не придумали очень красивых, очень простых или очень быстрых алгоритмов поиска таких меток, но алгоритмов, неплохо работающих на сотнях тысяч или даже миллионах вершин - полно.
Исходная статья про interval labeling
Исходная статья про 2-hop labeling
SCARAB: мета-подход к ускорению алгоритмов reachability
Одна из современных статей на тему ускорения 2-hop
Чумовые слайды про похожий на 2-hop алгоритм поиска кратчайших путей на дорожных сетях из MSR