Как определить, добавляет ли край к ориентированному графу цикл?

Я столкнулся с ожидающими графиками, и мне интересно, существуют ли какие-либо эффективные алгоритмы для обнаружения, если добавление ребра к ориентированному графу приводит к циклу?

Рассматриваемые графы являются изменяемыми (они могут иметь добавленные или удаленные узлы и ребра). И мы не заинтересованы в том, чтобы действительно знать оскорбительный цикл, просто зная, что одного достаточно (чтобы не добавлять к нему оскорбительный край).

Конечно, можно было бы использовать алгоритм для вычисления сильно связанных компонентов (например, Tarjan's), чтобы проверить, является ли новый граф ацикличным или нет, но повторять его каждый раз при добавлении края кажется довольно неэффективным.

Ответ 1

Если я правильно понял ваш вопрос, то новый ребро (u, v) будет вставлен только в том случае, если раньше не было пути от v до u (т.е. если (u, v) не создает цикл). Таким образом, ваш график всегда является DAG (направленный ациклический граф). Использование Tarjan Algorithm для обнаружения сильно связанных компонентов (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 (m)
Удаление ребер: Просто удалите их из графика. Сложность времени: O (1)

Хотя вставка (u, v) занимает O (m) время в худшем случае, вероятно, довольно быстро в вашей ситуации. Когда вы делаете BFS/DFS, начиная с v, чтобы проверить, достижимо ли u, вы только посещаете вершины, которые достижимы с v. Я бы предположил, что в вашей настройке граф довольно разрежен и что число вершин, доступных другому, не так высокий.

Однако, если вы хотите улучшить теоретическое время работы, вот несколько советов (в основном, показывая, что это будет непросто). Предположим, мы стремимся к тестированию в течение O (1) времени, существует ли направленный путь от v до u. Ключевое слово в этом контексте является транзитивным замыканием DAG (т.е. Графом, содержащим ребро (u, v) тогда и только тогда, когда существует направленный путь от u до v в DAG), К сожалению, сохранение транзитивного замыкания в динамическом режиме кажется не таким простым. Есть несколько статей, посвященных этой проблеме, и все документы, которые я нашел, были документами STOC или FOCS, что указывает на то, что они очень. Самый новый (и самый быстрый) результат, который я нашел, приведен в статье Динамическое транзитивное закрытие с помощью динамической матрицы Inverse Санковского (http://dl.acm.org/citation.cfm?id=1033207).

Даже если вы готовы понять один из этих динамических транзитивных алгоритмов закрытия (или даже хотите его реализовать), они не будут давать вам ускорение по следующей причине. Эти алгоритмы предназначены для ситуации, где у вас много запросов на подключение (которые затем могут быть выполнены в O (1) раз) и только несколько изменений в графике. Цель состоит в том, чтобы сделать эти изменения дешевле, чем перерасчет транзитивного закрытия. Однако это обновление все еще медленнее, чем одна проверка подключения. Таким образом, если вам нужно сделать обновление для каждого запроса на подключение, лучше использовать простой подход, упомянутый выше.

Итак, почему я упоминаю этот подход сохранения транзитивного закрытия, если он не соответствует вашим потребностям? Ну, это показывает, что поиск алгоритма, использующего только время запроса O (1), вероятно, не приведет вас к решению быстрее простого с использованием BFS/DFS. То, что вы можете попробовать, - это получить время запроса, которое быстрее, чем O (m), но хуже, чем O (1), а обновления также быстрее, чем O (m). Это очень интересная проблема, но это звучит для меня как очень амбициозная цель (так что, возможно, не трать слишком много времени на ее достижение).

Ответ 2

Как отметил Марк, можно использовать структуру данных, в которой хранятся связанные узлы. Лучше всего использовать булевую матрицу |V|x|V|. Значения могут быть инициализированы алгоритмом Флойда-Варшалла. Это делается в O(|V|^3).

Пусть T(i) - множество вершин, имеющих путь к вершине i, и F(j) набор вершин, где существует путь от вершины j. Сначала они верны в i 'th строке, а вторая - в столбце j'.

Добавление ребра (i,j) - простая операция. Если i и j не были подключены раньше, чем для каждого a из T(i), а каждый b из F(j) задал матричный элемент (a,b) равным true. Но операция не из дешевых. В худшем случае это O(|V|^2). То есть в случае направленной линии, а добавление края от вершины к начальной вершине делает все вершины соединенными со всеми другими вершинами.

Удаление ребра (i,j) - это не так просто, но не более дорогостоящая операция в худшем случае:-) Если после удаления края есть путь от i до j, то ничего не меняется. Это проверяется с помощью Dijkstra, меньше O(|V|^2). Вершины, которые не связаны больше, (a,b):

a в T(i) - i - T(j),
b in F(j) + j

Только T(j) изменяется с удалением края (i,j), поэтому его необходимо пересчитать. Это делается путем любого перемещения графика (BFS, DFS), переходя в противоположное направление от вершины j. Это делается менее чем за O(|V|^2). Поскольку установка матричного элемента в худшем случае снова равна O(|V|^2), эта операция имеет такую же худшую сложность, как добавление ребра.

Ответ 3

Если все предыдущие задания находятся в топологически отсортированном порядке. Затем, если вы добавите ребро, которое, похоже, заблокирует сортировку и не может быть исправлено, тогда у вас есть цикл.

fooobar.com/questions/2304/...

Итак, если у нас есть отсортированный список узлов:

1, 2, 3, ..., x, ..., z, ...
Such that each node is waiting for nodes to its left.

Скажем, мы хотим добавить ребро из x- > z. Хорошо, что, похоже, тормозит сортировку. Таким образом, мы можем переместить node в x в положение z + 1, которое будет фиксировать сортировку iif, если ни один из узлов (x, z] не имеет ребра к node в точке x.

Ответ 4

Если график направлен, вам нужно будет только проверить родительские узлы (перемещаться вверх, пока не достигнете корня) node, где должен начинаться новый край. Если один из родительских узлов равен концу ребра, добавление края создаст цикл.