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



 
#####################################
## Les représentations d'un graphe ##
#####################################


def mat_vers_listes(M):

    
def listes_vers_mat(L):
    
        




## Pour test (graphes générés aléatoirement) ##



# M1=np.array(
# [[0. 1. 0.],
#  [1. 0. 1.],
#  [0. 1. 0.]])
# L1=[[1], [0, 2], [1]]

# M2=np.array(
# [[0., 0., 0., 0.],
#  [0., 0., 1., 0.],
#  [0., 1., 0., 1.],
#  [0., 0., 1., 0.]])
# L2=[[], [2], [1, 3], [2]]

# M3=np.array(
# [[0., 1., 0., 0.],
#  [1., 0., 1., 1.],
#  [0., 1., 0., 0.],
#  [0., 1., 0., 0.]])
# L3=[[1], [0, 2, 3], [1], [1]]



 




#######################################
## Recherche de composantes connexes ##
#######################################

## Quelques exemples de listes d'adjacence de graphes non orientés
## à 6 ou 10 sommets pour test (graphes générés aléatoirement)

# [[3, 4], [5], [], [0], [0], [1]]
# [[1, 3, 5], [0], [], [0, 5], [5], [0, 3, 4]]
# [[2, 5], [4], [0, 3], [2], [1, 5], [0, 4]]
# [[2, 4], [2], [0, 1, 4], [], [0, 2], []]
# [[3], [5], [3, 4], [0, 2], [2], [1]]
# [[7], [3, 5, 8], [6], [1, 9], [5], [1, 4, 7, 8], [2], [0, 5], [1, 5], [3]]
# [[1, 3], [0], [], [0], [5, 6], [4, 7], [4], [5, 9], [], [7]]
# [[2], [5], [0, 9], [8], [5, 8], [1, 4], [], [9], [3, 4], [2, 7]]
# [[2, 5], [4, 7, 8, 9], [0], [4, 7], [1, 3, 7], [0], [], [1, 3, 4], [1], [1]]
# [[2, 7], [2, 4, 5], [0, 1, 3, 8], [2, 4, 7], [1, 3], [1, 8], [7], [0, 3, 6, 9], [2, 5], [7]]



## algo brutal

def compo_cnxs(M):


 

 ## par parcours
 
def comp_conn(L,i):
    """ composante connexe du sommet i, du graphe avec listes d'ajacence L"""
    n = len(L) ## nb de sommets
    visites = ..... ## statut d'un sommet (visite ou pas)
     						   ## initialement aucun sommet n'est visité
    .....    ## on marque i comme visité
    a_explorer = .....  ## et on l'ajoute à la liste "à explorer"
    while len(a_explorer) > 0:
        j = a_explorer.pop(0) ## commande HP : retire le premier sommet de la liste
                            ## a_explorer, et stocke sa valeur dans une variable j



    return [i for i in range(n) if visites[i]==1] ## on renvoie la liste 
                                                  ## des sommets visités

 
def compo_connexes(L):
    n = len(L)

    
    





####################################
## Tri topologique : algo de Kahn ##
####################################
 

def deg_entrant_nul(M):

    
def enlever_lignecol(M,i,j):
    """ prend une matrice M et renvoie cette matrice privée de la
    i-ème ligne et j-ème colonne"""
    (n,p) = np.shape(M) # format de la matrice
    l=...  # la liste [0,1,...,i-1,i+1,...,n-1]
    c=...  # la liste [0,1,...,j-1,j+1,...,p-1]
    return np.array([[M[a,b] for b in c] for a in l])


 


def tri_topo(M):
    """ effectue un tri topologique des sommets
    d'un graphe orienté acyclique de matrice
    d'adjacence M"""
    tri=[] # contiendra la liste des sommets triés
    n=np.shape(M) # le nombre de sommets du graphe
    liste_sommets = ... # contient initialement tous les sommets du graphe
    for k in range(n):
        somm = ... # l'indice d'un sommet de degré entrant nul
        ... # on ajoute le sommet à la liste des sommets triés
        ...
        ... # et de la liste de ses sommets 
    return tri

vetements=['manteau','chaussures','culotte',
           't-shirt','pull','montre','pantalon',
           'bonnet','chaussettes','sac à dos']

# 0:manteau
# 1:chaussures
# 2:culotte
# 3:t-shirt
# 4:pull
# 5:montre
# 6:pantalon
# 7:bonnet
# 8:chaussettes
# 9:sac à dos


## liste d'adjacence du graphe de dépendance des vêtements
# L_vet=[
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
#    [...],
# ]


## et la matrice d'adjacence qui en résulte

# mat_vet=listes_vers_mat(L_vet)