Búsqueda de unión dirigida

11

Considere un gráfico dirigido en el que se pueden agregar bordes dinámicamente y hacer algunas consultas específicas.G

Ejemplo: bosque disjunto

Considere el siguiente conjunto de consultas:

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

el primero agrega una flecha al gráfico, el segundo decide si , el último encuentra un representante canónico de la clase de equivalencia de , es decir, tal que implica .u v r ( u ) u v r ( v ) = r ( u )uvuvr(u)uvr(v)=r(u)

Existe un algoritmo bien conocido que utiliza la estructura de datos forestales de conjunto disjunto que implementa estas consultas en una complejidad amortizada casi constante, a saber, O(α(n)) . Tenga en cuenta que en este caso equivse implementa utilizando find.

Variante más compleja

Ahora estoy interesado en un problema más complejo en el que las instrucciones son importantes:

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

el primero agrega una flecha , los segundos deciden si hay un nodo accesible desde y , es decir, . El último debe devolver un objeto modo que implique donde debe ser fácilmente computable. (Para, por ejemplo, computa ). El objetivo es encontrar una buena estructura de datos para que estas operaciones sean rápidas.uvwuvuvr(u)uvr(u)r(v)confl

Ciclos

El gráfico puede contener ciclos.

No sé si hay una manera de calcular de manera eficiente e incremental los componentes fuertemente conectados, a fin de considerar solo los DAG para el problema principal.

Por supuesto, también agradecería una solución para los DAG. Correspondería a un cálculo incremental del antepasado menos común.

Enfoque ingenuo

La estructura de datos del bosque de conjunto disjunto no es útil aquí, ya que ignora la dirección de los bordes. Tenga en cuenta que no puede ser un solo nodo, en el caso de que el gráfico no sea confluente.r(u)

Se puede definir y definir como cuando . Pero, ¿cómo calcular esto de forma incremental?r(u)={vuv}S1S2S1S2

Probablemente que calcular un conjunto tan grande no sea útil, un conjunto más pequeño debería ser más interesante, como en el algoritmo habitual de búsqueda de unión.

jmad
fuente

Respuestas:

3

( Editar : reescribí completamente mi respuesta ahora que mi comprensión del problema es (espero) más clara).

Parece que este problema puede reducirse a construir y mejorar gradualmente una aproximación del cierre transitivo del gráfico, a medida que el gráfico se construye y se busca.

r(u) es, de manera abstracta, el conjunto de todos los nodos a los que se puede acceder desde y para cada en el gráfico. (Por supuesto, no todos los pares necesariamente tendrán un nodo al que se pueda llegar desde ambos). A diferencia del caso en union-find, este conjunto no puede representarse como un nodo canónico representativo en el gráfico, porque puede haber nodos a los que se pueda acceder desde y , y desde ambos y , que no se puedan alcanzar desde y .uvvuu,vuvuwvw

Digamos que usted mantiene, para cada , un conjunto de nodos accesibles desde (llamaré a esto ). Estos conjuntos serían necesariamente una estructura de datos adicional para cada nodo, o al menos, un conjunto de bordes de "acceso directo" adicionales en el gráfico. Si no le importa conservar la estructura especificada del gráfico, no habría necesidad de distinguir entre estos bordes y los bordes especificados.uuR(u)

No tengo ninguna idea para una estructura de datos que capture esto que sea más eficiente que el caso general (por ejemplo, un vector de bits o una tabla hash), pero puede actualizar estos conjuntos de forma incremental:

Cada vez que agrega una arista desde a algún otro nodo , establece .uvR(u)=R(u)R(v)

Implemente conflprobando primero ; si eso no está vacío, devuelve verdadero. Pero si está vacío, realice dos búsquedas paralelas de amplitud primero desde y hasta agotar ambos conjuntos accesibles o encontrar un nodo en común. Mientras hace esto, también actualice y (y las 's de todos los nodos intermedios que encuentre) para incluir los nodos accesibles que encontró. y si encuentra un nodo en común, establezca R (u) = R (v) = R (u) \ cup R (v) .R(u)R(v)R(u)R(v)R(u)R(v)R

find(u)solo devuelve . El problema es que no se implementa únicamente en términos de . No veo cómo podría ser a menos que el algoritmo no fuera incremental (es decir, precalcule todos los conjuntos de todos los nodos con el cierre transitivo del gráfico). Sin embargo, el enfoque incremental aún debería proporcionarle una amortización bastante buena costo, aunque no tengo idea de si se acerca a antemano. (Probablemente no. Una respuesta falsa requiere que inicies dos BFS incluso cuando tus conjuntos estén saturados; esto también parece inevitable a menos que el algoritmo se haga no incremental).R(u)conflfindRO(α(n))conflR

Esto se parece mucho a que podría ser un caso especial de los métodos de La Poutré y van Leeuwen para mantener el cierre transitivo de un gráfico .

Me doy cuenta de que esto no responde completamente a la pregunta, pero tal vez sirve para aclararlo, y alguien que tenga más experiencia con algoritmos de gráficos puede proporcionar una mejor estructura de datos para codificar los conjuntosR

Chris Pressey
fuente
Gracias por su respuesta, espero haber aclarado mi pregunta ahora: no me interesan los componentes conectados (pero los CCs pueden ser útiles para la solución final); Todavía no tengo y este no puede ser un solo nodo en un DAG. r(u)r(u)
jmad
OK, eso está un poco más claro. Parecería que es, de manera abstracta, el conjunto de todos los nodos a los que se puede acceder desde y para cada en el gráfico. Este conjunto podría ser un conjunto de bordes de "atajo" fuera de , creo, y luego esto comienza a parecerse a calcular el cierre transitivo de la accesibilidad en el gráfico. Todavía no veo de inmediato por qué esto no se puede hacer de forma incremental (comprima las rutas a medida que las encuentra), aunque probablemente requeriría más almacenamiento / trabajo (etiquetar / actualizar todos los bordes de "acceso directo") que union-find. ¿Esto tiene sentido? r(u)uv vuu
Chris Pressey
Asumiendo que el cierre transitivo es una forma justa de caracterizar , parece que estaría estrechamente relacionado: en.wikipedia.org/wiki/…r(u)
Chris Pressey
No creo que confl(u,v)deba fusionar y . Podría modificarlos, pero eso ya lo haría la llamada a , como en el método del bosque de conjunto disjunto. R(u)R(v)find
jmad
Tienes razón en que no debería fusionarlos; Editaré la respuesta. Pero las llamadas a findrealmente no pueden calcular nada útil, porque no hay un objeto único para "encontrar", excepto , que aproxima. (¿Cómo saber qué buscar para realizar actualizaciones? Solo se proporciona pero la información en aplica potencialmente a todos los demás nodos en el gráfico.)r(u)R(u)finduR(u)
Chris Pressey