graph theory - tabla - ¿Cómo detectar si agregar un borde a un gráfico dirigido da como resultado un ciclo?

como redondear los bordes de las celdas en excel (4)

Me encontré con los gráficos de espera y me pregunto, ¿hay algoritmos eficientes para detectar si agregar una ventaja a un gráfico dirigido da como resultado un ciclo?

Los gráficos en cuestión son mutables (pueden tener nodos y bordes agregados o eliminados). Y no nos interesa conocer realmente un ciclo ofensivo, solo saber que hay uno es suficiente (para evitar agregar una ventaja ofensiva).

Por supuesto, sería posible usar un algoritmo para calcular componentes fuertemente conectados (como el de Tarjan) para verificar si el nuevo gráfico es acíclico o no, pero ejecutarlo de nuevo cada vez que se agrega un borde parece bastante ineficaz.

Como Mark sugirió, es posible utilizar la estructura de datos que almacena los nodos conectados. Es lo mejor usar matriz booleana |V|x|V| . Los valores se pueden inicializar con el algoritmo Floyd – Warshall. Eso se hace en O(|V|^3) .

Sea T(i) un conjunto de vértices que tienen ruta al vértice i , y F(j) conjunto de vértices donde existe la ruta desde el vértice j . Primero están los verdaderos en la fila i y los segundos verdaderos en la columna j ''th.

Agregar un borde (i,j) es una operación simple. Si i y j no estaban conectados antes, entonces para cada a desde T(i) y cada b desde F(j) establece el elemento de matriz (a,b) en verdadero. Pero la operación no es barata. En el peor de los casos es O(|V|^2) . Eso es en el caso de una línea dirigida, y agregar un borde desde el extremo hasta el vértice de inicio hace que todos los vértices se conecten a todos los otros vértices.

Eliminar un borde (i,j) no es una operación tan simple, pero no más costosa en el peor de los casos :-) Si hay un camino de i a j después de eliminar el borde, no cambia nada. Eso se verifica con Dijkstra, menos que O(|V|^2) . Los vértices que ya no están conectados son (a,b) :

a en T(i) - i - T(j) ,
b en F(j) + j

Solo T(j) se cambia con la eliminación del borde (i,j) , por lo que debe recalcularse. Esto se hace mediante cualquier tipo de desplazamiento de gráficos (BFS, DFS), yendo en la dirección del borde opuesto del vértice j . Eso se hace en menos de O(|V|^2) . Dado que la configuración del elemento de matriz es, en el peor de los casos, otra vez O(|V|^2) , esta operación tiene la misma complejidad en el peor de los casos que la adición de borde.

Si el gráfico está dirigido, solo tendría que verificar los nodos principales (navegar hacia arriba hasta llegar a la raíz) del nodo donde debería comenzar el nuevo borde. Si uno de los nodos principales es igual al final del borde, agregar el borde crearía un ciclo.

Si entendí su pregunta correctamente, entonces una nueva arista (u, v) solo se inserta si no había una ruta desde v hasta u antes (es decir, si (u, v) no crea un ciclo). Por lo tanto, su gráfica siempre es un DAG (gráfica acíclica dirigida). El uso del algoritmo de Tarjan para detectar componentes fuertemente conectados ( http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ) suena como una exageración en este caso. Antes de insertar (u, v), todo lo que tiene que verificar es si hay una ruta dirigida de v a u, lo que se puede hacer con un simple BFS / DFS.

Así que la forma más sencilla de hacerlo es la siguiente (n = | V |, m = | E |):

Inserción (u, v): verifique si hay una ruta desde v hasta u (BFS / DFS). Complejidad del tiempo: O (m)
Eliminar bordes: simplemente elimínelos del gráfico. Complejidad del tiempo: O (1)

Aunque insertar (u, v) lleva O (m) tiempo en el peor de los casos, es probable que sea bastante rápido en su situación. Al hacer el BFS / DFS comenzando desde v para verificar si se puede alcanzar u, solo se visitan los vértices accesibles desde v. Supongo que en su configuración el gráfico es bastante escaso y que el número de vértices a los que puede acceder otro no es eso alto.

Sin embargo, si desea mejorar el tiempo de ejecución teórico, aquí hay algunos consejos (que muestran que esto no será muy fácil). Supongamos que nuestro objetivo es probar en O (1) tiempo si existe una ruta dirigida de v a u. La palabra clave en este contexto es el cierre transitivo de un DAG (es decir, un gráfico que contiene un borde (u, v) si y solo si hay una ruta dirigida de u a v en el DAG). Desafortunadamente, mantener el cierre transitivo en un entorno dinámico no parece ser tan simple. Hay varios documentos que consideran este problema y todos los documentos que encontré fueron STOC o FOCS, lo que indica que están muy involucrados. El resultado más nuevo (y más rápido) que encontré está en el artículo Dynamic Transitive Closure a través de Dynamic Matrix Inverse by Sankowski ( http://dl.acm.org/citation.cfm?id=1033207 ).

Incluso si está dispuesto a comprender uno de esos algoritmos de cierre dinámico transitivo (o incluso desea implementarlo), no le darán ninguna velocidad por la siguiente razón. Estos algoritmos están diseñados para la situación, donde tiene muchas consultas de conectividad (que luego se pueden realizar en tiempo O (1)) y solo algunos cambios en el gráfico. El objetivo entonces es hacer que estos cambios sean más económicos que volver a calcular el cierre transitivo. Sin embargo, esta actualización es aún más lenta que una única comprobación de conectividad. Por lo tanto, si necesita hacer una actualización en cada consulta de conectividad, es mejor usar el enfoque simple mencionado anteriormente.

Entonces, ¿por qué menciono este enfoque de mantener el cierre transitivo si no se ajusta a sus necesidades? Bueno, muestra que buscar un algoritmo que solo consuma tiempo de consulta O (1) probablemente no lo lleve a una solución más rápida que la simple utilizando BFS / DFS. Lo que podría intentar es obtener un tiempo de consulta más rápido que O (m) pero peor que O (1), mientras que las actualizaciones también son más rápidas que O (m). Este es un problema muy interesante, pero a mi me parece un objetivo muy ambicioso (por lo tanto, tal vez no dedique demasiado tiempo a intentarlo).

Si todos los trabajos anteriores están ordenados topológicamente. Luego, si agrega un borde que parece frenar la clasificación y no se puede arreglar, entonces tiene un ciclo.

https://.com/a/261621/831850

Así que si tenemos una lista ordenada de nodos:

1, 2, 3, ..., x, ..., z, ... Such that each node is waiting for nodes to its left.

Digamos que queremos agregar un borde desde x-> z. Bueno, eso parece frenar el ordenamiento. Así que podemos mover el nodo en x a la posición z + 1 que arreglará la ordenación si ninguno de los nodos (x, z] tiene un borde al nodo en x.