Aller au contenu

Applications (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Algorithmes sur les graphes non orientés⚓︎

Exploration d'un labyrinthe et existence d'un chemin entre deux sommets d'un graphe⚓︎

Exercice 15

💻 Saisir ses réponses sur Capytale

On représente un labyrinthe par un rectangle de \(n\) lignes et \(m\) colonnes constitué de \(n \times m\) cases qui sont séparées ou non par un mur. Chaque case est repérée par sa colonne et sa ligne : par exemple la case \((0, 4)\) est en colonne \(0\) et ligne \(4\).

alt

Source : Yann Langlais licence https://creativecommons.org/licenses/by-sa/3.0/deed.fr dans article Wikipedia

On peut alors modéliser le labyrinthe par un graphe dont les sommets sont les cases et les arcs représentent un passage (absence de mur) possible entre deux cases adjacentes.

alt

Source : Yann Langlais licence https://creativecommons.org/licenses/by-sa/3.0/deed.fr dans article Wikipedia

Dans cet exercice, on considère le labyrinthe ci-dessus qui est un labyrinthe parfait :

  • il existe un chemin entre deux cases/sommets quelconques : le graphe du labyrinthe est connexe
  • le chemin reliant deux cases/sommets est unique car on ne peut pas tourner en rond autour d'un ilôt, le graphe ne contient pas de cycle : il est acyclique.

Un graphe connexe acyclique est un arbre (mais il n'a pas de racine contrairement aux structures arborescentes également au programme).

On donne ci-dessous un script Python avec :

  • une classe Graphe pour représenter un graphe non orienté par dictionnaires de listes d'adjacences.
  • une classe File
  • une classe Pile
  • une représentation du labyrinthe ci-dessus dans une variable globale laby_wikipedia
  • une fonction explo_laby_bfs qui prend en paramètre un sommet debut d'entrée dans le labyrinthe, un sommet fin de sortie du labyrinthe et le labyrinthe laby (représentant un labyrinthe parfait) et qui renvoie la liste dans l'ordre de découverte des couples (sommet découvert, distance à debut) (ici ((colonne, ligne), distance) )
  • une fonction explo_laby_dfs qui prend en paramètre un sommet debut d'entrée dans le labyrinthe, un sommet fin de sortie du labyrinthe et le labyrinthe laby (représentant un labyrinthe parfait) et qui renvoie la liste dans l'ordre de découverte des sommets découverts (ici (colonne, ligne) )

###
from collections import dequebksl-nlbksl-nlclass Graphe:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, listepy-undsommets):bksl-nl """bksl-nl Crée une représentation de graphe non orienté à partir d'une liste de sommetsbksl-nl """bksl-nl self.listepy-undsommets = listepy-undsommetsbksl-nl self.adjacents = {sommet : [] for sommet in listepy-undsommets}bksl-nl bksl-nl def sommets(self):bksl-nl """bksl-nl Renvoie une liste des sommetsbksl-nl """bksl-nl return self.listepy-undsommetsbksl-nl bksl-nl def ajoutepy-undarc(self, sommetA, sommetB):bksl-nl """bksl-nl Ajoute dans la représentation de graphe l'arc sommetA - sommetBbksl-nl """bksl-nl assert (sommetA in self.listepy-undsommets), "sommet A pas dans le graphe"bksl-nl assert (sommetB in self.listepy-undsommets), "sommet B pas dans le graphe"bksl-nl if sommetB not in self.adjacents[sommetA]:bksl-nl self.adjacents[sommetA].append(sommetB)bksl-nl if sommetA not in self.adjacents[sommetB]:bksl-nl self.adjacents[sommetB].append(sommetA)bksl-nlbksl-nl def voisins(self, sommet):bksl-nl """bksl-nl Renvoie une liste des voisins du sommet dans la représentation du graphebksl-nl """bksl-nl assert sommet in self.listepy-undsommets, "sommet pas dans le graphe"bksl-nl return self.adjacents[sommet]bksl-nlbksl-nl def estpy-undarc(self, sommetA, sommetB):bksl-nl """bksl-nl Renvoie un booléen indiquant si l'arc sommetA - sommetB appartient au graphebksl-nl """bksl-nl assert sommetA in self.listepy-undsommets, "sommetA pas dans le graphe"bksl-nl return sommetB in self.adjacents[sommetA]bksl-nl bksl-nlbksl-nlclass File:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """Construit une file vide"""bksl-nl self.contenu = deque([])bksl-nl bksl-nl def filepy-undvide(self):bksl-nl """Teste si une file est vide"""bksl-nl return len(self.contenu) == 0bksl-nlbksl-nl def defiler(self):bksl-nl """bksl-nl Extrait l'élément en tête de filebksl-nl Coût constant, complexité en O(1)bksl-nl """bksl-nl assert not self.filepy-undvide(), "File Vide"bksl-nl return self.contenu.popleft()bksl-nl bksl-nl def enfiler(self, elt):bksl-nl """bksl-nl Insère elt en queue de filebksl-nl Coût constant, complexité en O(1)bksl-nl """bksl-nl self.contenu.append(elt)bksl-nl bksl-nlclass Pile:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """Construit une pile vide"""bksl-nl self.contenu = []bksl-nl bksl-nl def pilepy-undvide(self):bksl-nl """Teste si une file est vide"""bksl-nl return len(self.contenu) == 0bksl-nlbksl-nl def depiler(self):bksl-nl """bksl-nl Extrait l'élément au sommet de la pilebksl-nl Coût constant, complexité en O(1)bksl-nl """bksl-nl assert not self.pilepy-undvide(), "Pile Vide"bksl-nl return self.contenu.pop()bksl-nl bksl-nl def empiler(self, elt):bksl-nl """bksl-nl Insère elt au sommet de la pilebksl-nl Coût constant, complexité en O(1)bksl-nl """bksl-nl self.contenu.append(elt)bksl-nlbksl-nlbksl-nldef explopy-undlabypy-unddfs(debut, fin, laby):bksl-nl """Exploration avec parcours en profondeurbksl-nl du graphe non orienté laby bksl-nl depuis le sommet debut jusqu'au sommet finbksl-nl Renvoie la liste trace des sommets traversésbksl-nl """bksl-nl decouvert = {s: False for s in laby.sommets()} bksl-nl enpy-undattente = Pile()bksl-nl enpy-undattente.empiler(debut)bksl-nl trace = []bksl-nl # à compléterbksl-nl return tracebksl-nlbksl-nldef explopy-undlabypy-undbfs(sommet, sortie, laby):bksl-nl """Exploration avec parcours en largeurbksl-nl du graphe non orienté laby bksl-nl depuis le sommet debut jusqu'au sommet finbksl-nl Renvoie la liste trace des couples (sommet traversé, distance à debut)bksl-nl """bksl-nl distance = {s:float('inf') for s in laby.sommets()}bksl-nl decouvert = {s: False for s in laby.sommets()} bksl-nl enpy-undattente = File()bksl-nl decouvert[sommet] = Truebksl-nl distance[sommet] = 0bksl-nl enpy-undattente.enfiler(sommet)bksl-nl trace = []bksl-nl while not enpy-undattente.filepy-undvide():bksl-nl s = enpy-undattente.defiler()bksl-nl trace.append((s, distance[s]))bksl-nl if s == sortie:bksl-nl breakbksl-nl for v in laby.voisins(s):bksl-nl if not decouvert[v]:bksl-nl decouvert[v] = Truebksl-nl distance[v] = distance[s] + 1bksl-nl enpy-undattente.enfiler(v)bksl-nl return tracebksl-nlbksl-nl#On génère le labyrinthebksl-nlsommets = [(i, j) for i in range(6) for j in range(5)]bksl-nllabypy-undwikipedia = Graphe(sommets)bksl-nllistepy-undarcs = [((0,4), (1, 4)), ((1,4), (2, 4)), ((2,4), (2, 3)), ((2,3), (2, 2)),((2,3), (3, 3))bksl-nl , ((2,2), (1, 2)), ((1, 2), (1, 3)), ((1,3), (0, 3)), ((2, 2), (3, 2)), ((3, 2), (3, 1)),bksl-nl ((3, 1), (2, 1)), ((2, 1), (1, 1)),((1, 0), (0, 0)), ((0, 0), (0, 1)),((2, 1), (2, 0)),bksl-nl ((2, 0), (3, 0)), ((3, 0), (4, 0)),((2, 4), (3, 4)), ((3, 4), (4, 4)),bksl-nl ((4, 4), (4, 3)),((4, 3), (4, 2)), ((4, 2), (5, 2)),((5, 2), (5, 1)),((5, 1), (5, 0)),bksl-nl ((5, 2), (5, 3)), ((5, 2), (5, 3)), ((5, 3), (5, 4))]bksl-nlfor (i, j) in listepy-undarcs:bksl-nl labypy-undwikipedia.ajoutepy-undarc(i, j)bksl-nlbksl-nldef testpy-undlabypy-unddfs():bksl-nl """Test unitaire pour labypy-unddfs"""bksl-nl attendu = [(0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4)]bksl-nl assert explopy-undlabypy-unddfs((0,4), (5,4), labypy-undwikipedia)bksl-nl print("Tests réussis")bksl-nlbksl-nldef testpy-undlabypy-undbfs():bksl-nl """Test unitaire pour labypy-undbfs"""bksl-nl attendu = [((0, 4), 0), ((1, 4), 1), ((2, 4), 2), ((2, 3), 3), ((3, 4), 3), ((2, 2), 4),bksl-nl ((3, 3), 4), ((4, 4), 4), ((1, 2), 5), ((3, 2), 5), ((4, 3), 5), ((1, 3), 6),bksl-nl ((3, 1), 6), ((4, 2), 6), ((0, 3), 7), ((2, 1), 7), ((5, 2), 7), ((0, 2), 8),bksl-nl ((1, 1), 8), ((2, 0), 8), ((5, 1), 8), ((5, 3), 8), ((1, 0), 9), ((3, 0), 9),bksl-nl ((5, 0), 9), ((5, 4), 9)]bksl-nl assert explopy-undlabypy-undbfs((0,4), (5,4), labypy-undwikipedia)bksl-nl print("Tests réussis")bksl-nl

Question 1

Compléter la fonction explo_laby_dfs en adaptant légèrement la fonction de parcours en profondeur itératif dfs présentée dans la section précédente. On initialisera le parcours avec le sommet debut et on sortira de la boucle dès que le sommet fin sera atteint.

🐍 Script Python
def explo_laby_dfs(debut, fin, laby):
    """Exploration  du graphe non orienté laby 
    du sommet debut jusqu'au sommet fin
    Renvoie la liste trace des sommets traversés
    """
    decouvert = {s: False for s in laby.sommets()}    
    en_attente = Pile()
    en_attente.empiler(debut)
    trace = []
    while not en_attente.pile_vide():
        s = en_attente.depiler()
        trace.append(s)
        if s == fin:
            break
        if not decouvert[s]:
            decouvert[s] = True
            for v in laby.voisins(s):
                if not decouvert[v]:
                    en_attente.empiler(v)
    return trace
Question 2

Compléter la fonction explo_laby_bfs en adaptant légèrement la fonction de parcours en largeur itératif bfs présentée dans la section précédente. On initialisera le parcours avec le sommet debut et on sortira de la boucle dès que le sommet fin sera atteint.

🐍 Script Python
def explo_laby_bfs(sommet, sortie, laby):
    """Exploration avec parcours en largeur
    du graphe non orienté laby 
    depuis le  sommet debut jusqu'au sommet fin
    Renvoie la liste trace des  couples (sommet traversé, distance à debut)
    """
    distance = {s:float('inf') for s in laby.sommets()}
    decouvert = {s: False for s in laby.sommets()}    
    en_attente = File()
    decouvert[sommet] = True
    distance[sommet] = 0
    en_attente.enfiler(sommet)
    trace = []
    while not en_attente.file_vide():
        s = en_attente.defiler()
        trace.append((s, distance[s]))
        if s == sortie:
            break
        for v in laby.voisins(s):
            if not decouvert[v]:
                decouvert[v] = True
                distance[v] = distance[s] + 1
                en_attente.enfiler(v)
    return trace
Question 3

Le parcours en profondeur permet-il toujours d'atteindre la sortie en moins d'étapes que le parcours en largeur ?

Non, cela dépend de l'ordre d'énumération des voisins dans les listes d'adjacences.

Bulles informationnelles et composantes connexes dans un graphe non orienté⚓︎

Exercice 16

💻 Saisir ses réponses sur Capytale

Le graphe non orienté ci-dessous modélise les liens entre différents membres d'un réseau social : chaque sommet représente un membre et un arc relie deux sommets si les individus associés sont "amis" sur le réseau. La relation d'amitié est symétrique donc le graphe est non orienté.

S'algorithme du réseau affiche une information sur le fil d'actualité d'un individu A alors il l'affichera aussi sur le fil de tous les "amis" de A et de tous les "amis" des "amis" de A etc .... Ainsi deux membres du réseau associés à des sommets du graphe qui peuvent être reliés par un chemin appartiendront à la même bulle informationnelle . En théorie des graphes, on parle de composante connexe. Par exemple 'Mario' et 'Diddy Kong' sont dans la même bulle informationnelle mais 'Snake' est tout seul dans sa bulle ...

alt

Pour déterminer les composantes connexes d'un graphe non orienté un algorirthme simple est le suivant :

📋 Texte
On marque chaque sommet comme non decouvert
On initialise un compteur de composante connexe  à 1
Pour chaque sommet du graphe
    Si le sommet est non découvert alors 
        on lance un parcours de graphe depuis ce sommet
        et dans ce parcours on marque les sommets découverts
        et on leur attribue la valeur de compteur comme numéro de composante connexe
        A la fin du parcours on incrémente le compteur de composante connexe

Il suffit donc d'augmenter un algorithme de parcours de graphe avec un compteur de composante connexe et d'appeler cet algorithme dans une boucle sur l'ensemble des sommets du graphe. On donne ci-dessous un script à compléter pour numéroter à partir de 1 les composantes connexes du graphe de réseau social considéré.

Remarque 1

Il faut d'abord exécuter le script dans l'éditeur de l'exercice 15 afin que les classes Graphe, File et Pile soient disponibles.

Remarque 2

Le calcul des composantes connexes (dites fortement connexes) d'un graphe orienté est plus complexe. En effet, deux sommets appartiennent à une même composante s'il existe deux chemins les reliant dans un sens et dans l'autre et en général le chemin dans un sens ne peut pas être pris dans l'autre. L'algorithme de Kosaraju permet de résoudre ce problème à l'aide de deux parcours en profondeur et d'une variante du tri topolgique vu dans l'exercice 18.

###
# génération du graphebksl-nlbksl-nlindividus = ['Pikachu', 'Mewtwo', 'Link', 'Zelda', 'Sheik', 'Ganondorf', 'Snake', 'Samus', 'Samus sans armure',bksl-nl 'Dark Samus', 'Ridley', 'Fox', 'Wolf', 'Falco', 'Diddy Kong', 'King K. Rool', 'Donkey Kong', 'Mario',bksl-nl 'Sonic', 'Wario', 'Luigi', 'Bowser', 'Peach', 'Yoshi', 'Daisy']bksl-nlsmashbros = Graphe(individus)bksl-nllistepy-undarcs = [('Pikachu', 'Mewtwo'), ('Mewtwo', 'Pikachu'), ('Link', 'Ganondorf'), ('Zelda', 'Ganondorf'), ('Sheik', 'Ganondorf'), ('Ganondorf', 'Link'), ('Ganondorf', 'Zelda'), ('Ganondorf', 'Sheik'), ('Samus', 'Dark Samus'), ('Samus', 'Ridley'), ('Samus sans armure', 'Dark Samus'), ('Samus sans armure', 'Ridley'), ('Dark Samus', 'Samus'), ('Dark Samus', 'Samus sans armure'), ('Ridley', 'Samus'), ('Ridley', 'Samus sans armure'), ('Fox', 'Wolf'), ('Wolf', 'Fox'), ('Wolf', 'Falco'), ('Falco', 'Wolf'), ('Diddy Kong', 'King K. Rool'), ('King K. Rool', 'Diddy Kong'), ('King K. Rool', 'Donkey Kong'), ('Donkey Kong', 'King K. Rool'), ('Donkey Kong', 'Mario'), ('Mario', 'Donkey Kong'), ('Mario', 'Sonic'), ('Mario', 'Bowser'), ('Mario', 'Wario'), ('Sonic', 'Mario'), ('Wario', 'Mario'), ('Wario', 'Luigi'), ('Luigi', 'Wario'), ('Luigi', 'Bowser'), ('Bowser', 'Mario'), ('Bowser', 'Luigi'), ('Bowser', 'Peach'), ('Bowser', 'Daisy'), ('Bowser', 'Yoshi'), ('Peach', 'Bowser'), ('Yoshi', 'Bowser'), ('Daisy', 'Bowser')]bksl-nlfor i, j in listepy-undarcs:bksl-nl smashbros.ajoutepy-undarc(i, j) bksl-nlbksl-nlbksl-nldef dfspy-undrecpy-undcc(sommet, graphe, decouvert, composante, numero):bksl-nl """bksl-nl Parcours en profondeur qui marque dans un dictionnaire composantebksl-nl le numero de composante des sommets découvertsbksl-nl """bksl-nl # à compléterbksl-nl bksl-nlbksl-nldef composantespy-undconnexes(graphe):bksl-nl """bksl-nl Numérote à partir de 1 les composantes connexes bksl-nl d'un graphe non orienté dans un dictionnaire composante bksl-nl """bksl-nl decouvert = {s: False for s in graphe.sommets()}bksl-nl composante = {s: -1 for s in graphe.sommets()}bksl-nl numero = 1bksl-nl for s in graphe.sommets():bksl-nl if not decouvert[s]:bksl-nl dfspy-undrecpy-undcc(s, graphe, decouvert, composante, numero)bksl-nl numero += 1bksl-nl return composantebksl-nlbksl-nldef testpy-undcomposantespy-undconnexes():bksl-nl """Test unitaire pour composantespy-undconnexes"""bksl-nl attendu = {'Pikachu': 1, 'Mewtwo': 1, 'Link': 2, 'Zelda': 2, 'Sheik': 2, 'Ganondorf': 2, 'Snake': 3,bksl-nl 'Samus': 4, 'Samus sans armure': 4, 'Dark Samus': 4, 'Ridley': 4, 'Fox': 5, 'Wolf': 5, 'Falco': 5,bksl-nl 'Diddy Kong': 6, 'King K. Rool': 6, 'Donkey Kong': 6, 'Mario': 6, 'Sonic': 6, 'Wario': 6, 'Luigi': 6,bksl-nl 'Bowser': 6, 'Peach': 6, 'Yoshi': 6, 'Daisy': 6}bksl-nl assert composantespy-undconnexes(smashbros)bksl-nl print("Tests réussis")bksl-nlbksl-nl# Exécutez d'abord le code de l'éditeur de l'exercice 15bksl-nlbksl-nlbksl-nl

Question 1

Complétez la version augmentée du parcours en profondeur récursif dfs_rec_cc afin de répondre à ce problème.

🐍 Script Python
def dfs_rec_cc(sommet, graphe, decouvert, composante, numero):
    """
    Parcours en profondeur qui marque dans un dictionnaire composante
    le numero de composante des sommets découverts
    """
    decouvert[sommet] = True
    composante[sommet] = numero
    for v in graphe.voisins(sommet):
        if not decouvert[v]:
            dfs_rec_cc(v, graphe, decouvert, composante, numero)

def composantes_connexes(graphe):
    """
    Numérote à partir de 1 les composantes connexes 
    d'un graphe non orienté dans un dictionnaire composante    
    """
    decouvert = {s: False for s in graphe.sommets()}
    composante = {s: -1 for s in graphe.sommets()}
    numero = 1
    for s in graphe.sommets():
        if not decouvert[s]:
            dfs_rec_cc(s, graphe, decouvert, composante, numero)
            numero += 1
    return composante

Algorithmes sur les graphes orientés⚓︎

Détection d'un cycle dans un graphe de dépendances⚓︎

Exercice 17

💻 Saisir ses réponses sur Capytale

Lorsqu'on développe projet en Python, on doit écrire ou importer plusieurs modules. Les dépendances entre les différents modules du projet peuvent se modéliser par un graphe orienté. On donne deux exemples ci-dessous

alt

alt

Un graphe de dépendances présente un problème de dépendances circulaires, s'il contient un cycle, il est donc intéressant de disposer d'un algorithme de détection de cycle dans un graphe (ici orienté).

question 1

Pour chacun des graphes de dépendances 1 et 2, déterminer s'il contient un cycle.

Le grapĥe orienté 1 contient un cycle module_B - > module_A -> module_F -> module_E -> module_C -> module_B.

Le graphe orienté 2 ne contient pas de cycle.

question 2
  • Si on lance un parcours en profondeur depuis le sommet module_A dans le graphe 1, comment peut-on détecter un cycle ?
  • Va-t-on détecter un cycle si on lance un parcours en profondeur depuis le sommet math?
  • Proposer un algorithme pour détecter un cycle dans un graphe orienté.
  • On peut détecter un cycle au cours d'un parcours en profondeur lancé depuis le sommet module_A en remarquant lors de la découverte du sommet module_B que son successeur, module_A, est celui depuis lequel a été lancé le parcours.
  • On ne détectera pas de cycle si on lance un parcours en profondeur depuis le sommet math, le parcours va juste découvrir les sommets math et module_G
  • On peut détecter un cycle dans un graphe orienté en lançant un parcours en profondeur depuis chaque sommet s'il n'est pas découvert. Il faut tenir à jour deux dictionnaires pour marquer les sommets :
    • decouvert pour marquer les sommets déjà découverts au cours de l'exécution de l'algorithme, comme dans le parcours en profondeur classique
    • en_cours pour marquer les sommets depuis lesquels un parcours en profondeur a été lancé et n'est pas encore terminé : on positionne en_cours[sommet] à True au lancement du parcours puis à False lorsque le parcours est complètement terminé. Avec une version récursive du parcours dfs, il suffit de le faire au début et à la fin de l'appel.
question 3

Dans le script Python ci-dessous, compléter les codes des fonctions dfs_cycle et detecter_cycle en implémentant l'algorithme de détection de cycle dans un graphe orienté décrit dans la question précédente.

Remarque 1

Il faut d'abord exécuter le script dans l'éditeur de l'exercice 15 afin que les classes File et Pile soient disponibles.

###
class Graphepy-undoriente:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, listepy-undsommets):bksl-nl """bksl-nl Crée une représentation de graphe orienté à partir d'une liste de sommetsbksl-nl """bksl-nl self.listepy-undsommets = listepy-undsommetsbksl-nl self.adjacents = {sommet : [] for sommet in listepy-undsommets}bksl-nl bksl-nl def sommets(self):bksl-nl """bksl-nl Renvoie une liste des sommetsbksl-nl """bksl-nl return self.listepy-undsommetsbksl-nlbksl-nl def ajoutepy-undarc(self, sommetA, sommetB):bksl-nl """bksl-nl Ajoute dans la représentation de graphe l'arc sommetA -> sommetBbksl-nl """bksl-nl assert (sommetA in self.listepy-undsommets), "sommet A pas dans le graphe"bksl-nl assert (sommetB in self.listepy-undsommets), "sommet B pas dans le graphe"bksl-nl self.adjacents[sommetA].append(sommetB)bksl-nlbksl-nlbksl-nl def voisins(self, sommet):bksl-nl """bksl-nl Renvoie une liste des voisins du sommet dans la représentation du graphebksl-nl """bksl-nl assert sommet in self.listepy-undsommets, "sommet pas dans le graphe"bksl-nl return self.adjacents[sommet]bksl-nlbksl-nl def estpy-undarc(self, sommetA, sommetB):bksl-nl """bksl-nl Renvoie un booléen indiquant si l'arc sommetA -> sommetB appartient au graphebksl-nl """bksl-nl assert sommetA in self.listepy-undsommets, "sommetA pas dans le graphe"bksl-nl return sommetB in self.adjacents[sommetA]bksl-nl bksl-nl def supprimepy-undsommet(self, sommet):bksl-nl """bksl-nl Supprime sommet du graphebksl-nl """bksl-nl self.listepy-undsommets.remove(sommet)bksl-nl del self.adjacents[sommet]bksl-nl for s in self.sommets():bksl-nl if sommet in self.voisins(s):bksl-nl self.adjacents[s].remove(sommet) bksl-nl bksl-nl def degrepy-undentrant(self, sommet):bksl-nl """bksl-nl Renvoie le degré entrant d'un sommet du graphe orientébksl-nl """bksl-nl d = 0bksl-nl for s in self.sommets():bksl-nl if sommet in self.voisins(s):bksl-nl d = d + 1bksl-nl return dbksl-nl bksl-nl def degrepy-undsortant(self, sommet):bksl-nl """bksl-nl Renvoie le degré sortant d'un sommet du graphe orientébksl-nl """bksl-nl d = 0bksl-nl for s in self.voisins(sommet):bksl-nl d = d + 1bksl-nl return dbksl-nlbksl-nlbksl-nldef dfspy-undcycle(sommet, graphe, decouvert, enpy-undcours):bksl-nl """bksl-nl Parcours en profondeur récursif augmenté pour marquerbksl-nl dans le dictionnaire decouvert que sommet est découvert au cours du parcoursbksl-nl dans le dictionnaire enpy-undcours que sommet est en cours de parcours dfs au début de l'appelbksl-nl et en fin de parcours dfs à la fin de l'appelbksl-nl Renvoie un booléenbksl-nl """bksl-nl decouvert[sommet] = Truebksl-nl enpy-undcours[sommet] = Truebksl-nl # à compléterbksl-nl enpy-undcours[sommet] = Falsebksl-nl return Falsebksl-nlbksl-nldef detecterpy-undcycle(graphe):bksl-nl """bksl-nl Renvoie un booléen indiquant si le graphe bksl-nl orienté contient un cyclebksl-nl """bksl-nl decouvert = {s: False for s in graphe.sommets()} bksl-nl for s in graphe.sommets():bksl-nl if not decouvert[s]:bksl-nl enpy-undcours = {s: False for s in graphe.sommets()}bksl-nl # à compléterbksl-nl return Falsebksl-nlbksl-nlbksl-nl# génération du graphe de dépendances 1bksl-nllistepy-undsommets1 = ['complex', 'modulepy-undB', 'modulepy-undE', 'modulepy-undF', 'modulepy-undD', 'math', 'cmath', 'modulepy-undC', 'modulepy-undA', 'modulepy-undG']bksl-nllistepy-undarcs1 = [('complex', 'modulepy-undB'), ('complex', 'modulepy-undE'), ('modulepy-undB', 'modulepy-undA'), ('modulepy-undB', 'modulepy-undD'), ('modulepy-undE', 'modulepy-undC'), ('modulepy-undF', 'modulepy-undE'), ('modulepy-undD', 'modulepy-undE'), ('math', 'modulepy-undG'), ('cmath', 'modulepy-undA'), ('modulepy-undC', 'modulepy-undB'), ('modulepy-undA', 'modulepy-undF'), ('modulepy-undA', 'modulepy-undG')]bksl-nlgraphe1 = Graphepy-undoriente(listepy-undsommets1)bksl-nlfor i, j in listepy-undarcs1:bksl-nl graphe1.ajoutepy-undarc(i, j)bksl-nlbksl-nl# génération du graphe de dépendances 2bksl-nllistepy-undsommets2 = ['complex', 'modulepy-undB', 'modulepy-undE', 'modulepy-undG', 'modulepy-undF', 'math', 'cmath', 'modulepy-undC', 'modulepy-undA']bksl-nllistepy-undarcs2 = [('complex', 'modulepy-undB'), ('complex', 'modulepy-undE'), ('modulepy-undB', 'modulepy-undC'), ('modulepy-undB', 'modulepy-undE'), ('modulepy-undB', 'modulepy-undG'), ('modulepy-undE', 'modulepy-undF'), ('modulepy-undG', 'modulepy-undA'), ('modulepy-undF', 'modulepy-undC'), ('math', 'modulepy-undA'), ('cmath', 'modulepy-undA'), ('modulepy-undC', 'modulepy-undA')]bksl-nlgraphe2 = Graphepy-undoriente(listepy-undsommets2)bksl-nlfor i, j in listepy-undarcs2:bksl-nl graphe2.ajoutepy-undarc(i, j)bksl-nlbksl-nldef testpy-unddetecterpy-undcycle():bksl-nl """Test unitaire pour detesterpy-undcycle"""bksl-nl assert detecterpy-undcycle(graphe1) == True, "échec sur le graphe de dépendances 1"bksl-nl assert detecterpy-undcycle(graphe2) == False, "échec sur le graphe de dépendances 2"bksl-nl print("Tests réussis")bksl-nlbksl-nlbksl-nl

🐍 Script Python
def dfs_cycle(sommet, graphe, decouvert, en_cours):
    decouvert[sommet] = True
    en_cours[sommet] = True
    for v in graphe.voisins(sommet):
        if not decouvert[v]:
            if dfs_cycle(v, graphe, decouvert, en_cours):
                return True
        elif en_cours[v]:
            return True
    en_cours[sommet] = False
    return False

def detecter_cycle(graphe):
    decouvert = {s: False for s in graphe.sommets()}    
    for s in graphe.sommets():
        if not decouvert[s]:
            en_cours = {s: False for s in graphe.sommets()}
            rep = dfs_cycle(s, graphe, decouvert, en_cours)
            if rep:
                return True
    return False
question 4

On veut désormais reconstruire le cycle lorsqu'on en détecte un. Pour celà, on augmente encore le parcours en profondeur avec un dictionnaire precedent qui enregistre pour chaque sommet découvert, le prédécesseur dont est parti l'arc qui a permis de le découvrir.

Dans le script ci-dessous, compléter les fonctions :

  • construire_cycle
  • dfs_cycle2
  • detecter_cycle2

Remarque 1

Il faut d'abord exécuter le script dans l'éditeur de l'exercice 15 afin que les classes File et Pile soient disponibles, ainsi que le script dans l'éditeur de l'exercice 17 question 3, pour que les graphes orientés graphe1 et graphe2 soient définis.

###
def construirepy-undcycle(sommet, graphe, precedent):bksl-nl """bksl-nl Reconstruit un cycle d'extrémités sommetbksl-nl dans un graphe orientébksl-nl à partir du dictionnaire precedent bksl-nl associant à chaque sommet découvert son prédécesseurbksl-nl dans un parcours dfsbksl-nl """bksl-nl cycle = [sommet]bksl-nl courant = precedent[sommet]bksl-nl # à compléterbksl-nl return cyclebksl-nlbksl-nlbksl-nlbksl-nldef dfspy-undcycle2(sommet, graphe, decouvert, enpy-undcours, precedent):bksl-nl """bksl-nl Parcours en profondeur récursif augmenté pour marquer :bksl-nl - dans le dictionnaire decouvert que sommet est découvert au cours du parcoursbksl-nl - dans le dictionnaire enpy-undcours que sommet est en cours de parcours dfs au début de l'appelbksl-nl et en fin de parcours dfs à la fin de l'appelbksl-nl - dans le dictionnaire precedent le prédécesseur du sommet découvert bksl-nl bksl-nl Renvoie une liste Python : : le cycle ou une liste videbksl-nl """bksl-nl decouvert[sommet] = Truebksl-nl enpy-undcours[sommet] = Truebksl-nl for v in graphe.voisins(sommet):bksl-nl if not decouvert[v]:bksl-nl precedent[v] = sommetbksl-nl rep = dfspy-undcycle2(v, graphe, decouvert, enpy-undcours, precedent)bksl-nl # à compléterbksl-nl elif enpy-undcours[v]:bksl-nl precedent[v] = sommetbksl-nl # à compléterbksl-nl return ...bksl-nl enpy-undcours[sommet] = Falsebksl-nl return []bksl-nlbksl-nldef detecterpy-undcycle2(graphe):bksl-nl """bksl-nl Détermine si le graphe bksl-nl orienté contient un cyclebksl-nl Renvoie une liste Python : le cycle ou une liste videbksl-nl """bksl-nl decouvert = {s: False for s in graphe.sommets()} bksl-nl precedent = {s:None for s in graphe.sommets()}bksl-nl # à compléterbksl-nl ...bksl-nl return []bksl-nl bksl-nlbksl-nl bksl-nl bksl-nldef testpy-unddetecterpy-undcycle2():bksl-nl """Test unitaire pour detesterpy-undcycle"""bksl-nl assert detecterpy-undcycle2(graphe1) == ['modulepy-undB', 'modulepy-undC', 'modulepy-undE', 'modulepy-undF', 'modulepy-undA', 'modulepy-undB'], "échec sur le graphe de dépendances 1"bksl-nl assert detecterpy-undcycle2(graphe2) == [], "échec sur le graphe de dépendances 2"bksl-nl print("Tests réussis")bksl-nl

🐍 Script Python
def construire_cycle(sommet, graphe, precedent):
    """
    Reconstruit un cycle d'extrémités sommet
    dans un graphe orienté
    à partir du dictionnaire precedent 
    associant à chaque sommet découvert son prédécesseur
    dans un parcours dfs
    """
    cycle = [sommet]
    courant = precedent[sommet]
    while courant != sommet:
        cycle.append(courant)
        courant = precedent[courant]
    cycle.append(courant)
    return cycle
    
def dfs_cycle2(sommet, graphe, decouvert, en_cours, precedent):
    """
    Parcours en profondeur récursif augmenté pour marquer :
    - dans  le dictionnaire decouvert  que sommet est découvert au cours du parcours
    - dans le dictionnaire en_cours que sommet est en cours de parcours dfs au début de l'appel
    et en fin de parcours dfs à la fin de l'appel
    - dans le dictionnaire precedent le prédécesseur du sommet découvert 
    
    Renvoie une liste Python :  : le cycle ou une liste vide
    """
    decouvert[sommet] = True
    en_cours[sommet] = True
    for v in graphe.voisins(sommet):
        if not decouvert[v]:
            precedent[v] = sommet
            rep = dfs_cycle2(v, graphe, decouvert, en_cours, precedent)
            if len(rep) > 0:
                return rep
        elif en_cours[v]:
            precedent[v] = sommet
            return construire_cycle(v, graphe, precedent)
    en_cours[sommet] = False
    return []

def detecter_cycle2(graphe):
    """
    Détermine si  le graphe 
    orienté contient un cycle
    Renvoie  une liste Python : le cycle ou une liste vide
    """
    decouvert = {s: False for s in graphe.sommets()}    
    precedent = {s:None for s in graphe.sommets()}
    for s in graphe.sommets():
        if not decouvert[s]:
            en_cours = {s: False for s in graphe.sommets()}
            rep = dfs_cycle2(s, graphe, decouvert, en_cours, precedent)
            if len(rep) > 0:
                return rep
    return []

Planification de tâches et ordre topologique⚓︎

Exercice 18

Un professeur d'informatique doit construire une progression à partir de modules d'enseignement dont un graphe de précédence est donné ci-dessous.

alt

L'arc pointant du sommet algorithmique vers calcul scientifique signifie que le module algorithmique doit être traité avant celui de calcul scientifique. Le problème qui se pose au professeur est donc un problème d'ordonnancement / tri : dans quel ordre peut-il traiter les modules pour respecter les contraintes ?

Un ordonnancement respectant les contraintes de précédence est un ordre topologique du graphe orienté.

Question 1

Si on rajoute dans le graphe un arc d'origine réseaux de neurones et d'extrémité informatique commune, le problème a-t-il une solution ? Pourquoi ?

Non, le problème n'a pas de solution car le graphe orienté contient alors un cycle : algorithmique -> informatique théorique -> intelligence artificielle -> réseaux de neurones -> informatique commune -> algorithmique

Il est alors impossible de définir un ordre d'énumération des sommets respectant touts les contraintes de précédence : on devrait avoir * réseaux de neurone* placé avant informatique commune et réciproquement ce qui est contradictoire.

Question 2

On considère désormais un graphe orienté sans cycle.

On peut remarquer que le sommet en première position dans l'ordre topologique a un degré entrant nul car s'il avait un prédécesseur, celui-ci serait placé avant dans l'ordre topologique ce qui est contradictoire avec le fait que le sommet considéré est en première position.

On va exploiter cette propriété pour construire un ordre topologique du graphe orienté avec l'algorithme suivant :

  • Étape 1 : On place dans une file A tous les sommets dont le degré entrant est nul. On initialise une file B vide.
  • Étape 2 : Si la file A est vide on passe à l'étape 4 sinon, on retire le premier sommet u de la file A et on l'insère dans la file B représentant l'ordre topologique.
  • Étape 3 : On ajoute à la fileA tous les successeurs du sommet u dont le degré entrant est 1, puis on supprime le sommet u du graphe. On revient à l'étape 2.
  • Étape 4 : La file A est vide, l'algorithme est terminé, la file file B contient un ordre topologique du graphe orienté sans cycle.

Appliquer cet algorithme à la main, pour construire un ordre topologique du graphe de précédences du cours d'informatique.

Compléter la fonction ordre_topologique dans le script Python ci-dessous.

Quelle est la complexité de cet algorithme en fonction du nombre de sommets \(n\) et du nombre d'arcs \(m\) ? On suppose que chaque appel à la méthode degre_entrant parcourt l'ensemble des sommets du graphe.

Remarque 1

Il faut d'abord exécuter le script dans l'éditeur de l'exercice 15 afin que les classes File et Pile soient disponibles, ainsi que le script dans l'éditeur de l'exercice 17 question 3, pour que la classe Graphe_oriente soit définie. Son interface présente une méthode degre_entrant(self, sommet) et une méthode supprime_sommet(self, sommet).

###
bksl-nl# génération du graphe de cours d'informatiquebksl-nllistepy-undmodules = ['algorithmique', 'informatique commune', 'analyse', 'algèbre linéaire', 'informatique théorique', 'intelligence artificielle', 'apprentissage machine', 'calcul scientifique', 'programmation avancée', 'bases de données', 'bioinformatique', 'réseaux de neurones', 'robotique']bksl-nllistepy-undarcs = [('algorithmique', 'bases de données'), ('algorithmique', 'calcul scientifique'), ('algorithmique', 'informatique théorique'), ('informatique commune', 'algorithmique'), ('informatique commune', 'programmation avancée'), ('analyse', 'algèbre linéaire'), ('algèbre linéaire', 'informatique théorique'), ('informatique théorique', 'bioinformatique'), ('informatique théorique', 'intelligence artificielle'), ('intelligence artificielle', 'apprentissage machine'), ('intelligence artificielle', 'robotique'), ('intelligence artificielle', 'réseaux de neurones'), ('apprentissage machine', 'réseaux de neurones'), ('calcul scientifique', 'bioinformatique'), ('programmation avancée', 'calcul scientifique')]bksl-nlbksl-nlgraphepy-undinfo = Graphepy-undoriente(listepy-undmodules)bksl-nlfor i, j in listepy-undarcs:bksl-nl graphepy-undinfo.ajoutepy-undarc(i, j)bksl-nlbksl-nlbksl-nldef ordrepy-undtopologique(graphe):bksl-nl """bksl-nl Renvoie un ordre topologique d'un graphe orienté supposé sans cyclebksl-nl sous la forme d'une liste Python avec les sommets ordonnésbksl-nl de gauche à droitebksl-nl """bksl-nl fileA = File()bksl-nl for s in graphe.sommets():bksl-nl if graphe.degrepy-undentrant(s) == 0:bksl-nl fileA.enfiler(s)bksl-nl fileB = File()bksl-nl #à compléter bksl-nl ordre = []bksl-nl while not fileB.filepy-undvide():bksl-nl ordre.append(fileB.defiler())bksl-nl return ordrebksl-nlbksl-nlbksl-nldef testpy-undordrepy-undtopologique():bksl-nl """bksl-nl Test unitaire pour la fonction ordrepy-undtopologique bksl-nl """bksl-nl assert ordrepy-undtopologique(graphepy-undinfo) == ['informatique commune', 'analyse', 'algorithmique',bksl-nl 'programmation avancée', 'algèbre linéaire', 'bases de données', 'calcul scientifique',bksl-nl 'informatique théorique', 'bioinformatique', 'intelligence artificielle', 'apprentissage machine',bksl-nl 'robotique', 'réseaux de neurones'], "échec sur ordrepy-undtopologique(graphepy-undinfo)"bksl-nl print("Test unitaire réussi")bksl-nl bksl-nldef dfspy-undtopo(sommet, graphe, decouvert):bksl-nl """bksl-nl Parcours en profondeur récursif augmenté bksl-nl Marque dans le dictionnaire decouvert que sommet est découvert au cours du parcoursbksl-nl Affiche le sommet en fin d'appelbksl-nl """bksl-nl # à compléterbksl-nlbksl-nl bksl-nldef ordrepy-undtopologique2(graphe):bksl-nl decouvert = {s: False for s in graphepy-undinfo.sommets()}bksl-nl for s in graphe.sommets():bksl-nl if not decouvert[s]:bksl-nl dfspy-undtopo(s, graphe, decouvert)bksl-nlbksl-nl

Un ordre topologique possible (il peut en exister plusieurs) :

📋 Texte
['informatique commune',
'analyse',
'algorithmique',
'programmation avancée',
'algèbre linéaire',
'bases de données',
'calcul scientifique',
'informatique théorique',
'bioinformatique',
'intelligence artificielle',
'apprentissage machine',
'robotique',
'réseaux de neurones']

Une représentation d'un ordre topologique :

alt

Le code :

🐍 Script Python
def ordre_topologique(graphe):
    """
    Renvoie un ordre topologique d'un graphe orienté supposé sans cycle
    sous la forme d'une liste Python avec les sommets ordonnés
    de gauche à droite
    """
    fileA = File()
    for s in graphe.sommets():
        if graphe.degre_entrant(s) == 0:
            fileA.enfiler(s)
    fileB = File()
    while not fileA.file_vide():
        sc = fileA.defiler()
        fileB.enfiler(sc)
        for v in graphe.voisins(sc):
            if graphe.degre_entrant(v) == 1:
                fileA.enfiler(v)
        graphe.supprime_sommet(sc)        
    ordre = []
    while not fileB.file_vide():
        ordre.append(fileB.defiler())
    return ordre

La complexité de cet algorithme est en \(O(n \times m)\). Chaque sommet est ajouté et retiré une fois de la file A et inséré une fois dans la file B avec un coût constant donc on a déjà un coût en \(O(n)\). Ensuite, pour déterminer les prochains sommets à insérer dans la file A on examine les successeurs du sommet qu'on vient de retirer de la file A et pour chacun on détermine son degré entrant en parcourant tous les sommets du graphe. Tous les arcs sont examinés une fois et pour chacun tous les sommets sont parcourus, ce qui ajoute un coût en \(O(n \times m)\). Au total, on a donc une complexité en \(O(n \times m)\). On pourrait améliorer nettement la performance de l'algorithme en mémorisant les degrés entrants dans un dictionnaaire qu'on mettrait à jour dynamiquement lors de chaque retrait de sommet. Ainsi on ne serait pas obligé de parcourir tous les sommets pour recalculer chaque degré entrant et on aurait une complexité en \(O(n+m)\).

Question 3

Dans le script de la question précédente, modifier le parcours en profondeur récursif dfs_topo pour qu'il affiche le sommet sur lequel le parcours est appelé lorsque l'appel est terminé.

Tester ordre_topologique2(graphe_info).

Comment peut-on obtenir un ordre topologique des sommets du graphe à partir de l'affichage obtenu ? Quelle est la complexité de cet algorithme ?

L'ordre d'affichage post-dfs est l'ordre topologique inversé. En effet, un sommet est affiché lorsque tous les sommets atteignables depuis lui sont affichés.

🐍 Script Python
def dfs_topo(sommet, graphe, decouvert):
    """
    Parcours en profondeur récursif augmenté 
    Marque dans  le dictionnaire decouvert  que sommet est découvert au cours du parcours
    Affiche le sommet en fin d'appel
    """
    decouvert[sommet] = True
    for v in graphe.voisins(sommet):
        if not decouvert[v]:
            dfs_topo(v, graphe, decouvert)
    print(sommet)
    
def ordre_topologique2(graphe):
    """
    Affiche un ordre topolgique inversé du graphe orienté
    """
    decouvert = {s: False for s in graphe_info.sommets()}
    for s in graphe.sommets():
        if not decouvert[s]:
            dfs_topo(s, graphe, decouvert)

Pour obtenir un ordre topologique d'un graphe orienté, il suffit donc de lancer un parcours dfs depuis chaque sommet non découvert et de stocker dans une structure linéaire chaque sommet quand le parcours dfs lancé depuis lui est terminé.

Si la structure de stockage est une file FIFO, on obtient l'ordre topologique inversé. Si c'est une pile LIFO, on obtient l'ordre topologique.

Enfin, l'augmentation du parcours dfs se fait à coût constant pour chaque appel donc la complexité dans le pire des cas est celle du parcours dfs, donc en \(O(n_{s}+m_{s})\) pour chaque appel (où \(n_{s}\) et \(m_{s}\) sont respectivement le nombre de sommets et d'arcs atteignables depuis le sommet \(s\)) et en \(O(n+m)\) pour l'ensemble du graphe. C'est bien meilleur que pour l'algorithme précédent.