Considere un gráfico dirigido en el que se pueden agregar bordes dinámicamente y hacer algunas consultas específicas.
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 )
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, . Tenga en cuenta que en este caso equiv
se 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.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.
Se puede definir y definir como cuando . Pero, ¿cómo calcular esto de forma incremental?
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.
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.find
find
realmente 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.)find