#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Aug 21 10:02:29 2018

@author: adomps
"""


#####  Graphes exemples définis par listes d'adjacence
Listes_graphe_exams = [[1, 2, 3, 6], [0, 2, 3, 4], [0, 1, 3, 5, 6],
                      [0, 1, 2, 4, 5], [1, 3, 5, 6], [2, 3, 4, 6], [0, 1, 2, 4, 5]]

Listes_graphe_produits_chimiques = [[1, 2, 3, 6, 7],
                                   [0, 4, 5, 6],
                                   [0, 3, 5, 6, 7],
                                   [0, 2, 4, 7], 
                                   [1, 3, 5, 6], 
                                   [1, 2, 4],
                                   [0, 1, 2, 4],
                                   [0, 2, 3] ]

Listes_graphe_1 = [[1, 8], [0, 2, 3, 4, 7, 8], [1, 3, 4, 6], [1, 2, 5, 6],
            [1, 2, 5, 6, 8], [3, 4, 8], [2, 3, 4, 8], [1, 8], [0, 1, 4, 5, 6, 7]]

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


# Petite fonction auxiliaire
# c est un entier désignant une couleur
# voisins est une liste de voisins
# C
# Cette fonction indique par un booléen si l'un de ces voisins possède
# la couleur c
def est_deja_prise(c, liste_de_sommets, Couleur) :
    ''' Indique par un booléen si un des sommets de la liste  présente
    la couleur c. La liste couleurs indique la couleur de chacun des 
    sommets du graphe. Équivaut à recoder le test << in >> '''
    for j in liste_de_sommets :
        if Couleur[j] == c :
            return True
    return False
    
        
# Les couleurs sont les entiers 0, 1, 2, 3, ....
def coloration_glouton(L) :
    n = len(L)
    coloration = n * [None] # les couleurs ne sont pas définies pour l'instant
    for i in range(n) : # on parcourt les noeuds dans l'ordre naïf
        voisins = L[i]
        c = 0 # on commence pour chaque sommet par la première couleur
        while est_deja_prise(c, voisins, coloration) :
            c += 1 
        coloration[i] = c
    return coloration
        

print(coloration_glouton(Listes_graphe_1))
print(coloration_glouton(Listes_graphe_2))
print(coloration_glouton(Listes_graphe_produits_chimiques))
print(coloration_glouton(Listes_graphe_exams))
    

############   ALGO DE WELSH-POWELL #########################
# C'est un glouton car on ne revient pas en arrière.
# Mais un glouton amélioré par le choix de traiter les sommets
# par degrés décroissants.

def degre(i, L) :
    ''' Renvoie le degré du sommet i dans le graphe de listes d'adjacence L'''
    return len(L[i])
    
def second_element(liste) : # petite fonction utile pour un tri plus loin
    return liste[1]


#  Inutile  : on a déjà la fonction est_deja_prise qui joue presque le même rôle
#def est_autorisee(couleur, noeud, L, Coloration) :
#    ''' Indique si la couleur << couleur >> est autorisée pour le noeud
#    << noeud >> compte-tenu de ses voisins déjà colorié dans la liste Coloration '''
#    voisins = L[noeud]
#    for j in voisins :
#        if Coloration[j] == couleur :
#            return False
#    return True
#



def welsh_powell(L) :
    n = len(L)
    Coloration = n * [None] # Au départ les couleurs sont indéterminées
    liste_sommets_degres = []  # sera du type [ (0, deg0), (1, deg1), etc ], puis triée !
    for i in range(n) :
        deg = degre(i, L)
        liste_sommets_degres.append((i, deg)) 
    #print('sommets et degres', liste_sommets_degres)
    liste_sommets_degres.sort(key = second_element, reverse = True) # tri selon le second élément (ici degré)
    #print('sommets et degres', liste_sommets_degres)
    couleur = 0 # On commence par la première couleur.
    compteur = 0 # nombre de sommets coloriés
    while compteur < n :
        for a in liste_sommets_degres :
            sommet = a[0]
            voisins = L[sommet]
            if Coloration[sommet] == None and not est_deja_prise(couleur, voisins, Coloration) :
                Coloration[sommet] = couleur
                compteur += 1
        couleur += 1 # On passe à la couleur suivante.
    return Coloration
            
print(welsh_powell(Listes_graphe_1))
print(welsh_powell(Listes_graphe_2))
print(welsh_powell(Listes_graphe_produits_chimiques))
print(welsh_powell(Listes_graphe_exams))