Algoritmos para identificar todas las bases de ciclo 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 ciclo en ese gráfico.

Creo que Tarjans algorithm es un buen comienzo. Pero the reference que tengo es sobre la búsqueda de todos los ciclos , no base de ciclo (que, by definition es el ciclo que no puede ser construido por unión de otros ciclos).

Por ejemplo, echar un vistazo a la siguiente gráfica:

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

Answer 1

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

Para ver esto, veamos qué sucede cuando agrega un borde E que no está en el MST. Hagamos la forma matemática favorita para complicar las cosas y agregar algo de notación;) Llame al gráfico original G, al gráfico antes de agregar E G ', y al gráfico después de agregar E G' '. Entonces, necesitamos averiguar cómo cambia el "recuento del ciclo base" 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 agrega 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 un miembro de dos ciclos de base, entonces la "unión" de estos dos ciclos de base debe haber sido un ciclo de base en G ', así que de nuevo obtenemos que el cambio en el número de ciclos sigue siendo uno.

Ergo, para cada borde no en MST se obtiene un nuevo ciclo de base. Entonces la parte "contar" es simple. Encontrar todos los bordes para cada ciclo de base es un poco más difícil, 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 toda la base ciclos en un gráfico (los base_cycles establecidos en la parte inferior).Los supuestos son que usted sabe cómo:

• encontrar el árbol de expansión mínimo de un grafo (MST [G])
• ver la diferencia entre dos listas (bordes \ MST [G])
• hallazgo una intersección de dos listas
• encontrar el camino entre dos vértices en un MST
• dividir un ciclo en dos por la adición de un punto que la hace (la función split)

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

Answer 2

La forma estándar de detectar un ciclo es usar dos iteradores: para cada iteración, uno avanza un paso y los otros dos. Si hubiera un ciclo, en algún momento se señalarán entre sí.

Este enfoque podría ampliarse para registrar los ciclos encontrados y avanzar.

Answer 3

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

Answer 4

La siguiente es mi real no probado el código # C a encontrar todos estos "ciclos de base":

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 código era muy bien y clara pero estoy bastante seguro de que contiene una de error, o mí que no entiende su seudo código Python :) es

cycles[v] = [] 

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

Y, para añadir un precisation:

for vertex on cycle_to_split: 

dividida ciclo-a-es, probablemente, una lista ordenada de bordes para iterar a través de los vértices que hay que convertirlo en un conjunto de vértices. El orden aquí es insignificante, por lo que es una alghoritm muy simple.

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

Muchas gracias Oggy!