Algoritmos para identificar todas las bases de los ciclos en un gráfico no dirigido

Question

Tengo un gráfico no dirigido con Vertex V y Edge E . Estoy buscando un algoritmo para identificar todas las bases de los ciclos en esa gráfica.

Creo que algoritmo de Tarjans es un buen comienzo. Pero la referencia que tengo trata de encontrar todos los cycles , no cycle base (que, por definición, es el ciclo que no puede construirse mediante la unión de otros ciclos).

Por ejemplo, eche un vistazo al siguiente gráfico:

Por lo tanto, un algoritmo sería útil. Si hay una implementación existente (preferiblemente en C #), ¡es aún mejor!

Answer 1

Por lo que puedo decir, no solo está el punto de corazonada de Brian, sino que se mantiene una proposición aún más fuerte: cada borde que no está en el árbol de expansión mínimo agrega exactamente un nuevo "ciclo base".

Para ver esto, veamos qué sucede cuando agregas un borde E que no está en el MST. Hagamos la forma matemática favorita para complicar las cosas y agregar alguna notación;) Llame al gráfico G original, al gráfico antes de agregar E G 'y al gráfico después de agregar E G' '. Por lo tanto, debemos averiguar cómo cuenta el " ciclo base " cambiar de G 'a G' '.

Agregar E debe cerrar al menos un ciclo (de lo contrario, E estaría en el MST de G en primer lugar). Así que obviamente debe agregar al menos un " ciclo base " a los ya existentes en G '. ¿Pero añade más de uno?

No puede agregar más de dos, ya que ningún borde puede ser miembro de más de dos ciclos básicos. Pero si E es miembro de dos ciclos básicos, entonces " union " de estos dos ciclos de base debe haber sido un ciclo de base en G ', por lo que nuevamente obtenemos que el cambio en el número de ciclos sigue siendo uno.

Ergo, por cada borde que no esté en MST, obtendrá un nuevo ciclo base. Así que el " cuenta " La parte es simple. Encontrar todos los bordes para cada ciclo básico es un poco más complicado, pero siguiendo el razonamiento anterior, creo que esto podría hacerlo (en pseudo-Python):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

Editar : el código debe encontrar todos los ciclos básicos en un gráfico (los ciclos base establecidos en la parte inferior). Los supuestos son que usted sabe cómo:

• encuentre el árbol de expansión mínimo de un gráfico (mst [G])
• encuentra la diferencia entre dos listas (bordes \ mst [G])
• encuentra una intersección de dos listas
• encuentre la ruta entre dos vértices en un MST
• divide un ciclo en dos agregándole un borde adicional (la función de división)

Y sigue principalmente la discusión anterior. Para cada borde que no está en el MST, tiene dos casos: trae un ciclo base completamente nuevo o divide uno existente en dos. Para rastrear cuál de los dos es el caso, rastreamos todos los ciclos básicos de los que forma parte un vértice (usando el diccionario de ciclos).

Answer 2

fuera de la parte superior de mi cabeza, comenzaría observando cualquier algoritmo de árbol de expansión mínima (Prim, Kruskal, etc.). No puede haber más ciclos de base (si lo entiendo correctamente) que los bordes que NO están en el MST ...

Answer 3

El siguiente es mi código no probado C # real para encontrar todos estos " ciclos básicos " ;:

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy's muy bueno y claro pero estoy bastante seguro de que contiene un error, o soy yo quien no entiende su código de pseudo python:)

cycles[v] = []

no puede ser un diccionario indexado de vértices de listas de bordes. En mi opinión, tiene que ser un diccionario de vértice indexado de conjuntos de listas de bordes.

Y, para agregar una precisión:

for vertex on cycle_to_split:

ciclo-a-división es probablemente una lista ordenada de bordes, por lo que para iterarla a través de vértices, debe convertirla en un conjunto de vértices. El orden aquí es insignificante, por lo que es un algoritmo muy simple.

Repito, esto es un código no probado y incompleto , pero es un paso adelante. Todavía requiere una estructura gráfica adecuada (uso una lista de incidencias) y muchos algoritmos gráficos que puede encontrar en libros de texto como Cormen. No pude encontrar FindPath () y SplitCycle () en los libros de texto, y son muy difíciles de codificar en el tiempo lineal del número de bordes + vértices en el gráfico. Los reportaré aquí cuando los probaré.

¡Muchas gracias Oggy!

Answer 4

La forma estándar de detectar un ciclo es usar dos iteradores: para cada iteración, uno avanza un paso y los otros dos. En caso de que haya un ciclo, en algún punto se apuntarán entre sí.

Este enfoque podría extenderse para registrar los ciclos encontrados y seguir adelante.