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

Question

J'ai un graphe non dirigé avec Vertex V et Edge E . Je cherche un algorithme pour identifier toutes les bases de cycle de ce graphique.

Je pense que l'algorithme de Tarjans est un bon début. Mais ma référence , elle concerne la recherche de tous les cycles . , pas base de cycle (qui, par définition, est le cycle qui ne peut pas être construit par l'union d'autres cycles).

Par exemple, consultez le graphique ci-dessous:

Donc, 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 l'intuition de Brian est active, mais une proposition encore plus solide tient: chaque bord qui ne fait pas partie de l'arborescence minimale ajoute exactement un nouveau "cycle de base".

Pour voir cela, 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 ajouter une notation;) Appelez le graphe d'origine G, le graphe avant d'ajouter E G ', et le graphe après l'ajout de E G' '. Nous devons donc savoir comment le & compte; cycle de base compte " changer de G 'à G' '.

L'ajout de E doit fermer au moins un cycle (sinon, E serait dans le MST de G en premier lieu). Donc, évidemment, il faut ajouter au moins un "cycle de base". aux existants dans G '. Mais en ajoute-t-il plus d'un?

Il ne peut pas en ajouter plus de deux, car aucun bord ne peut être membre de plus de deux cycles de base. Mais si E est membre de deux cycles de base, le "syndicat" de ces deux cycles de base doit avoir été un cycle de base en G ', nous constatons donc à nouveau que le changement du nombre de cycles est toujours égal à un.

Donc, pour chaque bord qui n'est pas dans MST, vous obtenez un nouveau cycle de base. Donc, le "décompte" la partie est simple. Trouver toutes les arêtes pour chaque cycle de base est un peu plus compliqué, mais 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 rechercher tous les cycles de base d'un graphique (les cycles de base définis en bas). Les hypothèses sont que vous savez comment:

• recherche l'arbre couvrant minimal d'un graphe (mst [G])
• trouvez la différence entre deux listes (arêtes \ mst [G])
• trouver une intersection de deux listes
• trouver le chemin entre deux sommets sur un MST
• divisez un cycle en deux en y ajoutant un bord supplémentaire (la fonction de division)

Et cela suit principalement la discussion ci-dessus. Vous avez deux cas pour chaque bord qui ne fait pas partie du MST: soit il crée un cycle de base complètement nouveau, soit il divise un cycle existant en deux. Pour suivre l’un des deux cas, nous suivons tous les cycles de base dont un sommet fait partie (en utilisant le dictionnaire des cycles).

Answer 2

Pour commencer, je commencerais par examiner 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 de bords qui ne sont PAS dans le MST ....

Answer 3

Ce qui suit est mon code non testé actuel pour rechercher 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;
}

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

cycles[v] = []

ne peut pas être un dictionnaire indexé de sommets de listes d'arêtes. À mon avis, il doit s'agir d'un dictionnaire indexé de sommets de ensembles de listes d'arêtes.

Et pour ajouter une précision:

for vertex on cycle_to_split:

cycle-to-split est probablement une liste d'arêtes ordonnée . Par conséquent, pour le parcourir par les sommets, vous devez le convertir en un ensemble de sommets. L'ordre ici est négligeable, donc c'est un algorithme très simple.

Je le répète, il s'agit de code non testé et non complet , mais constitue un progrès. Cela nécessite toujours une structure de graphe appropriée (j'utilise une liste d'incident) et de nombreux algorithmes de graphes que vous pouvez trouver dans des manuels comme Cormen. Je ne pouvais pas trouver FindPath () et SplitCycle () dans les manuels et il est très difficile de les coder en temps linéaire de nombre d'arêtes + de sommets dans le graphique. Les signaler ici lorsque je les testerai.

Merci beaucoup Oggy!

Answer 4

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

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