União-encontrar dirigido

Considere um gráfico direcionado $G$ no qual é possível adicionar dinamicamente arestas e fazer algumas consultas específicas.

Exemplo: floresta com conjunto separado

Considere o seguinte conjunto de consultas:

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

o primeiro adiciona uma seta $u→v$ para o gráfico, o segundo decide se $u↔^*v$ , o último se encontra um representante canônico da classe de equivalência de $↔^*$ , ou seja, um $r(u)$ de tal forma que $u↔^*v$ implica $r(v)=r(u)$ .

Existe um algoritmo bem conhecido usando a estrutura de dados da floresta de conjunto separado, implementando essas consultas com complexidade amortizada quase constante, a saber . Observe que, neste caso, é implementado usando .$O(α(n))$equivfind

Variante mais complexa

Agora, estou interessado em um problema mais complexo, onde as instruções são importantes:

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

o primeiro adiciona uma seta , os segundos decide se existe um nó acessível a partir do e , ou seja, . O último deve retornar um objeto forma que implique onde deva ser facilmente computável. (Para, digamos, computar ). O objetivo é encontrar uma boa estrutura de dados para que essas operações sejam rápidas.w u v u → ∗ ← ∗ v r ( u ) u → ∗ ← ∗ v r ( u ) ∙ r ( v ) $u→v$$w$$u$$v$$u→^*←^*v$$r(u)$$u→^*←^*v$$r(u) \bullet r(v)$$\bullet$confl

Ciclos

O gráfico pode conter ciclos.

Não sei se existe uma maneira de calcular de maneira eficiente e incremental os componentes fortemente conectados, a fim de considerar apenas os DAGs para o problema principal.

É claro que eu também apreciaria uma solução para DAGs. Corresponderia a uma computação incremental do ancestral menos comum.

Abordagem ingênua

A estrutura de dados da floresta desarticulada não é útil aqui, pois desconsidera a direção das arestas. Observe que não pode ser um nó único, caso o gráfico não seja confluente.$r(u)$

Pode-se definir e definir como quando S 1 ∩ S 2 ≠ ∅ . Mas como calcular isso de forma incremental?∙ S 1 ∙ S $r(u)=\{v ∣ u→^*v\}$$\bullet$$S_1\bullet S_2$$S_1 ∩ S_2≠∅$

Provavelmente que a computação de um conjunto tão grande não seja útil, um conjunto menor deve ser mais interessante, como no algoritmo usual de busca por união.

( Editar : reescrevi completamente minha resposta agora que minha compreensão do problema é (espero) mais clara.)

Parece que esse problema pode ser reduzido à construção e aprimoramento incremental de uma aproximação do fechamento transitivo do gráfico, à medida que o gráfico é construído e pesquisado.

é, em abstracto, o conjunto de todos os nós que são acessíveis a partir de ambos u e v para cada v ≠ u no gráfico. (É claro que nem todos ospares u , v necessariamente terão um nó que pode ser alcançado pelos dois.) Diferentemente do caso na localização por união, esse conjunto não pode ser representado como um nó representativo canônico no gráfico, porque pode haver nós que estão ao alcance de ambos u e v , e de ambos u e w , que, todavia, não são acessível a partir do v e w .$r(u)$$u$$v$$v \ne u$$u, v$$u$$v$$u$$w$$v$$w$

Digamos que você mantenha, para cada , um conjunto de nós alcançáveis ​​a partir de u (chamarei de R ( u ) ). Esses conjuntos seriam necessariamente uma estrutura de dados extra para cada nó, ou pelo menos um conjunto de arestas de "atalho" extras no gráfico. Se você não se preocupa em manter a estrutura especificada do gráfico, não há necessidade de distinguir entre essas arestas e as arestas especificadas.$u$$u$$R(u)$

Não tenho ideias imediatas para uma estrutura de dados que captura isso mais eficiente do que o caso geral (por exemplo, um vetor de bits ou tabela de hash), mas você pode atualizar esses conjuntos de forma incremental:

Cada vez que você adiciona uma aresta de a algum outro nó v , você define R ( u ) = R ( u ) ∪ R ( v ) .$u$$v$$R(u) = R(u) \cup R(v)$

Implementar confltentando primeiro ; se não estiver vazio, retorne true. Mas se estiver vazio, faça duas buscas paralelas em primeiro lugar a partir de R ( u ) e R ( v ) até você esgotar os dois conjuntos alcançáveis ​​ou encontrar um nó em comum. Enquanto você faz isso, atualize também R ( u ) e R ( v ) (e os Rs de todos os nós intermediários encontrados) para incluir os nós alcançáveis ​​que você encontrou.$R(u) \cap R(v)$$R(u)$$R(v)$$R(u)$$R(v)$$R$e se você encontrar um nó em comum, defina R (u) = R (v) = R (u) \ cup R (v) .

find(u)apenas retorna . O problema é que isso não é implementado apenas em termos de . Não vejo como isso poderia ser, a menos que o algoritmo não fosse incremental (ou seja, pré-calcule todos os conjuntos R de todos os nós com o fechamento transitivo do gráfico.) No entanto, a abordagem incremental ainda deve fornecer amortizações razoavelmente boas custo, embora eu não tenha idéia se ele se aproxima de O ( α ( n ) ) imediatamente. (Provavelmente não. Uma resposta falsa exige que você inicie dois BFS, mesmo quando seus conjuntos R estão saturados; isso também parece inevitável, a menos que o algoritmo seja tornado não incremental.)$R(u)$conflfind$R$$O(\alpha(n))$confl$R$

Parece muito que pode ser um caso especial dos métodos de La Poutré e van Leeuwen para manter o fechamento transitivo de um gráfico .

$R$