Cycle dans un graphe
Rappel : Cycle
Un cycle est un chemin simple, non trivial qui commence et termine au même sommet.
Des cycles dans python
Imaginons que plutôt que choisir les représentations proposées en cours pour les graphes, nous avons choisi une représentation plus naturelle.
Nous avons donc la définition suivante.
def Sommet:
def __init__(self, aretes: List[Arete]):
self.aretes = aretes
def Arete:
def __init__(self, source: Sommet, destination: Sommet):
self.src = source
self.dst = destination
Cette représentation semble intuitive, mais si ce n'est celle que l'on a utilisée, c'est qu'elle présente un problème.
En effet quand on y regarde de plus proche, pour pouvoir définir les sommets il nous faut les arêtes, mais pour définir les arêtes il nous faut les sommets.
On arrive donc sur un serpent qui se mord la queue.
Dans notre cas, il est assez facile de le détecter. Mais sur de gros projet, avec des centaines de fichier, le cycle de dépendance peut-être beaucoup plus long et difficile à repérer.
C'est pourquoi, python passe beaucoup de temps à détecter ces dépendances cycliques. Mais comment faire ?
Fondamental : Détecter les cycles dans un graphe non-orienté
Pour détecter les cycles dans un graphe non-orienté, il suffit de faire un parcours (en largeur ou en profondeur) et de s’arrêter dès qu'on voit pour la deuxième fois un sommet.
En effet si on voit deux fois le même sommet alors on a deux chemins pour y aller. En les mettant bout-à-bout, on obtient un cycle.
Fondamental : Détecter les cycles dans un graphe orienté
Pour détecter les cycles dans un graphe orienté, c'est un peu plus compliqué. En effet, la technique précédente ne fonctionne plus, les deux chemins pourraient ne pas être inversibles.
Pour détecter les cycles dans un graphe orienté, on va continuer à faire un parcours, mais ici, on s’arrête si on rencontre un sommet qui est l'ancêtre du sommet actuel.