########################################################################
## Voici un cours programme en python pour illustrer l'exercice sur le
## parcours en profondeur recursif vu en TD. Vous aurez besoin de
## la version 3 de python a cause du mot cle "nonlocal"

## usage : python3 pprecursif.py

## pour toute question ou commentaire sur le code n'hesitez pas a me
## joindre par mail : 
## guillaume [point] guegan [chez] l i r m m [point] fr
########################################################################

# on utilise un dictionnaire de listes pour representer un graphe
# ici le graphe de petersen
petersen = {
    1 : [ 2, 3, 4 ],
    2 : [ 1, 5, 9 ],
    3 : [ 1, 7, 8 ],
    4 : [ 1, 6, 0 ],
    5 : [ 2, 6, 8 ],
    6 : [ 4, 5, 7 ],
    7 : [ 3, 6, 9 ],
    8 : [ 3, 5, 0 ],
    9 : [ 2, 7, 0 ],
    0 : [ 4, 8, 9 ],
}
# petersen moins l'arete 12 
petersen2 = {
    1 : [ 3, 4 ],
    2 : [ 5, 9 ],
    3 : [ 1, 7, 8 ],
    4 : [ 1, 6, 0 ],
    5 : [ 2, 6, 8 ],
    6 : [ 4, 5, 7 ],
    7 : [ 3, 6, 9 ],
    8 : [ 3, 5, 0 ],
    9 : [ 2, 7, 0 ],
    0 : [ 4, 8, 9 ],
}
# un graphe non connexe
nconnexe = {
    0 : [ 1, 2 ],
    1 : [ 0, 2 ],
    2 : [ 0, 1 ],
    3 : [ 4 ],
    4 : [ 3 ]
}

## notre beau parcours recursif
def parcoursProfondeur(v, G):
    # les initialisations
    n = len(G); t = 1 # n nbr de sommets de G, t sert a remplir ordre
    ordre = n * [-1]; pere = list( range(n) ) # les 2 tbls que l'on retourne
    dejaVu = n * [ False ] # dejaVu[x]=Vrai ssi on a deja visite le sommet x 
    
    # definition d'une fonction locale
    def pp(x, G):
        nonlocal t # nonlocal n'existe qu'en python _3_ 
        dejaVu[x] = True
        ordre[x] = t
        t += 1
        for y in G[x]: # pour tous les voisins du sommet x
            if not dejaVu[y]: 
                pere[y] = x
                pp(y, G)

    # appel de la fonction locale et retour des resultats
    pp(v, G)
    return (ordre, pere)

## le code execute par l'appel du programme
print( str( parcoursProfondeur(8, petersen2) ) )
print( str( parcoursProfondeur(0, nconnexe) ) )

## note 1 : python c'est cool
## note 2 : pourquoi je dois utiliser "nonlocal" pour t et pas pour les
## listes ordre, pere et dejavu :
  # http://stackoverflow.com/questions/11164149/python-closure-global-strangeness
  # http://stackoverflow.com/questions/12182068/python-closure-function-losing-outer-variable-access
  # http://stackoverflow.com/questions/4851463/python-closure-write-to-variable-in-parent-scope
  # etc...