#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 29 18:01:50 2023

@author: vincentleprince
"""


# Matrice servant d'exemple dans le 1 :
M = [[0, 1,1,0,0,0,0,0,0,0 ],
             [1,0,1, 1,1,0,0,0,0,0],
             [1,1,0,1,0,1,0,0,0,0],
             [0,1,1,0,1,1,1,0,0,0],
            [0,1,0,1,0,1,1,1,0,0],
            [0,0,1,1,1,0,1,0,0,1],
             [0,0,0,1,1,1,0,0,1,0],
             [0, 0,0,0,1,0,0,0,1,0 ],
             [0, 0,0,0,0,0,1,1,0,0 ],
             [0, 0,0,0,0,1,0,0,0,0 ]]


# Matrice servant d'exemple pour les parcours :
M1 = [[0,1,1,0,0,0,0],
      [1,0,0,1,0,0,0],
      [1,0,0,0,0,0,1],
      [0,1,0,0,1,1,0],
      [0,0,0,1,0,0,0],
      [0,0,0,1,0,0,0],
      [0,0,1,0,0,0,0]
      ]



def parcours_prof(M,sommet):
    n = len(M)
    pile = [sommet]
    etats_sommets = [0 for s in range(n)]
    etats_sommets[sommet] = 1  # 0 pour les sommets non encore traiées
                               # 1 pour les sommets dans la pile
                               # 2 pour les sommets visités 
    ordre_sommets_visites = []
    liste_peres = [-1 for s in range(n)] # pour reconstituer un chemin
    while pile != []:
        s = pile.pop()
        ordre_sommets_visites.append(s)
        etats_sommets[s] = 2
        for t in range(n): 
            if M[s][t]==1 and etats_sommets[t] == 0 :
                # mise à jour de pile et sommets_visites (et liste_peres)
                pile.append(t)
                etats_sommets[t] = 1
                liste_peres[t] = s
                
    return ordre_sommets_visites ,liste_peres

# tests : 
print(parcours_prof(M,0)) 

print(parcours_prof(M1,0)) 

def chemin_prof(M,sommet1,sommet2):
    liste_peres = parcours_prof(M,sommet1)[1]
    s = sommet2
    cheminS1S2 = [s]
    
    while s != sommet1:
        s = liste_peres[s]
        cheminS1S2.append(s)
    cheminS1S2.reverse()
    return cheminS1S2

print(chemin_prof(M,0,7))


    


# parcours en largeur
    
def parcours_larg(M,sommet):
    n = len(M)
    file = [sommet]
    etats_sommets = [0 for s in range(n)]
    etats_sommets[sommet] = 1 # 0 pour les sommets non encore traiées
                               # 1 pour les sommets dans la pile
                               # 2 pour les sommets visités 
    ordre_sommets_visites = []
    
    while file != []:
        s = file.pop(0)
        ordre_sommets_visites.append(s)
        etats_sommets[s] = 2
        for t in range(n): 
            if M[s][t]==1 and etats_sommets[t] == 0 :
                # mise à jour de file et sommets_visites (et liste_peres)
                file.append(t)
                etats_sommets[t] = 1
                 
                
    return ordre_sommets_visites  

print(parcours_larg(M,0)) 

print(parcours_larg(M1,0)) 


def parcours_larg_dist(M,sommet):
    n = len(M)
    file = [sommet]
    etats_sommets = [0 for s in range(n)]
    etats_sommets[sommet] = 1 # 0 pour les sommets non encore traiées
                               # 1 pour les sommets dans la pile
                               # 2 pour les sommets visités 
    liste_dist = [0 for i in range(n)]

    liste_dist[sommet] = 0
    
    while file != []:
        s = file.pop(0)
        etats_sommets[s] = 2
        for t in range(n): 
            if M[s][t]==1 and etats_sommets[t] == 0 :
                # mise à jour de file et sommets_visites (et liste_peres)
                file.append(t)
                etats_sommets[t] = 1
                liste_dist[t] =  liste_dist[s] + 1
                
    return liste_dist 
 
print(parcours_larg_dist(M,0)) 

print(parcours_larg_dist(M1,0))     


# fonction récursive pour le parcours en profondeur:
    
def parcours_prof_rec(M,sommet):
    n = len(M)
    etats_sommets = [0 for s in range(n)] # passe à 1 lorsqu'un
                                          # sommet est visité
    liste_peres = [-1 for s in range(n)]
    ordre_sommets_visites = []
    def aux(s):
        etats_sommets[s] = 1
        ordre_sommets_visites.append(s)
        #print("visite du sommet " + str(sommet)) # pour constater l'ordre des appels
        for t in range(n): 
            if M[s][t]==1 and etats_sommets[t] == 0:
                liste_peres[t] = s
                aux(t)
                
    aux(sommet)
    return ordre_sommets_visites , liste_peres
                
 
# tests : 
print(parcours_prof_rec(M1,0))  
print(parcours_prof(M1,0))   
# remarque : on n'obtient pas exactement les mêmes réponses   
#            du fait des choix différents qui peuvent être faits 
#            dans le choix de l'ordre dans lequel on traite les successeurs.



print(parcours_prof_rec(M1,0))  
print(parcours_prof(M1,0))