Algorithmes pour identifier toutes les bases de cycle dans un graphique non dirigé

Question

J'ai un graphique non orienté avec Vertex V et Edge E. Je cherche un algorithme pour identifier toutes les bases du cycle dans ce graphique. Je pense que Tarjans algorithm est un bon début. Mais je the reference est de trouver tous les cycles, non base du cycle (qui, by definition est le cycle qui ne peut être construit par l'union d'autres cycles).

Par exemple, jetez un oeil au graphique ci-dessous:

Ainsi, un algorithme serait utile. S'il existe une implémentation existante (de préférence en C#), c'est encore mieux!

Answer 1

D'après ce que je peux dire, non seulement Brian a-t-il une idée en tête, mais une proposition encore plus forte tient: chaque arête qui ne se trouve pas dans l'arbre couvrant minimum ajoute exactement un nouveau "cycle de base".

Pour voir ceci, voyons ce qui se passe lorsque vous ajoutez un bord E qui n'est pas dans le MST. Faisons la méthode mathématique préférée pour compliquer les choses et ajoutons des notations;) Appelez le graphe original G, le graphe avant d'ajouter E G ', et le graphe après avoir ajouté E G' '. Nous devons donc savoir comment le «compte du cycle de base» passe de G 'à G' '.

Ajout de E doit fermer au moins un cycle (sinon E serait dans le MST de G en premier lieu). Alors évidemment il faut ajouter au moins un "cycle de base" à ceux déjà existants dans G '. Mais en ajoute-t-il plus d'un?

Il ne peut pas en ajouter plus de deux, car aucune arête ne peut faire partie de plus de deux cycles de base. Mais si E est un membre de deux cycles de base, alors l '"union" de ces deux cycles de base doit avoir été un cycle de base dans G', de sorte que nous obtenons que le changement du nombre de cycles est toujours un.

Ergo, pour chaque arête non en MST, vous obtenez un nouveau cycle de base. La partie "count" est donc simple. Trouver tous les bords pour chaque cycle de base est un peu plus délicat, mais après le raisonnement ci-dessus, je pense que cela pourrait le faire (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) 

Modifier: le code doit trouver toute la base cycles dans un graphique (l'ensemble base_cycles en bas).Les hypothèses sont que vous savez comment:

• trouver l'arbre couvrant minimal d'un graphe (mst [G])
• trouver la différence entre les deux listes (arêtes \ mst [G])
• trouver une intersection de deux listes
• trouver le chemin entre deux sommets sur une MST
• diviser un cycle en deux en ajoutant un avantage supplémentaire à elle (la fonction split)

Et il suit principalement la discussion ci-dessus. Pour chaque arête qui n'est pas dans le MST, vous avez deux cas: soit il apporte un cycle de base complètement nouveau, soit il divise un existant en deux. Pour savoir lequel des deux est le cas, nous suivons tous les cycles de base dont un sommet fait partie (en utilisant le dictionnaire des cycles).

Answer 2

La méthode standard pour détecter un cycle consiste à utiliser deux itérateurs - pour chaque itération, on avance d'un pas et les deux autres. S'il y a un cycle, ils se rapprocheront à un moment donné.

Cette approche pourrait être étendue pour enregistrer les cycles ainsi trouvés et passer à autre chose.

Answer 3

Je commencerais par regarder n'importe quel algorithme Minimum Spanning Tree (Prim, Kruskal, etc.). Il ne peut y avoir plus de cycles de base (si je comprends bien) que d'arêtes qui ne sont pas dans le MST ....

Answer 4

Ce qui suit est mon réelle non testé code C# pour trouver tous ces "cycles 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; 
} 

Code Oggy's était très bon et clair mais je suis sûr qu'il contient un erreur, ou c'est moi qui ne comprends pas votre pseudo code python :)

cycles[v] = [] 

ne peut pas être une diction indexée de sommet ary de listes d'arêtes. À mon avis, il doit être un dictionnaire indexé par le vertex de ensembles de listes des bords.

Et, pour ajouter un precisation:

for vertex on cycle_to_split: 

cycle à-split

est probablement une liste ordonnée des bords ainsi itérer par des sommets que vous devez le convertir dans un ensemble de sommets. L'ordre ici est négligeable, donc c'est un algoritme très simple.

je le répète, c'est non testé et uncomplete Code, mais est un pas en avant. Il nécessite encore une bonne structure graphique (j'utilise une liste d'ouverture) et de nombreux algorytes graphiques que vous pouvez trouver dans les livres de texte comme Cormen. Je n'ai pas pu trouver FindPath() et SplitCycle() dans les manuels, et sont très difficile de les coder en temps linéaire du nombre d'arêtes + sommets dans le graphique. Les rapporterai ici quand je les testerai.

Merci beaucoup Oggy!