Error Algoritmo de Tarjan
Martín Buchwald
Hola a todos,
Hoy venimos con una “noticia”: hubo un error en nuestra interpretación de un detalle del algoritmo de Tarjan que hace que, dependiendo de algunos factores, nos topemos con falsos negativos (lease, vértices que deberían pertenecer a una CFC no están perteneciendo).
Esto surgió de un error con el que se topaba un compañero al entregar el TP3. En su caso particular, no guardaba los resultados, por lo que en alguno de los pedidos aparecía el bug que estoy por explicar. Con esto quiero decir que aquellos que recibieron un todo ok no tienen que preocuparse, porque habiendo guardado los resultados justo sucede que recorriendo desde Viena (que creo que es el primer caso) no se reproduce, así que no es que tienen que hacer algo (en realidad, podría ser, pero considerando que el error fue nuestro asumimos nosotros el problema y ya).
Supongamos que tenemos el siguiente grafo:
Espero que les sea más o menos evidente que todos los vértices pertenecen a una gran CFC.
Voy a hacer un seguimiento comenzando desde el vértice A, que cómo verán va a estar bastante forzado a toparnos con el error (cualquier bifurcación diferente haría que no se reproduzca, de ahí que surgió en un caso muy particular en un grafo muy grande, y que nunca lo habíamos pensado)
- Empezamos en A, orden[A] = mb[A] = 0. De acá vamos a B.
- Estamos en B, orden[B] = mb[B] = 1. Vamos a C.
- Estamos en C, orden[C] = mb[C] = 2. Vamos a D (no, si viéramos ahora la arista de retorno a A no se reproduciría el bug).
- Estamos en D, orden[D] = mb[D] = 3. Vamos a E.
- Estamos en E, orden[E] = mb[E] = 4. Vemos a C, que ya fue visitado (y está en la pila), entonces mb[E] = min(mb[E], mb[C]) = 2. Terminamos con E, y orden[E] != mb[E], nada que hacer, volvemos a D.
- Volvimos a D, entonces mb[D] = min(mb[D], mb[E]) = 2. Terminamos con los adyacentes de D, y mb[D] != orden[D], nada que hacer, volvemos a C.
- Volvemos a C, entonces mb[C] = min(mb[C], mb[D]) = 2 (no cambió nada), pero vemos ahora el otro adyacente: una arista de retorno a A. Entonces mb[C] = min(mb[C], mb[A]) = 0… pero importantísimo, mb[D] y mb[E] siguen valiendo 2. Terminamos con C, orden[C] != mb[C], no hay nada que hacer, volvemos a B.
- Volvimos a B, entonces mb[B] = min(mb[B], mb[C]) = 0. Terminamos con los adyacentes de B, orden[B] != mb[B], nada que hacer, volvemos a A.
- Volvimos a A, vemos su otro adyacente, F.
- Estamos en F, orden[F] = mb[F] = 1. Vemos su adyacente, E, que ya fue visitado y está en la pila, así que mb[F] = min(mb[F], mb[E]) = 1, no 0. Entonces ahora terminamos con F, vemos que orden[F] == mb[F] y armamos una CFC sólo con F, luego volveremos a A y armaremos una CFC con los demás vértices.
Luego de leer varias veces el pseudocódigo de varias fuentes, encontramos cuál fue el error: considerar el orden como el orden en profundidad. Esto fue una mala interpretación de nuestra parte. Puede verse en el pseudo código que aparece hasta en Wikipedia (bastante válido para el contexto de nuestro TP, je). Ese índice que aparece allí es “global”, en el sentido que siempre aumenta. No debería suceder que F tenga orden 1, sino que debería tener orden 5 (que no sea orden[w] = orden[v] + 1, sino indice + 1, que siempre se actualiza, como si hiciéramos orden[w] = ++indice).
Este error se produce únicamente en un caso así, bastante forzado (cualquier elección diferente que hubiéramos tomado no lo habría reproducido), pero el error existe. Y, debo admitir, por un momento dudé que el Algoritmo estaba mal, pero es indudable que Tarjan sabe más que yo sobre grafos como para andar concluyendo eso tan levemente.
Espero que se haya entendido cuál es el problema y cuál es la solución. Nos aseguraremos que para el próximo cuatrimestre quede esto actualizado tanto en la clase como en el video que tenemos grabado (cuando tenga tiempo lo actualizaré). Como decía Tusam, puede fallar.
Las pruebas siguen estando bien, pero sí tuve que actualizar el ejemplo para Boca del enunciado.
Saludos
Martín