Как определить, приводит ли добавление ребра к ориентированному графу к циклу?
Я натолкнулся на графики ожидания, и мне интересно, существуют ли эффективные алгоритмы обнаружения, если добавление ребра в ориентированный граф приводит к циклу?
Рассматриваемые графы являются изменяемыми (они могут иметь добавленные или удаленные узлы и ребра). И мы не заинтересованы в том, чтобы на самом деле знать цикл оскорблений, достаточно просто знать, что он существует (чтобы предотвратить добавление непристойного ребра).
Конечно, можно было бы использовать алгоритм для вычисления сильно связанных компонентов (таких как Тарьяна), чтобы проверить, является ли новый граф ациклическим или нет, но запуск его снова каждый раз, когда добавляется ребро, кажется довольно неэффективным.
5 ответов
Если я правильно понял ваш вопрос, то новое ребро (u, v) вставляется только в том случае, если ранее не было пути от v к u (т. Е. Если (u, v) не создает цикл). Таким образом, ваш граф всегда является DAG (ориентированный ациклический граф). Использование алгоритма Тарьяна для обнаружения сильно связанных компонентов ( http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) в данном случае выглядит излишним. Перед вставкой (u, v) все, что вам нужно проверить, это наличие направленного пути от v к u, что можно сделать с помощью простой BFS/DFS.
Поэтому простейшим способом сделать это является следующее (n = |V|, m = |E|):
- Вставка (u,v): проверьте, существует ли путь от v к u (BFS/DFS). Временная сложность: O (м)
- Удаление ребер: просто удалите их с графика. Сложность времени: O(1)
Хотя для вставки (u, v) в худшем случае требуется время O(m), в вашей ситуации это, вероятно, довольно быстро. При выполнении BFS / DFS, начиная с v, чтобы проверить, достижима ли u, вы посещаете только те вершины, которые достижимы из v. Я предполагаю, что в ваших настройках граф довольно редок и что число вершин, достижимых другой, не высоко.
Однако, если вы хотите улучшить теоретическое время выполнения, вот несколько советов (в основном показывающих, что это будет не очень легко). Предположим, что мы стремимся за время (1) проверить, существует ли направленный путь от v до u. Ключевым словом в этом контексте является транзитивное замыкание группы обеспечения доступности баз данных (т. Е. Графа, содержащего ребро (u, v) тогда и только тогда, когда в группе обеспечения доступности есть направленный путь от u до v). К сожалению, поддерживать транзитивное замыкание в динамическом режиме не так просто. Есть несколько работ, рассматривающих эту проблему, и все документы, которые я нашел, были документами STOC или FOCS, что указывает на их большую вовлеченность. Самый новый (и самый быстрый) результат, который я нашел, находится в статье " Динамическое транзитивное замыкание с помощью динамической обратной матрицы", написанной Санковским ( http://dl.acm.org/citation.cfm?id=1033207).
Даже если вы хотите понять один из этих алгоритмов динамического транзитивного замыкания (или даже хотите реализовать его), они не дадут вам ускорения по следующей причине. Эти алгоритмы предназначены для ситуации, когда у вас много запросов на подключение (которые затем могут быть выполнены за O(1) раз) и только несколько изменений в графике. Тогда цель состоит в том, чтобы сделать эти изменения дешевле, чем пересчитывать транзитивное замыкание. Тем не менее, это обновление все еще медленнее, чем однократная проверка подключения. Таким образом, если вам нужно обновлять каждый запрос на подключение, лучше использовать простой подход, упомянутый выше.
Итак, почему я упоминаю этот подход поддержания транзитивного замыкания, если оно не соответствует вашим потребностям? Что ж, это показывает, что поиск алгоритма, потребляющего только O(1) времени запроса, вероятно, не приведет вас к решению быстрее, чем простое, использующее BFS/DFS. Вы можете попытаться получить время запроса, которое быстрее, чем O(m), но хуже, чем O(1), тогда как обновления также быстрее, чем O(m). Это очень интересная проблема, но для меня это звучит как очень амбициозная цель (поэтому, возможно, не тратьте слишком много времени на ее достижение...).
Как предположил Марк, можно использовать структуру данных, которая хранит связанные узлы. Лучше всего использовать булеву матрицу |V|x|V|, Значения могут быть инициализированы с помощью алгоритма Флойда-Варшалла. Что сделано в O(|V|^3),
Позволять T(i) быть набором вершин, которые имеют путь к вершине i, а также F(j) множество вершин, где существует путь от вершины j, Во-первых верны в iи второй истины в jКолонка
Добавление ребра (i,j) это простая операция. Если i а также j не был связан раньше, чем для каждого a от T(i) и каждый b от F(j) установить матричный элемент (a,b) к истине. Но операция не дешевая. В худшем случае это O(|V|^2), Это в случае направленной линии, и добавление ребра от конца к начальной вершине делает все вершины связанными со всеми остальными вершинами.
Удаление края (i,j) Это не так просто, но не более дорогая операция в худшем случае:-) Если есть путь от i в j после удаления края ничего не меняется. Это проверено с Dijkstra, менее чем O(|V|^2), Вершины, которые больше не связаны, (a,b):
aвT(i)-i-T(j),bвF(j)+j
Только T(j) изменяется с удалением края (i,j), так что это должно быть пересчитано. Это делается с помощью любого вида обхода графа (BFS, DFS), проходя в противоположном направлении от вершины j, Это сделано менее чем за O(|V|^2), Поскольку настройка матричного элемента в худшем случае снова O(|V|^2)эта операция имеет ту же сложность в худшем случае, что и добавление ребра.
Это проблема, с которой я недавно столкнулся в несколько иной ситуации (оптимальный порядок взаимозависимых инструкций компилятора).
Хотя я не могу улучшить теоретические границы O(n*n), после изрядного количества экспериментов и предположения об эвристике для моего случая (например, предполагая, что первоначальный порядок не был создан злонамеренно), следующий алгоритм был лучшим компромиссом с точки зрения производительности.
(В моем случае у меня был приемлемый «правосторонний сбой»: после того, как были добавлены начальные узлы и дуги (что было гарантировано возможным), для оптимизатора было допустимо иногда отклонять добавление дополнительных дуг там, где они действительно могли быть. Добавлено Это приближение не является необходимым для этого алгоритма, когда он доведен до конца, но он допускает такое приближение, если вы хотите это сделать, и, таким образом, еще больше ограничивает время его выполнения).
Хотя граф топологически отсортирован, он гарантированно не содержит циклов. На первом этапе, когда мне нужно было добавить статическое количество узлов и дуг, я добавил узлы, а затем отсортировал их топологически.
Во время второй фазы добавления дополнительных дуг возможны две ситуации при рассмотрении дуги из A в B. Если A уже лежит левее B в сортировке, можно просто добавить дугу и цикл не может быть сгенерирован, так как список по-прежнему топологически отсортирован.
Если B находится слева от A, мы рассматриваем подпоследовательность между B и A и разбиваем ее на две непересекающиеся последовательности X, Y, где X — те узлы, которые могут достигать A (а Y — остальные). Если A недостижимо из B , т. е. нет прямых дуг из B в X или в A, то последовательность может быть переупорядочена XABY перед добавлением дуги A в B, показывая, что она по-прежнему не содержит циклов, и сохраняя топологическую сортировку. Эффективность по сравнению с наивным алгоритмом здесь заключается в том, что нам нужно рассматривать только подпоследовательность между B и A, поскольку наш список топологически отсортирован: A недостижим ни из одного узла справа от A. Для моей ситуации, когда локализованные переупорядочивания являются наиболее частыми и важно, это важный выигрыш.
Поскольку мы не меняем порядок внутри последовательностей X,A,B,Y, ясно, что любые дуги, которые начинаются или заканчиваются в одной и той же последовательности, по-прежнему упорядочены правильно и одинаково на каждом фланге, а любые дуги «пролета» из слева на правый фланг. Любые дуги между флангами и X,A,B,Y также по-прежнему упорядочены правильно, поскольку наше переупорядочивание ограничено этой локальной областью. Поэтому нам нужно рассматривать только дуги между нашими четырьмя последовательностями. Рассмотрим каждую возможную «проблемную» дугу для нашего окончательного порядка XABY по очереди: YB YA YX BABX AX. Наш первоначальный заказ был B[XY]A, поэтому AX и YB не могут возникнуть. X достигает A, а Y нет, поэтому YX и YA не встречаются или A может быть достигнуто из источника дуги в Y (потенциально через X) — противоречие. Нашим критерием приемлемости было отсутствие ссылок BX или BA. Так что проблемных дуг нет,
Наш единственный критерий приемлемости (недостижимость A из B) явно достаточен для создания цикла при добавлении дуги A->B: B-(X)->A->B, поэтому показано и обратное.
Это может быть реализовано достаточно эффективно, если мы сможем добавить флаг к каждому узлу. Рассмотрим узлы [BXY], идущие справа налево от узла непосредственно слева от A. Если этот узел имеет прямую дугу к A, установите флаг. В произвольном таком узле нам нужно рассматривать только прямые исходящие дуги: узлы справа от него либо после A (и поэтому нерелевантны), либо уже помечены, если достижимы из A, поэтому флаг на таком произвольном узле устанавливается когда любые помеченные узлы встречаются по прямой ссылке. Если B не помечен в конце процесса, переупорядочивание допустимо, и помеченные узлы содержат X.
Хотя это всегда дает правильное упорядочение, если оно доведено до конца (насколько я могу судить), как я упоминал во введении, это особенно эффективно, если ваша начальная сборка приблизительно правильная (в смысле размещения возможных дополнительных дуг без изменения порядка).
Также существует эффективное приближение, если ваш контекст таков, что «возмутительные» дуги могут быть отклонены (те, которые будут массово переупорядочиваться), ограничивая расстояние от A до B, которое вы готовы сканировать. Если у вас есть первоначальный список дополнительных дуг, которые вы хотите добавить, их можно упорядочить, увеличивая расстояние в начальном порядке, пока у вас не закончится некоторый «кредит» сканирования, и на этом этапе ваша оптимизация завершится.
Если график направлен, вам нужно будет только проверить родительские узлы (перемещаться вверх, пока не дойдете до корня) узла, с которого должно начинаться новое ребро. Если один из родительских узлов равен концу ребра, добавление ребра создаст цикл.
Если все предыдущие работы в топологически отсортированном порядке. Затем, если вы добавляете ребро, которое кажется тормозящим сортировку, и не может быть исправлено, тогда у вас есть цикл.
Итак, если у нас есть отсортированный список узлов:
1, 2, 3, ..., x, ..., z, ...
Such that each node is waiting for nodes to its left.
Скажем, мы хотим добавить ребро из x->z. Ну, похоже, это тормозит. Таким образом, мы можем переместить узел в точке x в положение z+1, что зафиксирует сортировку, если ни один из узлов (x, z] не имеет ребра для узла в точке x.