Замыкание DAG (ориентированного ациклического графа)

[Geen]

Добрый день!

Предварительная задача.
Имеется направленный ациклический граф (достаточно разреженный, для определённости можно считать, что кол-во рёбер порядка $N\log N$, где $N$ - количество вершин графа).
К графу могут добавляться/убираться вершины/рёбра (без дублирования и нарушения ацикличности).
Необходимо быстро отвечать на вопрос связаны ли две вершины путём (в том числе, и для проверки ацикличности при добавлении нового ребра).
Напрашивается решение хранить предпосчитанными все пары вершин, связанных хотя бы одним путём (транзитивное замыкание).
При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.

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

Вариант с хранением предпосчитанными всех путей выглядит неоптимальным.
Есть ли решения лучше?

[popolznev]

Цитата:

после чего все пути, проходящие через эту пару вершин считаются недействительными

Это значит - пути, содержащие ребро, связывающее эти две вершины?

[Geen]

popolznev в сообщении #955571 писал(а):

Цитата:

после чего все пути, проходящие через эту пару вершин считаются недействительными

Это значит - пути, содержащие ребро, связывающее эти две вершины?

Нет, такого ребра может и не быть. "Исключаются" все пути, в которых встречается указанная пара вершин (в заданном порядке).

[Skeptic]

Один путь включает в себя несколько коротких. Попробуйте хранить самые длинные пути.
Например, для кольцевого направленного незамкнутого графа достаточно хранить один самый длинный путь. На таком графе можно изучить изменение путей при добавлении/удалении вершин/рёбер.

[arseniiv]

Skeptic в сообщении #955591 писал(а):

Попробуйте хранить самые длинные пути.

И что с ними делать при добавлении ребра к вершине, входящей в «выключенный»? Если хранить все пути, можно будет новые посчитать без особых проблем (кажется).

Geen в сообщении #955533 писал(а):

При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.

А как это хранение при удалении ребра обновлять быстрее, чем обновлять транзитивное замыкание?

[Geen]

arseniiv в сообщении #955616 писал(а):

Geen в сообщении #955533 писал(а):

При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.

А как это хранение при удалении ребра обновлять быстрее, чем обновлять транзитивное замыкание?

Обозначим ребро от вершины a до вершины b как (ab), множество вершин, из которых достижима вершина a через U(a), множество вершин которые достижимы из вершины b как D(b). Сами вершины тоже входят в соответствующие мн-ва. Элементы соответствующих мн-в обозначаем буквой в нижнем регистре (например, $u(a)\in U(a)$). Кол-во путей от c к d обозначим $P(c,d)$ ($\forall x P(x,x)=1$). Тогда, добавление ребра (ab) приводит к следующим изменениям кол-ва путей: $P'(u(a),d(b))=P(u(a),d(b))+P(u(a),a) P(b,d(b))$. Остальные "счётчики" остаются неизменными. Удаление ребра приводит к обратному изменению "счётчиков". При этом, $P(c,d)=0$, очевидно, эквивалентно отсутствию путей, и такие пары можно просто не хранить/удалять.

-- 03.01.2015, 01:28 --

Есть две идеи, которые я пока не знаю как (можно ли) развить.
1. Рёбра, входящие в вершину b можно интепретировать как операцию объединения: $U(b)=\{b\}\cup\bigcup_a U(a)$. Тогда, пометка пары вершин (cb) будет означать $U(b)=\{b\}\cup\bigcup_a U(a)\backslash U(c)$
2. Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра. Соответсвенно, как-то вести учёт моно/полихромных путей.

[arseniiv]

Geen в сообщении #955651 писал(а):

Удаление ребра приводит к обратному изменению "счётчиков".

Хм, точно…

Geen в сообщении #955651 писал(а):

2. Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра. Соответсвенно, как-то вести учёт моно/полихромных путей.

Видимо, можно вести достаточно прямо: $P_k(a,b)$ — количество путей, содержащих хотя бы одно ребро цвета $k$. Как будто считаться должно не сильно сложнее. И, если так, это замечательное решение (и вряд ли упрощаемое)!

[Geen]

arseniiv в сообщении #960316 писал(а):

Видимо, можно вести достаточно прямо: $P_k(a,b)$ — количество путей, содержащих хотя бы одно ребро цвета $k$. Как будто считаться должно не сильно сложнее.

К сожалению, я не нашёл как это применить к исходной задаче...

[arseniiv]

Как же? Вы ведь сами писали:

Geen в сообщении #955651 писал(а):

Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра.

Тогда если $P_\text{ч}(c,d) = P(c,d)$, все пути из $c$ в $d$ содержат хоть одно чёрное ребро, и потому переход $c\to d$ заблокирован. Ну а если $P_\text{ч}(c,d) < P(c,d)$, пути ещё есть.

Вообще, я сначала понял слова «добавление чёрного ребра» как предварительное удаление исходного и потом уже добавление чёрного. Такая смена цвета не изменит соответствующие $P$, но изменит $P_\text{ч}$.