Eliminar las dependencias del ciclo en un gráfico dirigido con bordes fijos

Question

Tengo un gráfico cíclico dirigido. Algunos bordes están FIJOS y no se pueden quitar. Los otros bordes se pueden quitar para romper un ciclo.

¿Cuál es la mejor manera de eliminar los ciclos en este gráfico? El recorrido debe ser tanto como un DFS como sea posible y comenzar en un nodo determinado.

Answer 1

Utilicé el siguiente algoritmo para resolver mi problema:

Comience con un gráfico de todos los bordes fijos marcados como confirmed

Desde un nodo de inicio, repire a través de todos los bordes confirmados, así como los no confirmados. Pero cuando esté a punto de recurrir por un borde aún no confirmado, primero verifique si el nodo al que va el borde tiene una ruta, siguiendo los bordes confirmados, a un nodo en el árbol de búsqueda actual (es decir, un nodo con un < em> visitando conjunto de banderas). Esta verificación debe hacerse de forma recursiva siguiendo todos los bordes confirmados, pero esto es demasiado lento para mí, así que me conformaré aquí para verificar si el nodo está visitando o si alguno de los nodos a los que está confirmado que está conectado está visitando. Esto cubrirá la mayoría de mis casos, pero ocasionalmente deja ciclos en el gráfico.

Después del paso anterior, uso el algoritmo de Tarjan para encontrar los componentes fuertemente conectados que quedan en el gráfico (esto se puede hacer en tiempo O (V + E)). La cantidad de componentes fuertemente conectados será muy pequeña en mis casos, por lo que solo paso por cada componente fuertemente conectado y quito un borde extraíble cada uno. Luego hago este paso nuevamente hasta que no queden más ciclos en el gráfico.

Esto funciona bien y es lo suficientemente rápido.

Answer 2

Lo que puedes hacer es usar el algoritmo de Dijkstra: comienza con un gráfico que contenga solo los bordes FIJOS. Luego aplique una adaptación del algoritmo comenzando con el gráfico que ya tiene:

1. Comience con el nodo inicial y todos los bordes FIJOS en el componente del nodo inicial. Supongamos que esto es un árbol.
2. Agregue el nodo más cercano al árbol.
3. También agregue cualquier borde FIJO en el componente del nodo que acaba de agregar.
4. Si todos los nodos están en el árbol, finalice. De lo contrario, vaya al paso 4.

Esto, por supuesto, asume que la gráfica que consiste solo en los bordes FIJOS no contiene ciclos. Si lo hace, no hay solución (es decir, un subgrafo sin bordes, pero que contiene todos los bordes FIJOS).

Para gráficos dirigidos, es un poco más complicado. En este caso, cualquier componente del gráfico de bordes FIJOS debe ser un árbol. En el algoritmo similar a Dijkstra, solo las raíces de estos nodos deben ser candidatas para agregarse al árbol.

Answer 3

el problema está subestimado porque no ha especificado, por ejemplo, si el gráfico debe permanecer conectado o si desea eliminar un " pequeño " número de bordes no FIJOS para romper todos los ciclos, o si realmente necesita que se elimine el número mínimo global de bordes no FIJOS.

Si el gráfico no necesita permanecer conectado, solo atraviesa todos los bordes y elimina todos los no FIJOS. Eso elimina todos los ciclos que puede eliminar sin eliminar los bordes FIJOS.

Si desea que un algoritmo codicioso simple elimine bordes que son DFS puros, puede usar algo como esto SI el gráfico permanece conectado también cuando elimina algunos de los bordes NO FIJOS:

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]