# -*- coding: utf-8 -*- """ Created on Wed Sep 13 16:07:37 2017 @author: adomps """ import time import random as rd ################ QUELQUES GRAPHES POUR LES EXEMPLES ################################" # petit graphe connexe, Gondran page 18 L_11 = [[3], [2, 3],[1, 3],[0, 1, 2, 4],[3]] # petit graphe personnel L_andre = [[5, 6, 9], [2, 5, 8], [1], [4], [3], [0, 1, 8], [0], [], [1, 5, 9], [0, 8]] # Graphe complet K5 (chacun des cinq noeuds est lié aux quatre autres) # Il est intéressant pour bien voir le terme en O(m) dans la # complexité, en affichant tout. K_5 = [[1, 2, 3, 4], [0, 2, 3, 4], [0, 1, 3, 4], [0, 1, 2, 4], [0, 1, 2, 3]] # Graphe orienté, Fournier page 89 L_orientee_p89 = [[1, 2], [0, 5], [3], [2, 4], [4, 6], [4, 6], [7], [3, 4]] # Graphe orienté, cours ENS_Rennes. q = 0, r = 1, s = 2, etc L_Rennes = [[8], [], [0, 6], [0], [1], [2], [0, 5], [3, 9], [1, 3, 4], [7]] ################################################################################## # parcours en profondeur du graphe à partir du sommet i # Il serait bien confortable d'utiliser le tableau marques # comme une variable globale, mais je me l'interdis # par idéologie ! # Comme je ne veux pas utiliser de variable globale, je modifie # le tableau marques passé par référence. # Il faudra appeler cette fonction avec un tableau # marques préalablement mis à False pour tous les noeuds. # Pour la version avec pile explicite, voir plus bas. # L : liste d'adjacente du graphe # i : sommet étudié def parcours_profondeur_rec_0(L, i, marques) : ''' Parcours du graphe avec simple marquage des sommets visités''' marques[i] = True #print("début de l'exploration à partir du sommet", i) # Affichage des visites dans l'ordre PRÉFIXE for j in L[i] : # on parcourt les voisins de i if not marques[j] : # pour éviter de tourner en rond dans les cycles parcours_profondeur_rec_0(L, j, marques) #else : # juste pour suivi visuel # print('On étudie', i, ' mais on a déjà visité', j) print("fin de l'exploration pour le sommet ", i) # Affichage des visites dans l'ordre POSTFIXE # Complexité en O(n+m) : la fonction et appelée au plus une fois pour chaque noeud, # avec une affectation de marque[i]. Dans le pire des cas, si on va vers tous les noeuds, # cela fait du O(n). # Mais il faut aussi faire un test << if not marques[j] >> pour tous les voisins de i, # dont le nombre est le degré de i. Dans le pire des cas, on peut avoir autant # de test que d'arêtes (2 fois plus en fait car on regarde dans les deux sens). # Cela fait du O(m). Donc en tout, O(n+m). # B ien expliquée dans, http://mapage.noos.fr/laurent.pierre/graphe/parcours_en_profondeur.pdf # Exemple marques = [False for _ in range(len(K_5))] parcours_profondeur_rec_0(K_5, 0, marques) print(marques) # Exemple n = len(L_andre) marques = [False for _ in range(n)] parcours_profondeur_rec_0(L_andre, 0, marques) print(marques) # Renvoie un booléen indiquant si le graphe est connexe. def est_connexe(L) : # L est ls liste d'adjacence d'un graphe n = len(L) i = 0 # on peut démarre de n'importe quel nœud marques = n * [False] parcours_profondeur_rec_0(L, i, marques) for m in marques : if not m : return False return True # Petits essais print('test de connexité pour L_11') print(est_connexe(L_11)) print('test de connexité pour L_andre') print(est_connexe(L_andre)) print('test de connexité de L_touffue') print(est_connexe(L_touffue)) # Dans cette version, on renvoie aussi la liste des noeuds # connectés à i qui forment sa composante connexe. # On pourrait se passer des booléens marques, le test # if not marques[j] serait remplacé par if j not in L_atteignables. # Mais cela nécessité un parcours de cette liste ce qui nuit à la # complexité en la multipliant par O(n) # Comme ne ne veux pas utiliser de variable globale, je modifie # L_atteignables et marques passés par référence. # Selon la position de l'instruction L_atteignables.append(i), # on obtiendra les listes dans l'ordre POSTFIXE our PRÉFIXE def parcours_profondeur_rec_1(L, i, marques, L_atteignables = []) : ''' parcours du graphe avec construction de la liste des sommets connectés à i ''' #L_atteignables.append(i) # Avec cette ligne ici, on les obtient dans l'ordre PRÉFIXE marques[i] = True for j in L[i] : # cette liste contient les voisins de i if not marques[j] : # pour éviter de tourner en rond dans les cycles parcours_profondeur_rec_1(L, j, marques, L_atteignables) L_atteignables.append(i) # Avec cette ligne ici, on les obtient dans l'ordre POSTFIXE # J'encapsule la partie récursive pour écrire une fonction # qui renvoie la composante connexe. def parcours_profondeur(L, i) : ''' renvoie la liste des sommets connectés à i ''' n = len(L) atteignables = [] marques = n * [False] parcours_profondeur_rec_1(L, i, marques, atteignables) return atteignables # Petit essai i_depart = 0 reponse = parcours_profondeur(L_andre, i_depart) print('atteignables_ partir de ', i_depart, ':', reponse) # On réutilise la fonction parcours_profondeur_rec_1. # Le caractère postfixe ou préfixe est donc hérité de cette fonction. # On ne peut pas utiliser la version encapsulée car on veut travailler # sur la même liste marques def composantes_connexes(L) : ''' renvoie les composantes connexes d'un graphe ''' n = len(L) Composantes = [] marques = n * [False] for i in range(n) : # on parcourt les noeuds if not marques[i] : # qui n'ont pas déjà été visités L_atteignables = [] # on crée une nouvelle composante connexe parcours_profondeur_rec_1(L, i, marques, L_atteignables) Composantes.append(L_atteignables) return Composantes print(composantes_connexes(L_11)) print(composantes_connexes(L_andre)) print(composantes_connexes(L_touffue)) ######################################################## # PARTIE SUR KOSARAJU # Parcourt tout le graphe et renvoie les sommets. # On peut réutiliser la fonction composantes_connexes : il suffit # de concaténer les composantes. # On obtient l'ordre postfixe si la fonction # parcours_rec_1 est elle-même postfixe def parcours_enumeration(L) : liste_des_composantes = composantes_connexes(L) P = [] for composante in liste_des_composantes : P += composante # concaténation return P # Exemple P = parcours_enumeration(L_andre) print(P) def inverse_graphe(L) : n = len(L) L_inv = [ [] for _ in range(n)] for i in range(n) : # On parcourt les liste L liste_voisins = L[i] for j in liste_voisins : # Pour ces valeurs de j, il y a un arc de i vers j dans L L_inv[j].append(i) # donc on place un arc de j vers i dans L_inv return L_inv # Écriture en traduisant simplement l'algo. def Kosaraju(L) : n = len(L) P = parcours_enumeration(L) # sommets en ordre postfixe P_envers = [P[i] for i in range(n-1, -1, -1)] # inversion de l'odre postfixe. Liste.inverse() L_inv = inverse_graphe(L) marques = [False for _ in range(n)] Composantes = [] for x in P_envers : if not marques[x] : L_atteignables = [] parcours_profondeur_rec_1(L_inv, x, marques, L_atteignables) Composantes.append(L_atteignables) return Composantes # Exemples Kosaraju(L_orientee_p89) Kosaraju(L_Rennes) ###################################################################### # Parcours qui enregistre le rang de chaque noeud visité # dans le parcours en renvoie aussi le tableau des pères # de chaque élément dans le parcours def parcours_profondeur_rec_2(L, i, marques, peres, indices) : global ind # C'est tellement plus pratique !!! marques[i] = True indices[i] = ind ind += 1 for j in L[i] : # cette liste contient les voisins de i if not marques[j] : # pour éviter de tourner en rond dans les cycles peres[j] = i parcours_profondeur_rec_2(L, j, marques, peres, indices) # Encapsule la fonction précédente ind = 0 # début de la numérotation, variable globale def parcours_avec_peres(L, i) : n = len(L) marques = n * [False] peres = n * ['*'] # indices = n * ['*'] # idem parcours_profondeur_rec_2(L, i, marques, peres, indices) return marques, peres, indices # essai parcours_avec_peres(L_andre, 0) ##### UTILISATION DE PILES ################################## # Fait la même chose que parcours_profondeur_0, # mais on n'a pas besoin d'initialiser les marques avant. # Exécuter d'abord le fichier avec les fonctions pour les piles def parcours_profondeur_pile_0(L, i) : ''' parcours du graphe qui marque les sommet connectés à i en renvoie le tableau des marques ''' n = len(L) marques = n * [False] Pile = cree_pile() empile(i, Pile) while not est_vide(Pile) : a = depile(Pile) marques[a] = True for j in L[a] : # on parcourt les voisins de a if not marques[j] : empile(j, Pile) return marques # Exemple print(parcours_profondeur_pile_0(L_andre, 0)) # Comparaison avec l'algo récursif marques = [False for _ in range(len(L_andre))] parcours_profondeur_rec_0(L_andre, 1, marques) print(marques) def parcours_profondeur_pile_1(L, i) : ''' parcours du graphe qui renvoie la liste des sommets connectés à i ''' atteignables = [] n = len(L) marques = n * [False] Pile = cree_pile() empile(i, Pile) while not est_vide(Pile) : a = depile(Pile) atteignables.append(a) # on pourrait s'en passer ... print('a', a, 'atteignables', atteignables) marques[a] = True for j in L[a] : # on parcourt les voisins de a if not marques[j] : empile(j, Pile) return atteignables # ... et trouver les atteignables avec la tableau marques # Exemple print(parcours_profondeur_pile_1(L_touffue, 0))