Направленный союз-найти

11

Рассмотрим ориентированный граф , на котором можно динамически добавлять края и сделать некоторые конкретные запросы.грамм

Пример: непересекающееся-множество лесов

Рассмотрим следующий набор запросов:

arrow(u, v)
equiv(u, v)
find(u)

первый добавляет стрелку к графу, второй решает, если , последний находит канонического представителя класса эквивалентности , то есть a такого что подразумевает .u v r ( u ) u v r ( v ) = r ( u )UvU*v*р(U)U*vр(v)знак равнор(U)

Существует хорошо известный алгоритм с использованием структуры данных лесов непересекающейся-набором , реализующую эти запросы в квазипостоянном амортизируется, а именно сложность . Обратите внимание , что в данном случае реализуется с помощью .О(α(N))equivfind

Более сложный вариант

Теперь меня интересует более сложная проблема, где направления имеют значение:

arrow(u, v)
confl(u, v)
find(u)

первый добавляет стрелку , секунд решает, есть ли узел достижимый как от и от , т.е. . Последний должен возвращать объект такой, что подразумевает где должен легко вычисляться. (Для того, чтобы, скажем, вычислить ). Цель состоит в том, чтобы найти хорошую структуру данных, чтобы эти операции выполнялись быстро.Uvвесuvuvr(u)uvr(u)r(v)confl

циклы

Граф может содержать циклы.

Я не знаю, есть ли способ эффективно и постепенно вычислять сильно связанные компоненты, чтобы рассматривать DAG только для основной проблемы.

Конечно, я был бы признателен за решение для DAG. Это будет соответствовать инкрементному вычислению наименее общего предка.

Наивный подход

Структура данных леса с несвязным множеством здесь не помогает, так как она игнорирует направление ребер. Обратите внимание, что не может быть одним узлом, если граф не является слитым.r(u)

Можно определить и определить как когда . Но как вычислить это постепенно?S 1S 2 S 1S 2r(u)={vuv}S1S2S1S2

Вероятно, что вычисление такого большого набора бесполезно, меньший набор должен быть более интересным, как в обычном алгоритме поиска объединения.

jmad
источник

Ответы:

3

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

Похоже, что эту проблему можно свести к постепенному построению и улучшению аппроксимации транзитивного замыкания графа по мере построения и поиска графа.

у v v U U , V U V U ш V шr(u) - это, абстрактно, множество всех узлов, которые достижимы из и для каждого в графе. (Конечно, не все пары обязательно будут иметь узел, к которому можно обратиться из обоих.) В отличие от случая в union-find, этот набор не может быть представлен как канонический репрезентативный узел в графе, потому что могут быть узлы, которые достижимы как от и , так и от и , которые, тем не менее, недоступны как от и от .uvvuu,vuvuwvw

Скажите , вы поддерживаете, для каждого , множество вершин , достижимых из (я буду называть эту ). Эти наборы по необходимости могут быть дополнительной структурой данных для каждого узла или, по крайней мере, набором дополнительных «горячих» ребер в графе. Если вы не заботитесь о сохранении указанной структуры графа, не было бы необходимости различать эти ребра и заданные ребра.U R ( U )uuR(u)

У меня нет никаких идей по поводу структуры данных, которая фиксирует это, что более эффективно, чем общий случай (например, битовый вектор или хэш-таблица), но вы можете обновлять эти наборы постепенно:

Каждый раз, когда вы добавляете ребро от к другому узлу , вы устанавливаете .v R ( u ) = R ( u ) R ( v )uvR(u)=R(u)R(v)

Реализовать conflпервым пытающегося ; если это не пусто, возвращает истину. Но если он является пустым, сделайте два параллельных ширину первого поиска из и , пока вы не исчерпывают оба множества достижимости или найти узел общего. В то время как вы делаете это, а также обновление и (и «S всех промежуточных узлов , которые вы найдете) включать достижимые узлы , которые вы нашли. и если вы нашли узел в общем, набор R (и) = R (v) = R (и) \ чашка R (v) .R ( U ) R ( v ) R ( U ) R ( v ) RR(u)R(v)R(u)R(v)R(u)R(v)R

find(u)просто возвращает . Проблема заключается в том, что не реализуется исключительно в терминах . Я не понимаю , как это могло бы быть , если алгоритм не был ненаращиваемым (т.е. предварительно вычислить все множества всех узлов с транзитивным замыканием графа.) Тем не менее, поэтапный подход должен еще дать вам достаточно хорошие АМОРТИЗИРОВАННОМУ стоимость, хотя я понятия не имею , если он приближается экспромтом. (Это , вероятно , не ложный ответ от. Требует , чтобы вы запустить два BFS'es даже тогда , когда ваши множества насыщаются;. Это также кажется неизбежным , если алгоритм не сделан ненаращиваемый)R(u)conflfindRO(α(n))conflR

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

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

Крис Пресси
источник
Спасибо за ваш ответ. Надеюсь, теперь я прояснил свой вопрос: мне нет дела до подключенных компонентов (но сильно CC могут быть полезны для окончательного решения); У меня еще нет и этот r ( u ) не может быть единственным узлом в группе обеспечения доступности баз данных. r(u)r(u)
Джмад
r(u)uv vuu
r(u)
confl(u,v)R(u)R(v)find
findр(U)р(U)finduR(u)