Détection de circuits

La résolution du problème passant par la garantie qu'il n'y a aucun circuit, il est nécessaire de disposer d'un algorithme permettant de les retrouver dans la trace d'exécution. Il est possible de procéder ainsi[4] :

1. $S \leftarrow \{o_{j}^{1}, o_{i}^{1}\}$;
2. $B \leftarrow \emptyset$;
3. tant que ( $S \not= \emptyset$);
4. $v \leftarrow k \in S$;
5. s'il n'existe pas de sommet $v^{\prime}$ tel que $v^{\prime}$ est un prédécesseur de $v$, et $v^{\prime}$ est non marqué;
6. on marque $v$;
7. $S \leftarrow S \cup \{v^{\prime\prime} \mid v^{\prime\prime}\ est\ un\ successeur\ de\ v\}$;
8. $B \leftarrow B \backslash \{v\}$;
9. sinon $B \leftarrow B \cup \{v\}$;
10. fin si;
11. $S \leftarrow S \backslash \{v\}$;
12. fin tant que;
13. Les sommets de $B$ sont impliqués dans un circuit.

On remarque qu'il peut y avoir plusieurs occurrences d'un même sommet dans $S$ ou dans $B$. La ligne $7$ ajoute $v$ dans $S$ même s'il s'y trouve déjà. La ligne $11$ n'enlève qu'une occurrence de $v$ de $S$. Par contre, l'instruction $9$ n'ajoute $v$ dans $B$ que s'il ne s'y trouve déjà, et l'instruction de la ligne $8$ élimine le seul $v$ de $B$ s'il s'y trouve.

Le principe de cet algorithme est le suivant : on marque un sommet si tous ses prédécesseurs sont marqués, les sommets non marquables sont impliqués dans un circuit.