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

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


blanc,gris,noir=0,1,2
non_visite,visite=0,1


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

config=[[0, 0, 2, 0, 0, 0, 0], [0, 2, 2, 2, 0, 0, 0], [2, 0, 2, 0, 0, 0, 2], [0, 0, 0, 0, 0, 2, 2], [0, 0, 0, 0, 0, 0, 2]]


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


def aff(config):
    plt.pcolormesh(np.array(config),cmap='Greys')
    ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()


################################################################################
#   EXERCICE 1
################################################################################


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 2
    Renvoie la liste des sommets, c'est-à-dire des pixels noirs de l'image
    """
    S=[]
    #
    #
    # 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 2
    Renvoie le dictionnaire des arêtes de transition entre pixels noirs
    """
    A={}
    S=sommets(config)
    #
    #
    #  A COMPLETER
    #
    #
    return A


################################################################################
#   EXERCICE 2
################################################################################


from collections import deque


def visit_comp(A,s0,comp,etat):
    """visit_comp(A:dict,s0:tuple,comp:list,etat:dict)->None
    Réalise le parcours en largeur du graphe d'arêtes A depuis le pixel noir s0.
    Tous les pixels de la tâche contenant s0 sont visités et placés dans la liste comp.
    """
    F=deque()
    F.append(s0)
    #
    #
    # A COMPLETER
    #
    #

def comp_connexe(config):
    """comp_connexe(config:list)->dict
    Renvoie le dictionnaire des composantes connexes au format k:[ ... ]
    avec k entier entre 1 et n le nombre de composantes connexes.
    La valeur associée à k est la liste des pixels de la composante."""
    C={}
    S=sommets(config)
    A=aretes(config)
    etat={}
    #
    #
    # A COMPLETER
    #
    #
    return C



################################################################################
#   EXERCICE 3
################################################################################


def bfs(A,s0):
    """bfs(A:dict,s0:tuple)->dict
    Renvoie le dictionnaire des distances entre s0 et les sommets
    appartenant à la même composante connexe que s0."""
    dist={}
    F=deque()
    #
    #
    # A COMPLETER 
    #
    #
    return dist
    
def diametre_comp(config,comp):
    """diametre_comp(config:list,comp:list)->int
    Renvoie le diametre de la tâche noire décrite par la composante connexe comp."""
    diam=0
    A=aretes(config)
    #
    #
    # A COMPLETER
    #
    #
    return diam

def diametre(config):
    """diametre(config:list)->list
    Renvoie la liste des couples (k,d) avec k le numéro d'une tâche et d son diamètre."""
    return []
    # SUPPRIMER LA LIGNE CI-DESSUS
    #
    # A COMPLETER
    #
    #



    
################################################################################
#   EXERCICE 4
################################################################################


def tri(L):
    """tri(L:list)->list
    Réalise le tri d'une liste de couples (k,d) selon la deuxième composante."""
    return []
    # SUPPRIMER LA LIGNE CI-DESSUS
    #
    # A COMPLETER
    #
    #
    

L_diam=diametre(config)
print("diametre=",L_diam)
aff(config)

L_diam_tri=tri(L_diam)    
print("diametre trié=",tri(L_diam))
n=len(L_diam)

gros_diam=L_diam_tri[int(.8*n):]
L_comp=comp_connexe(config)

#
#
# A COMPLETER
#
#



aff(config)