################################################################################
################################################################################
#   TP01 - EVALUE
################################################################################
################################################################################

import numpy as np, numpy.random as rd
import matplotlib.pyplot as plt

################################################################################
#   EXEMPLE DE GENERATION D'UNE CONFIGURATION D'IMAGE
################################################################################

# L : nombre de lignes
# C : nombre de colonnes
# p : probabilité qu'une case soit noircie

L,C=5,5
p=.3
config=[[int(rd.random()<p) for j in range(C)] for i in range(L)]


################################################################################
#   EXEMPLE DU SUJET
################################################################################


config=[[1,0,0,1,0,0],[0,0,1,0,1,0],[0,0,0,1,1,0],[0,0,0,0,1,1],[0,0,0,0,0,0]]


################################################################################
#   AFFICHAGE DE LA CONFIGURATION
################################################################################


plt.pcolormesh(np.array(config),cmap='Greys',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()


################################################################################
#   CONSTRUCTION DU GRAPHE D'UNE IMAGE
################################################################################


def sommets(config):
    """sommets(config:list)->list
    Génération de la liste des sommets du graphe associé à une image
    représentée par une liste de listes contenant des 0 et 1
    Renvoie la liste des sommets, c'est-à-dire des pixels noirs de l'image
    """
    S=[]
    noir=1
    #
    #
    # A COMPLETER
    #
    #
    return S



def aretes(config):
    """aretes(config:list)->dict
    Génération du dictionnaire des arêtes du graphe associé à une image
    représentée par une liste de lites contenant des 0 et 1
    Renvoie le dictionnaire des arêtes de transition entre pixels noirs
    """
    A={}
    noir=1
    S=sommets(config)
    #
    #
    # A COMPLETER
    #
    #
    return A


S=sommets(config)
A=aretes(config)

################################################################################
#   PARCOURS EN PROFONDEUR
################################################################################


def dfs_rec(S,A,s0,etat):
    """dfs_rec(S:list,A:dict,s0:tuple,etat:dict)->None
    Réalise récursivement le parcours du graphe (S,A) depuis le pixel noir s0.
    Tous les pixels de la tâche contenant s0 sont visités lors du parcours.
    """
    # convention non-visité = 0, visité = 1
    non_visite,visite=0,1
    #
    #
    # A COMPLETER
    #
    #


################################################################################
#   COMPTAGE DES TACHES EN PROFONDEUR
################################################################################


def nb_taches_dfs(S,A):
    """nb_taches_dfs(S:list,A:dict)->int
    Renvoie le nombre de tâches de l'image décrite par le graphe (S,A)"""
    etat={}
    # convention non-visité = 0
    non_visite=0
    # nb : compteur de taches
    nb=0
    #
    #
    # A COMPLETER
    #
    #
    return nb

print("Parcours en profondeur")
print("nombre de taches=",nb_taches_dfs(S,A))

################################################################################
#   PARCOURS EN LARGEUR
################################################################################

from collections import deque

def bfs(S,A,s0,etat):
    """bfs(S:list,A:dict,s0:tuple,etat:dict)->None
    Réalise en largeur le parcours du graphe (S,A) depuis le pixel noir s0.
    Tous les pixels de la tâche contenant s0 sont visités lors du parcours.
    """
    # convention non-visité = 0, visité = 1
    non_visite,visite=0,1
    etat[s0]=visite
    F=deque()
    #
    #
    # A COMPLETER
    #
    #


################################################################################
#   COMPTAGE DES TACHES EN LARGEUR
################################################################################


def nb_taches_bfs(S,A):
    """nb_taches_bfs(S:list,A:dict)->int
    Renvoie le nombre de tâches de l'image décrite par le graphe (S,A)"""    
    etat={}
    # convention non-visité = 0
    non_visite=0
    # nb : compteur de taches
    nb=0
    #
    #
    # A COMPLETER
    #
    #
    return nb



plt.pcolormesh(np.array(config),cmap='Greys',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()

print("Parcours en largeur")
print("nombre de taches=",nb_taches_bfs(S,A))



################################################################################
#   DIJSKTRA
################################################################################


def dijkstra_deb_fin(S,A,deb,fin):
    dist,predec,djvu={},{},{}
    #
    #
    # A COMPLETER
    #
    #
    return predec


################################################################################
#   EXEMPLE DE CONFIGURATION
################################################################################

config=[[1]*8 for k in range(5)]
config[2][2]=0
config[3][2]=0
config[4][2]=0

config[0][5]=0
config[1][5]=0
config[2][5]=0



def aretes_dijkstra(config):
    """aretes(config:list)->dict
    Génération du dictionnaire des arêtes du graphe associé à une image
    représentée par une liste de lites contenant des 0 et 1
    Renvoie le dictionnaire des arêtes de transition entre pixels noirs
    """
    A={}
    noir=1
    S=sommets(config)
    #
    #
    # A COMPLETER
    #
    #
    return A

S,A=sommets(config),aretes_dijkstra(config)

plt.pcolormesh(np.array(config),cmap='gray',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()


################################################################################
#   COLORATION D'UN PLUS COURT CHEMIN
################################################################################

def color_ppc(config,predec,deb,fin):
    if predec=={}:
        return None
    gris=.5
    config[deb[0]][deb[1]]=gris
    config[fin[0]][fin[1]]=gris
    s=fin
    while predec[s]!=deb:
        s=predec[s]
        config[s[0]][s[1]]=gris



################################################################################
#   UN PLUS COURT CHEMIN
################################################################################

deb,fin=(2,0),(2,7)

predec=dijkstra_deb_fin(S,A,deb,fin)
color_ppc(config,predec,deb,fin)

plt.pcolormesh(np.array(config),cmap='gray',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()



################################################################################
#   DIJSKTRA ETENDU
################################################################################

from collections import deque


def dijkstra_all_deb_fin(S,A,deb,fin):
    """Recherche de tous les plus courts chemins avec Dijkstra étendu
    Le graphe doit posséder un tel plus court chemin de deb à fin"""
    dist,predec,djvu={},{},{}
    # F_config : file pour mémoriser toutes les configs rencontrées
    F_config=deque()
    # L_sol : liste des différents dictionnaires predec solutions
    L_sol=[]
    F_config.append([deb,dist,predec,djvu])
    #
    #
    # A COMPLETER
    #
    #
    return L_sol


################################################################################
#   EXEMPLE DE CONFIGURATION
################################################################################


config=[[1]*5 for k in range(3)]
config[0][3]=0
config[1][3]=0

S,A=sommets(config),aretes_dijkstra(config)

plt.pcolormesh(np.array(config),cmap='gray',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()

################################################################################
#   TOUS LES PLUS COURTS CHEMINS DE DIJKSTRA
################################################################################

deb,fin=(0,0),(2,4)

L_sol=dijkstra_all_deb_fin(S,A,deb,fin)
print("Tous les plus courts chemins obtenus par Dijkstra")


def elim_doublon(L_sol,deb,fin):
    L_ppc=[]
    L_sol_clean=[]
    #
    #
    # A COMPLETER
    #
    #
    return L_sol_clean

L_sol=elim_doublon(L_sol,deb,fin)

from copy import deepcopy

for sol in L_sol:
    predec=sol
    D_ppc=deepcopy(config)
    color_ppc(D_ppc,predec,deb,fin)
    plt.pcolormesh(np.array(D_ppc),cmap='gray',edgecolors='k', linewidth=2)
    ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()