Détection de cycle eulérien¶

Les sommets des graphes sont des entiers indexés à partir de 0 et les relations d'djacence sont représentées par des listes d'adjacence.

Algorithme de Fleury¶

Source : https://www.irif.fr/~habib/Documents/Eulerien.pdf

In [1]:

def cycle_eulerien(graphe, depart, debug = False):
    """
    Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n
    Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste)
    Implémentation de l'algorithme de Fleury
    """
    pile_aretes_vues = []
    source = depart
    dest = graphe[depart][0]
    #depart_cycle : départ du cyle
    #depart_cycle_inter : départ d'un cycle intermédaire inséré dans le cycle final qui remiera depart_cycle à depart_cycle
    depart_cycle = depart_cycle_inter = depart
    pile_aretes_vues.append((None, None))
    cycle = []
    #tant que la pile est vide
    #il reste des sommets sur le chemin à partir desquels on n'a pas terminé l'exploration de cycles intermédiaires
    # c'est à dire des sommets qu'on n'a pas encore inséré dans le cycle
    while pile_aretes_vues: 
        #on enlève l'arête (source, dest) du graphe qui relie source à dest
        if dest in graphe[source]:
            graphe[source].remove(dest)  #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles
        if source in graphe[dest]: #cas d'un graphe non orienté
            graphe[dest].remove(source)
        # s'il reste des aretes non explorées partant du sommet dest
        if len(graphe[dest]) > 0:
            #on empile l'arête qu'on vient de parcourir
            pile_aretes_vues.append((source, dest))      
            #on met à jour source, dest avec l'arête libre issue de dest
            source, dest = dest, graphe[dest][0]
        #sinon il n'y a plus d'arete libre partant de dest
        else:
            #si on n'est pas revenu au sommet depart_cycle_inter le graphe n'est pas eulérien
            if dest != depart_cycle_inter: #pas de cycle eulérien, sommet de degré impair
                return (False, dest)
            #sinon on a terminé un cycle intermédiaire
            else:
                #on peut insérer le sommet dest dans le cycle eulérien car plus aucune arete libre n'en part
                cycle.append(dest)
                #on recherche un cycle après du sommet précédent (source) dans notre exploration 
                depart_cycle_inter = source
                #on dépile l'arete qui nous avait amené en ce sommet source (dest après dépilement)
                #en effet la pile permet de mémoriser tous les sommets (extémité d'arete dans la pile)
                #qui n'ont pas encore été inséré dans le chemin
                source, dest = pile_aretes_vues.pop()
    #on referme le cycle avec le sommet de départ
    cycle.append(depart_cycle)
    return (True, cycle)

def cycle_eulerien(graphe, depart, debug = False): """ Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste) Implémentation de l'algorithme de Fleury """ pile_aretes_vues = [] source = depart dest = graphe[depart][0] #depart_cycle : départ du cyle #depart_cycle_inter : départ d'un cycle intermédaire inséré dans le cycle final qui remiera depart_cycle à depart_cycle depart_cycle = depart_cycle_inter = depart pile_aretes_vues.append((None, None)) cycle = [] #tant que la pile est vide #il reste des sommets sur le chemin à partir desquels on n'a pas terminé l'exploration de cycles intermédiaires # c'est à dire des sommets qu'on n'a pas encore inséré dans le cycle while pile_aretes_vues: #on enlève l'arête (source, dest) du graphe qui relie source à dest if dest in graphe[source]: graphe[source].remove(dest) #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles if source in graphe[dest]: #cas d'un graphe non orienté graphe[dest].remove(source) # s'il reste des aretes non explorées partant du sommet dest if len(graphe[dest]) > 0: #on empile l'arête qu'on vient de parcourir pile_aretes_vues.append((source, dest)) #on met à jour source, dest avec l'arête libre issue de dest source, dest = dest, graphe[dest][0] #sinon il n'y a plus d'arete libre partant de dest else: #si on n'est pas revenu au sommet depart_cycle_inter le graphe n'est pas eulérien if dest != depart_cycle_inter: #pas de cycle eulérien, sommet de degré impair return (False, dest) #sinon on a terminé un cycle intermédiaire else: #on peut insérer le sommet dest dans le cycle eulérien car plus aucune arete libre n'en part cycle.append(dest) #on recherche un cycle après du sommet précédent (source) dans notre exploration depart_cycle_inter = source #on dépile l'arete qui nous avait amené en ce sommet source (dest après dépilement) #en effet la pile permet de mémoriser tous les sommets (extémité d'arete dans la pile) #qui n'ont pas encore été inséré dans le chemin source, dest = pile_aretes_vues.pop() #on referme le cycle avec le sommet de départ cycle.append(depart_cycle) return (True, cycle)

In [2]:

# Tests
graphe1 = [[1], [2], [3], [0]] #graphe orienté eulérien
cycle_eulerien(graphe1, 0, True)

# Tests graphe1 = [[1], [2], [3], [0]] #graphe orienté eulérien cycle_eulerien(graphe1, 0, True)

Out[2]:

(True, [0, 3, 2, 1, 0])

In [3]:

# Tests
graphe2 = [[3,1], [0,2], [1,3], [0,2]] #graphe non orienté eulérien
cycle_eulerien(graphe2, 0, True)

# Tests graphe2 = [[3,1], [0,2], [1,3], [0,2]] #graphe non orienté eulérien cycle_eulerien(graphe2, 0, True)

Out[3]:

(True, [0, 1, 2, 3, 0])

In [4]:

# Tests
graphe3 = [[1], [2,4],[3],[1], [0] ] #graphe  orienté eulérien
cycle_eulerien(graphe3, 0, True)

# Tests graphe3 = [[1], [2,4],[3],[1], [0] ] #graphe orienté eulérien cycle_eulerien(graphe3, 0, True)

Out[4]:

(True, [0, 4, 1, 3, 2, 1, 0])

In [5]:

# Tests
graphe3 = [[1], [2,4],[3],[1, 5], [0], []] #graphe  orienté non eulérien
cycle_eulerien(graphe3, 0, True)

# Tests graphe3 = [[1], [2,4],[3],[1, 5], [0], []] #graphe orienté non eulérien cycle_eulerien(graphe3, 0, True)

Out[5]:

(False, 5)

In [6]:

#Tests graphe RT
graphe4= [[1,2], [0,2,3,4],[0,1,4,6],[1,5],[1,2,5,6],
          [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9],
          [5,7,8,11],[5,11],[10,9]
         ] #graphe  non orienté  eulérien
cycle_eulerien(graphe4, 0, True)

#Tests graphe RT graphe4= [[1,2], [0,2,3,4],[0,1,4,6],[1,5],[1,2,5,6], [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9], [5,7,8,11],[5,11],[10,9] ] #graphe non orienté eulérien cycle_eulerien(graphe4, 0, True)

Out[6]:

(True, [0, 2, 6, 7, 9, 11, 10, 5, 9, 8, 7, 5, 6, 4, 5, 3, 1, 4, 2, 1, 0])

Détection de parcours eulérien¶

In [7]:

def liste_sommet_impair(graphe):
    """Renvoie la liste des sommets de degré impair d'un graphe
    représenté sous forme de liste d'adjacence avec les sommets 
    numérotés à partir de 0
    """
    sommet_impair = []
    for sommet in range(len(graphe)):
        if len(graphe[sommet]) % 2 == 1:
            sommet_impair.append(sommet)
    return sommet_impair


def chemin_source_destination(graphe, source, destination):
    dejavu = [False] * len(graphe)
    pile = [source]
    chemin = []
    while pile[-1] != destination:
        sommet = pile.pop()
        dejavu[sommet] = True
        chemin.append(sommet)
        for voisin in graphe[sommet]:
            if not dejavu[voisin]:
                pile.append(voisin)
    chemin.append(destination)
    for k in range(len(chemin) - 1):
        source = chemin[k]
        dest = chemin[k + 1]
        if dest in graphe[source]:
            graphe[source].remove(dest)  #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles
        if source in graphe[dest]: #cas d'un graphe non orienté
            graphe[dest].remove(source)
    return chemin

def parcours_eulerien(graphe, debug = False):
    """
    Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n
    Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste)
    Implémentation de l'algorithme de Fleury
    """
    sommet_impair = liste_sommet_impair(graphe)
    if len(sommet_impair) == 0: #tous sommets pairs, cycle eulérien
        return cycle_eulerien(graphe, 0, debug)
    elif len(sommet_impair) == 2: #2 sommets impairs, parcours eulérien
        sommet1, sommet2 = sommet_impair
        print(sommet1, sommet2)
        chemin_entre_impair = chemin_source_destination(graphe, sommet1, sommet2)
        print(chemin_entre_impair)
        premier_cycle = []
        eulerien = True
        if len(graphe[sommet1]) > 0:
            (eulerien, premier_cycle) = cycle_eulerien(graphe, sommet1, debug)
        second_cycle = []
        if eulerien:
            if len(graphe[sommet2]) > 0:
                (eulerien, second_cycle) = cycle_eulerien(graphe, sommet2, debug)  
        if premier_cycle:
            premier_cycle = premier_cycle[:-1]
        if second_cycle:
            second_cycle = second_cycle[1:]
        return (eulerien, premier_cycle + chemin_entre_impair  + second_cycle)
    else:   #nb de sommets impairs différents de 2 : pas de parcours eulérien
        return (False, [])

def liste_sommet_impair(graphe): """Renvoie la liste des sommets de degré impair d'un graphe représenté sous forme de liste d'adjacence avec les sommets numérotés à partir de 0 """ sommet_impair = [] for sommet in range(len(graphe)): if len(graphe[sommet]) % 2 == 1: sommet_impair.append(sommet) return sommet_impair def chemin_source_destination(graphe, source, destination): dejavu = [False] * len(graphe) pile = [source] chemin = [] while pile[-1] != destination: sommet = pile.pop() dejavu[sommet] = True chemin.append(sommet) for voisin in graphe[sommet]: if not dejavu[voisin]: pile.append(voisin) chemin.append(destination) for k in range(len(chemin) - 1): source = chemin[k] dest = chemin[k + 1] if dest in graphe[source]: graphe[source].remove(dest) #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles if source in graphe[dest]: #cas d'un graphe non orienté graphe[dest].remove(source) return chemin def parcours_eulerien(graphe, debug = False): """ Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste) Implémentation de l'algorithme de Fleury """ sommet_impair = liste_sommet_impair(graphe) if len(sommet_impair) == 0: #tous sommets pairs, cycle eulérien return cycle_eulerien(graphe, 0, debug) elif len(sommet_impair) == 2: #2 sommets impairs, parcours eulérien sommet1, sommet2 = sommet_impair print(sommet1, sommet2) chemin_entre_impair = chemin_source_destination(graphe, sommet1, sommet2) print(chemin_entre_impair) premier_cycle = [] eulerien = True if len(graphe[sommet1]) > 0: (eulerien, premier_cycle) = cycle_eulerien(graphe, sommet1, debug) second_cycle = [] if eulerien: if len(graphe[sommet2]) > 0: (eulerien, second_cycle) = cycle_eulerien(graphe, sommet2, debug) if premier_cycle: premier_cycle = premier_cycle[:-1] if second_cycle: second_cycle = second_cycle[1:] return (eulerien, premier_cycle + chemin_entre_impair + second_cycle) else: #nb de sommets impairs différents de 2 : pas de parcours eulérien return (False, [])

In [8]:

#Tests graphe RT
graphe4= [[1,2], [0,2],[0,1,4,6],[5],[2,5,6],
          [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9],
          [5,7,8,11],[5,11],[10,9]
         ] #graphe  non orienté  eulérien
parcours_eulerien(graphe4, True)

#Tests graphe RT graphe4= [[1,2], [0,2],[0,1,4,6],[5],[2,5,6], [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9], [5,7,8,11],[5,11],[10,9] ] #graphe non orienté eulérien parcours_eulerien(graphe4, True)

3 4
[3, 5, 10, 11, 9, 8, 7, 6, 4]

Out[8]:

(True, [3, 5, 10, 11, 9, 8, 7, 6, 4, 5, 9, 7, 5, 6, 2, 1, 0, 2, 4])