Algoritmi per identificare tutte le basi del ciclo in un grafico non diretto

Question

Ho un grafico non indirizzato con Vertex V e Edge E . Sto cercando un algoritmo per identificare tutte le basi del ciclo in quel grafico.

Penso che Algoritmo di Tarjans è un buon inizio. Ma il riferimento che ho riguarda la ricerca di tutti i cicli , non base di cicli (che, per definizione è il ciclo che non può essere costruito dall'unione di altri cicli).

Ad esempio, dai un'occhiata al grafico qui sotto:

Quindi, un algoritmo sarebbe utile. Se esiste un'implementazione esistente (preferibilmente in C #), è ancora meglio!

Answer 1

Da quello che posso dire, non solo è il punto di intuizione di Brian, ma una proposizione ancora più forte vale: ogni spigolo che non si trova nell'albero di spanning minimo aggiunge esattamente un nuovo "ciclo di base".

Per vedere questo, vediamo cosa succede quando aggiungi un bordo E che non è nell'MST. Facciamo il modo matematico preferito per complicare le cose e aggiungere qualche notazione;) Chiama il grafico originale G, il grafico prima di aggiungere E G 'e il grafico dopo aver aggiunto E G' '. Quindi dobbiamo scoprire in che modo il ciclo "base conta" " cambia da G 'a G' '.

L'aggiunta di E deve chiudere almeno un ciclo (altrimenti E sarebbe in primo luogo nel MST di G). Quindi ovviamente deve aggiungere almeno un "ciclo base" a quelli già esistenti in G '. Ma ne aggiunge più di uno?

Non può aggiungere più di due, poiché nessun bordo può essere membro di più di due cicli di base. Ma se E è un membro di due cicli di base, allora l '"unione" di questi due cicli di base deve essere stato un ciclo di base in G ', quindi di nuovo otteniamo che il cambiamento nel numero di cicli è ancora uno.

Ergo, per ogni fronte non in MST si ottiene un nuovo ciclo di base. Quindi il "conteggio" la parte è semplice. Trovare tutti i bordi per ogni ciclo di base è un po 'più complicato, ma seguendo il ragionamento sopra, penso che questo potrebbe farlo (in 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)

Modifica : il codice dovrebbe trovare tutti i cicli di base in un grafico (i cicli di base impostati in basso). I presupposti sono che tu sappia come:

• trova l'albero di spanning minimo di un grafico (mst [G])
• trova la differenza tra due elenchi (edge ??\ mst [G])
• trova un'intersezione di due liste
• trova il percorso tra due vertici su un MST
• dividi un ciclo in due aggiungendo un ulteriore vantaggio (la funzione di divisione)

E segue principalmente la discussione sopra. Per ogni fronte non presente nell'MST, sono disponibili due casi: o porta un ciclo di base completamente nuovo o divide uno esistente in due. Per tracciare quale dei due è il caso, seguiamo tutti i cicli di base di cui fa parte un vertice (usando il dizionario dei cicli).

Answer 2

dalla parte superiore della mia testa, vorrei iniziare guardando qualsiasi algoritmo di Spanning Tree minimo (Prim, Kruskal, ecc.). Non ci possono essere più cicli di base (se ho capito bene) dei bordi che NON si trovano nel MST ....

Answer 3

Quello che segue è il mio vero codice non testato C # per trovare tutti questi "cicli 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 codice era molto buono e chiaro ma sono abbastanza sicuro che contenga un errore, o sono io che non capisco il tuo codice pseudo python:)

cycles[v] = []

non può essere un dizionario indicizzato vertice di elenchi di bordi. A mio avviso, deve essere un dizionario indicizzato vertice di set di liste di bordi.

E, per aggiungere una precisazione:

for vertex on cycle_to_split:

Il

ciclo da dividere è probabilmente un elenco di spigoli ordinati , quindi per iterarlo attraverso i vertici devi convertirlo in un insieme di vertici. L'ordine qui è trascurabile, quindi è un algoritmo molto semplice.

Ripeto, questo è non testato e incompleto , ma è un passo avanti. Richiede ancora una struttura grafica adeguata (utilizzo un elenco di incidenti) e molti algoritmi grafici che puoi trovare nei libri di testo come Cormen. Non sono riuscito a trovare FindPath () e SplitCycle () nei libri di testo e sono molto difficili da codificare in tempo lineare di numero di bordi + vertici nel grafico. Li segnalerò qui quando li metterò alla prova.

Grazie mille Oggy!

Answer 4

Il modo standard per rilevare un ciclo consiste nell'utilizzare due iteratori: per ogni iterazione, uno si sposta in avanti di un passaggio e degli altri due. Se dovesse esserci un ciclo, a un certo punto si indicheranno l'un l'altro.

Questo approccio potrebbe essere esteso per registrare i cicli così trovati e andare avanti.