#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Chapitre 3 : Un peu de graphes

PCSI2 - LAS - Le Raincy
"""

##Exemple 9 Pile

pile = []
pile.append(1)
pile.append(2)
pile.append('ajoute')
print('Etat de la pile : ', pile)
for i in range(len(pile)):
    element = pile.pop()
    print('Etat de la pile : ', pile)
    print('Element dépilé : ', element)

##Exemple 9 File
from collections import deque

file = deque()
print('Etat de la file : ', file)
file.append('a')
print('Etat de la file : ', file)
file.append('b')
print('Etat de la file : ', file)
file.append('c')
print('Etat de la file : ', file)
for i in range(len(file)):
    element = file.popleft()
    print('Etat de la file : ', file)
    print('Element défilé : ', element)


##Exemple 10
def est_connexe(G:dict, origine) -> bool:
    '''
    Entrée : G graphe donné par le dictionnaire
    de ses listes d'adjacence
    origine est un sommet de G
    Sortie : renvoie True si G est connexe
    False sinon
    '''
    visites = {} #sommets visités
    attente = [origine] #pile
    while len(attente) > 0:
        sommet = attente.pop()
        if sommet not in visites:
            print('Sommet visité : ', sommet)
            visites[sommet] = True
            for voisin in G[sommet]:
                attente.append(voisin)
    if len(visites) == len(G):
        return True
    else:
        return False

#Tests
G1 = {0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2]}
#assert est_connexe(G1, 0)
G2 = {0:[1,4], 1:[0,2], 2:[0,3], 3:[2,4,5], 4:[0,3,5], 5:[3,4]}
assert est_connexe(G2, 0)
G3 = {0:[1,2], 1:[0,2], 2:[0,1], 3:[]}
#assert not est_connexe(G3, 0)

##Exemple 11
from collections import deque #pour les files
def cycle(G:dict, origine) -> bool:
    '''
    Entrée : G est un graphe connexe donné par
    le dictionnaire de ses listes d'adjacences,
    origine est un sommet de G.
    Sortie : renvoie True s'il y a un cycle
    dans le graphe et False sinon
    '''
    distances = {s: None for s in G} #dist à origine
    distances[origine] = 0
    attente = deque() #Une file
    attente.append(origine)
    while len(attente) > 0:
        sommet = attente.popleft()
        print('Sommet visité : ', sommet)
        for voisin in G[sommet]:
            if distances[voisin] == None:
                distances[voisin] = distances[sommet] + 1
                attente.append(voisin)
            elif distances[voisin] >= distances[sommet]:
                return True
    return False

#Tests
G1 = {0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2]}
assert cycle(G1, 0)
G2 = {0:[1,4], 1:[0,2], 2:[0,3], 3:[2,4,5], 4:[0,3,5], 5:[3,4]}
assert cycle(G2, 0)