Trouver tous les cycles dans un graphe dirigé

Question

Comment puis-je trouver (itérer sur) TOUS les cycles dans un graphe dirigé de/vers un nœud donné ?

Par exemple, je veux quelque chose comme ça :

A->B->A
A->B->C->A

mais pas : B->C->B

Answer 1

J'ai trouvé cette page dans mes recherches et comme les cycles ne sont pas les mêmes que les composants fortement connectés, j'ai continué à chercher et finalement, j'ai trouvé un algorithme efficace qui liste tous les cycles (élémentaires) d'un graphe dirigé. Il est de Donald B. Johnson et l'article peut être trouvé dans le lien suivant :

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Une implémentation java peut être trouvée dans :

http://normalisiert.de/code/java/elementaryCycles.zip

A Mathematica La démonstration de l'algorithme de Johnson se trouve à l'adresse suivante aquí La mise en œuvre peut être téléchargée à partir de la droite ( "Télécharger le code de l'auteur" ).

Note : En fait, il existe de nombreux algorithmes pour ce problème. Certains d'entre eux sont énumérés dans cet article :

http://dx.doi.org/10.1137/0205007

Selon l'article, l'algorithme de Johnson est le plus rapide.

Answer 2

Pour autant que je sache, la meilleure façon de résoudre ce problème serait d'utiliser l'algorithme de Tarjans (ou Gabows ou Kosaraju - voir le lien Wikipedia ci-dessous) pour trouver les composants fortement connectés d'un graphe. Les composantes fortement connectées et les cycles sont synonymes (mais pas exactement les mêmes).

Pour vous faire une meilleure idée, veuillez consulter les liens suivants :

1. Wikipedia sur l'algorithme de Tarjans : http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

2. Une explication rigoureuse : http://www.ics.uci.edu/~eppstein/161/960220.html

3. Autres liens intéressants :
   http://discuss.joelonsoftware.com/default.asp?design.4.249152.10
   http://forums.sun.com/thread.jspa?threadID=597673
   http://coding.derkeiler.com/Archive/General/comp.theory/2004-02/0468.html

4. Question similaire sur SO : Meilleur algorithme pour la détection des cycles dans un graphe dirigé

Maintenant que j'ai donné les liens, laissez-moi vous expliquer (après tout, ce sont les bonnes réponses et non les liens qui font de stackoverflow un endroit si formidable).

Quelques points à retenir (Tiré du lien 1) :
Deux sommets, A et B, sont fortement connectés s'il existe un chemin de A à B et un chemin de B à A.

L'ensemble de tous les sommets qui sont fortement connectés à un sommet donné forme une composante fortement connectée du graphe.

3. toute composante fortement connectée comportant plus d'un sommet contient au moins un cycle, à l'exception des composantes comportant un sommet. auto-boucle . (Merci pour l'aide Jens Schauder, bcorso)

Nous voulons d'une manière ou d'une autre réduire tous les sommets d'un cycle en un seul nœud dans un "arbre" (voir les liens). Tout cycle futur impliquant des sommets que nous avons déjà visités est regroupé dans le même nœud. Nous obtenons ainsi un arbre où chaque nœud est un composant fortement connecté.

Pour ce faire, il faut stocker deux bits d'information supplémentaires sur chaque nœud. Le nombre d'étapes que la recherche en profondeur prend pour atteindre ce nœud et le nombre minimum d'étapes que la recherche en profondeur prend pour atteindre n'importe quel nœud dans la composante fortement connectée de ce nœud (à partir des nœuds que nous avons vus jusqu'à présent).

Lorsque nous effectuons une recherche en profondeur sur le graphe principal, nous utilisons la structure de données secondaire pour nous aider à tester si deux nœuds sont "identiques" (dans la même composante fortement connectée, comme il s'avère) et ajouter correctement le nœud actuel à cette structure secondaire.

Algorithme
La question que vous vous posez n'est pas triviale à résoudre. Voici comment fonctionne l'algorithme de Tarjans-

La première chose à savoir est que vous devez faire un DFS. Je suppose qu'une pile est utilisée pour le faire. La DFS doit couvrir todo sommets du graphe.

2. chaque sommet v, doit être étiqueté avec deux valeurs, l'index et le lowval. L'index est simplement l'ordre dans lequel DFS visite le nœud. Le lowval est le minimum de l'index de v et de l'index du sommet le plus proche de v dans le DFS. Ce sommet est ensuite poussé sur la pile.

3. pour chaque sommet accessible à partir de v, reculer s'il n'est pas déjà dans la pile.

Pour un sommet v, dont lowval == index, extraire tous les éléments de la pile jusqu'à v lui-même et les imprimer comme une composante fortement connectée (cycle).

Je vais essayer d'implémenter cet algorithme. Je le posterai ici si je réussis et si vous le voulez à ce moment-là.

Editar
Cette question me laisse toujours perplexe - Cet algorithme est linéaire en V+E. Cependant, le nombre de cycles peut être exponentiel en V. Je suis assez perplexe quant à la façon dont cela peut être possible ? Je n'ai pas réussi à le comprendre moi-même.
Voir ce lien : http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf donnés par ShuggyCoUk et unknown(yahoo) pour plus de détails sur le nombre de cycles.

Answer 3

La recherche en profondeur avec retour en arrière devrait fonctionner ici. Gardez un tableau de valeurs booléennes pour savoir si vous avez déjà visité un nœud. Si vous n'avez plus de nouveaux nœuds à atteindre (sans toucher un nœud déjà visité), il suffit de revenir en arrière et d'essayer une autre branche.

Le DFS est facile à mettre en œuvre si vous disposez d'une liste d'adjacence pour représenter le graphe. Par exemple adj[A] = {B,C} indique que B et C sont les enfants de A.

Par exemple, le pseudo-code ci-dessous. "start" est le nœud à partir duquel vous commencez.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Appelez la fonction ci-dessus avec le nœud de départ :

visited = {}
dfs(adj,start,visited)

Answer 4

Tout d'abord, vous ne voulez pas vraiment essayer de trouver littéralement tous les cycles, car s'il y en a un, il y en a un nombre infini. Par exemple A-B-A, A-B-A-B-A etc. Ou encore, il est possible de réunir deux cycles pour former un cycle de type 8, etc. L'approche la plus sensée consiste à rechercher tous les cycles dits simples - ceux qui ne se croisent pas, sauf au point de départ/arrivée. Ensuite, si vous le souhaitez, vous pouvez générer des combinaisons de cycles simples.

L'un des algorithmes de base pour trouver tous les cycles simples dans un graphe dirigé est le suivant : Effectuer une traversée en profondeur de tous les chemins simples (ceux qui ne se croisent pas) dans le graphe. Chaque fois que le nœud actuel a un successeur sur la pile, un cycle simple est découvert. Il est constitué des éléments de la pile en commençant par le successeur identifié et en terminant par le sommet de la pile. La traversée en profondeur de tous les chemins simples est similaire à la recherche en profondeur mais vous ne marquez/enregistrez pas les nœuds visités autres que ceux actuellement sur la pile comme points d'arrêt.

L'algorithme de force brute ci-dessus est terriblement inefficace et, de plus, il génère de multiples copies des cycles. Il est cependant le point de départ de multiples algorithmes pratiques qui appliquent diverses améliorations afin d'améliorer les performances et d'éviter la duplication des cycles. J'ai été surpris de découvrir il y a quelque temps que ces algorithmes n'étaient pas facilement disponibles dans les manuels et sur le web. J'ai donc fait quelques recherches et j'ai implémenté 4 de ces algorithmes et 1 algorithme pour les cycles dans les graphes non orientés dans une bibliothèque Java open source ici : http://code.google.com/p/niographs/ .

BTW, puisque j'ai mentionné les graphes non orientés : l'algorithme pour ceux-ci est différent. Construisez un arbre couvrant et ensuite chaque arête qui ne fait pas partie de l'arbre forme un cycle simple avec certaines arêtes de l'arbre. Les cycles trouvés de cette façon forment ce qu'on appelle une base de cycles. Tous les cycles simples peuvent alors être trouvés en combinant 2 ou plusieurs cycles de base distincts. Pour plus de détails, voir par exemple ceci : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Answer 5

La réponse la plus simple à ce problème est probablement :

Effectuez une recherche en profondeur à partir de A. Lorsque vous visitez un nœud qui a un chemin vers A, vous avez obtenu votre cycle.

(Si vous n'êtes pas dans un graphe dirigé.)