Algorithmen zur Identifizierung des Zyklus Bases Alle in einem ungerichteten Graphen

Question

Ich habe einen ungerichteten Graphen mit Vertex V und Edge-E. Ich suche nach einem Algorithmus alle Zyklus Basen in diesem Diagramm zu identifizieren.

Ich denke, Tarjans Algorithmus ist ein guter Anfang. Aber die Referenz ich alle der Zyklen über die Suche nach haben wird , nicht Zyklus Basis (die per definitionem den Zyklus ist, die durch die Vereinigung von anderen Zyklen nicht aufgebaut werden kann).

Nehmen wir zum Beispiel einen Blick auf die Grafik unten:

So würde ein Algorithmus hilfreich sein. Wenn es eine vorhandene Implementierung (vorzugsweise in C #), ist es noch besser!

Answer 1

Von dem, was ich sagen kann, ist nicht nur Brians krümmen Stelle auf, aber ein noch stärkerer Satz gilt: jede Kante, die nicht im Minimum Spanning Tree ist fügt genau eine neuen „Basiszyklus“.

Um dies zu sehen, mal sehen, was passiert, wenn Sie einen Rand E hinzuzufügen, die nicht in der MST ist. Lassen Sie sich die Lieblingsmathe Art und Weise tun, um die Dinge zu komplizieren und eine Notation hinzufügen;) Rufen Sie das ursprüngliche Graphen G, die Grafik vor dem Hinzufügen von E G‘und das Diagramm nach der Zugabe von E G‚‘. Also müssen wir herausfinden, wie funktioniert die „Basiszykluszahl“ Änderung von G‘G‚‘.

E Hinzufügen muss mindestens einen Zyklus schließen (sonst E in der MST von G in erster Linie sein würde). So offensichtlich muss es mindestens einen „Basiszyklus“ zu den bereits bestehenden in G‘hinzuzufügen. Aber fügt es mehr als ein?

Es kann nicht mehr als zwei hinzufügen, da keine Kante Mitglied von mehr als zwei Basiszyklen sein kann. Aber wenn E ein Mitglied von zwei Basiszyklen ist, dann ist die „Vereinigung“ dieser beiden Grundzyklen must've ein Basiszyklus in G‘gewesen, so wieder bekommen wir, dass die Veränderung der Anzahl der Zyklen ist nach wie vor ein.

Ergo, für jede Kante nicht in MST erhalten Sie einen neuen Basiszyklus. So ist der „count“ Teil ist einfach. Das Finden all Kanten für jeden Basiszyklus ist ein wenig komplizierter, aber oben im Anschluss an die Argumentation, ich denke, das könnte es tun (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)

Bearbeiten : Der Code sollte alle Basiszyklen in einem Diagramm finden (die base_cycles am Boden befestigt). Die Annahmen sind, dass Sie wissen, wie Sie:

• findet den minimalen Spannbaum eines Graphen (mst [G])
• Den Unterschied zwischen zwei Listen (Kanten \ mst [G])
• eine Kreuzung von zwei Listen finden
• finden Sie den Pfad zwischen zwei Knoten auf einem MST
• Split einen Zyklus in zwei durch einen zusätzlichen Vorteil ihm hinzufügen (die Split-Funktion)

Und es folgt in erster Linie die Diskussion darüber. Für jede Kante nicht in der MST, haben Sie zwei Fälle: Entweder er bringt einen völlig neuen Basiszyklus, oder es teilt mir eine vorhandene in zwei Teilen. welche der beiden zu verfolgen der Fall ist, wir alle Basiszyklen verfolgen, die eine Ecke ist ein Teil (die Zyklen Wörterbuch verwendet wird).

Answer 2

aus der Spitze von meinem Kopf, würde ich durch einen Blick auf jedem Minimum Spanning Tree-Algorithmus (Prim, Kruskal, etc.) starten. Es kann nicht mehr Basiszyklen (Wenn ich es richtig verstanden hat) als Kanten, die nicht im MST sind ....

Answer 3

Hier finden Sie mein eigentlicher ungetestet C # -Code alle diese "Basiszyklen" zu finden:

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;
}

Oggys Code war sehr gut und klar , aber ich bin mir ziemlich sicher, dass es einen Fehler enthält, oder es ist mir, dass Ihre Pseudo-python-Code nicht verstehen:)

cycles[v] = []

kann nicht eine Ecke sein Wörterbuch der Listen von Kanten indiziert. Meiner Meinung nach, muss es eine Vertex-Wörterbuch von Sätzen von Listen indiziert wird von Kanten.

Und hinzufügen, um eine precisation:

for vertex on cycle_to_split:

Zyklus-zu-split ist wahrscheinlich ein bestellt Liste von Kanten, so dass es durch Ecken iterieren Sie es in einer Menge von Knoten zu konvertieren. Bestellen Sie hier vernachlässigbar ist, so ist es eine sehr einfache alghoritm.

Ich wiederhole, das ist ungetestet und uncomplete Code, ist aber ein Schritt nach vorn. Es erfordert noch eine richtige Graphenstruktur (i verwenden, um eine incidency Liste) und viele Graph alghoritms Sie in Text Bücher wie Cormen finden. Ich war nicht in der Lage FindPath () und SplitCycle () in Text Bücher zu finden, und bin sehr schwer, sie in linearer Zeit der Anzahl der Kanten zu codieren + Ecken in der Grafik. Wird sie hier berichten, wenn ich sie testen.

Vielen Dank Oggy!

Answer 4

Der Standard Weg, um einen Zyklus zu erkennen ist zwei Iteratoren verwenden - für jede Iteration, bewegt man sich einen Schritt nach vorn und die beiden anderen. Sollte es ein Zyklus sein, werden sie an einem gewissen Punkt Punkt zueinander stehen.

Dieser Ansatz könnte erweitert werden, die Zyklen so gefunden zu erfassen und bewegen.