Algorytmy identyfikujące wszystkie podstawy cyklu w niezorientowanym grafie

Question

Mam nieukierunkowany wykres z wierzchołkami V i Edge E. Szukam algorytmu do identyfikacji wszystkich baz cyklu na tym wykresie.

Myślę, że Tarjans algorithm to dobry początek. Ale the reference mam jest o znalezienie wszystkich cykli, nie baza cykl (co by definition jest cykl, który nie może być wykonana przez Unię innych cykli).

Na przykład spojrzeć na poniższy wykres:

więc algorytm byłoby pomocne. Jeśli istnieje istniejąca implementacja (najlepiej w języku C#), jest jeszcze lepiej!

Answer 1

Z tego, co wiem, nie tylko punkt przeczucia Briana, ale jeszcze silniejsza propozycja hold: każda krawędź, która nie znajduje się w minimalnym drzewie opinającym, dodaje dokładnie jeden nowy "cykl bazowy".

Aby to zobaczyć, zobaczmy, co się stanie, gdy dodasz krawędź E, której nie ma w MST. Zróbmy ulubiony sposób matematyki, aby komplikować rzeczy i dodać notację;) Wywołaj oryginalny wykres G, wykres przed dodaniem E G ', a wykres po dodaniu E G' '. Musimy więc dowiedzieć się, w jaki sposób zmienia się "liczba cykli bazowych" z G 'na G' '.

Dodanie E musi zamknąć co najmniej jeden cykl (w przeciwnym razie E byłoby w MST z G w pierwszej kolejności). Więc oczywiście musi dodać przynajmniej jeden "podstawowy cykl" do już istniejących w G '. Ale czy dodaje więcej niż jeden?

Nie można dodać więcej niż dwa, ponieważ żadna krawędź nie może być członkiem więcej niż dwóch cykli bazowych. Ale jeśli E jest członkiem dwóch podstawowych cykli, to "zjednoczenie" tych dwóch podstawowych cykli musiało być podstawowym cyklem w G ', więc znowu otrzymujemy, że zmiana liczby cykli jest wciąż jedna.

Ergo, dla każdej krawędzi nie w MST otrzymujesz nowy cykl podstawowy. Więc część "liczenia" jest prosta. Znalezienie wszystkie krawędzie dla każdego cyklu bazowej jest trochę trudniejsze, ale następujące rozumowanie powyżej, myślę, że to może to zrobić (w 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) 

Edit: kod powinien znaleźć wszystkie bazy cykle na wykresie (base_cycles ustawione na dole).Założenia są takie, że wiesz, jak:

• znaleźć minimalne drzewo rozpinające grafu (MST [g])
• znaleźć różnicę pomiędzy dwoma listami (krawędzie \ MST [g])
• find skrzyżowanie dwóch listach
• znaleźć drogę między dwoma wierzchołkami na MST
• podzielić na dwie części cyklu poprzez dodanie do niej krawędzi (funkcja split)

I wynika głównie z powyższej dyskusji. Dla każdej krawędzi nie w MST masz dwa przypadki: albo przynosi całkowicie nowy cykl podstawowy, albo dzieli istniejący na dwa. Aby śledzić, który z tych dwóch przypadków dotyczy, śledzimy wszystkie cykle bazowe, których częścią jest wierzchołek (używając słownika cykli).

Answer 2

Standardowym sposobem wykrywania cyklu jest użycie dwóch iteratorów - w każdej iteracji jeden porusza się o jeden krok, a drugi o dwa. Jeśli będzie jakiś cykl, w pewnym momencie nawzajem się nawzajem.

Takie podejście można rozszerzyć, aby zapisać tak odkryte cykle i przejść dalej.

Answer 3

z góry mojej głowy, zacznę od patrzenia na algorytm minimalnego drzewa opinającego (Prim, Kruskal, itp.). Nie może być więcej cykli bazowych (jeśli rozumiem to poprawnie) niż krawędzie, które NIE są w MST ....

Answer 4

Poniżej moja rzeczywista niesprawdzone kod C#, aby znaleźć wszystkie te „cykle bazowych”:

kod

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 był bardzo dobre i jasne ale jestem pewien, że zawiera błąd, albo ja nie rozumiem Twojego pseudo kod Pythona :)

cycles[v] = [] 

nie może być wierzchołek indeksowane dykcję lista list krawędzi. Moim zdaniem, musi to być słownik indeksowanych wierzchołków zestawów list krawędzi.

A, aby dodać precisation:

for vertex on cycle_to_split: 

cykl do podziału jest prawdopodobnie nakazał lista krawędziach tak iteracyjne go przez wierzchołki trzeba przekształcić go w zbiorze wierzchołków. Zamów tutaj jest znikomy, więc jest to bardzo prosta alghoritm.

Powtarzam, to jest niesprawdzone i uncomplete kod, ale jest krokiem naprzód. Nadal wymaga odpowiedniej struktury wykresu (używam listy incydentów) i wielu algorytmów wykresów, które można znaleźć w podręcznikach tekstowych, takich jak Cormen. Nie mogłem znaleźć FindPath() i SplitCycle() w książkach tekstowych i są one trudne do zakodowania ich w liniowym czasie liczby krawędzi + wierzchołków na wykresie. Powiadomię ich tutaj, kiedy je przetestuję.

Wielkie dzięki Oggy!