#coloration de graphes
#trois graphes : ceux du sujet, et les régions de France
Gex =  [	[1, 3, 4, 6, 7],	[0, 2, 3],	[1, 3],	[0, 1, 2, 4],	[0, 3, 5, 6, 7],
	[4, 6, 7],	[0, 4, 5, 7],	[0, 4, 5, 6]]		

France = LA = [ 	[1, 4],	[0, 2, 4, 5, 12],	[1, 3, 12],	[2, 6, 12],	[0, 1, 5, 7],	[1, 4, 6, 7, 8, 12],	[3, 5, 8, 12],
	[4, 5, 8, 9],	[5, 6, 7, 9, 10],	[7, 8, 10],	[8, 9],	[ ],	[1, 2, 3, 5, 6]]	

FranceBis = LA = [ 	[1, 4],	[0, 2, 4, 5, 12],	[1, 3],	[2, 6, 12],	[0, 1, 5, 7],	[1, 4, 6, 7, 8, 12],	[3, 5, 8, 12],
	[4, 5, 8, 9],	[5, 6, 7, 9, 10],	[7, 8, 10],	[8, 9],	[ ],	[1, 2, 5, 6]]	#la carte de France vue par Rayane et Widad, pour vérifier

Gex2 = [[1,2],[0,2,3],[0,1,3],[1,2,4],[3]]
AlphaFrance = [8, 6, 0, 5, 11, 3, 2, 12, 1, 7, 9, 4, 10] #ordre alphabétique pour la France

CG = [-1]*len(Gex)
CG2 = [-1]*len(Gex)
CF = [-1]*len(France)




def coloration_valide(LA, C) : #list of list of int, list of int -> boolean
    for i in range(len(LA)) :
        for j in LA[i] : #on ne regarde que ses voisins
            
            if C[i] == C[j] :
                return False #un voisin de la même couleur que i
    return True

def colore_sommet(C, s, LA) : #spécifications
    #on détermine la liste des couleurs des voisins de s déjà colorés
    coul_vois = [ ]
    for j in LA[s] :
        if C[j] != -1 :
            coul_vois.append(C[j])
    #coul_vois est maintenant déterminée et on recherche la
    #plus petite couleur, notée num_coul, absente de coul_vois
    num_coul = 0 #on va commncer par tester la couleur 0
    while num_coul in coul_vois : #tant qu'il s'agit d'une couleur prise
        num_coul += 1 #couleur suivante à tester

    #la valeur num_coul trouvée devient la couleur du sommet s :
    C[s] = num_coul

def colorer1(LA) :
    n = len(LA)
    C = [-1]*n
    for i in range(n) :
        colore_sommet(C, i, LA)
        mise_a_jour(C)
    return(C)


def colorer2(ordre, LA) :
    n = len(LA)
    C = [-1]*n
    for i in ordre :
        colore_sommet(C, i, LA)
        mise_a_jour(C)
    return(C)

def ranger(LA) :
    R = [[] for k in LA]
    for i in range(len(LA)) :
        R[len(LA[i])].append(i)
    return R


def trier_sommets(LA) :
    R = ranger(LA)
    T = []
    for i in range(len(R)) :
        T.extend(R[-i-1])
    return T

def colorer3(LA) :
    return colorer2(trier_sommets(LA), LA)

def combi(L, k) :
	if k == 0  :
		return [[]]
	if k > len(L) :
		return []
	Ck, Ckm = combi(L[:-1],k), combi(L[:-1],k-1)
	Ck.extend([liste+[L[-1]] for liste in Ckm])
	return Ck

def est_clique(LA, K) :
    for i in range(len(K)) :
        for j in range(i) :
            if not(K[j] in LA[K[i]]) :
                return False
    return True

def cherche_clique(LA) :
    n = len(LA)
    S = [k for k in range(n)]
    i = n
    test = True
    la_clique = []
    while test :
        for clique in combi(S, i) :
            if est_clique(LA, clique) :
                test = False
                la_clique.append(clique)
        i = i-1
    return i, la_clique

def deg_satur(LA, s, C) :
    coul_vois = [ ]
    for v in LA[s] :
        cou = C[v]
        if cou != -1 and not(cou in coul_vois) :
            coul_vois.append(cou)
    return len(coul_vois)

def liste_satur(LA, C) :
    record = 0
    Lrec = [ ]
    for s in range(len(LA)) :
        if C[s] == -1 :
            deg = deg_satur(LA, s, C)
            if deg == record :
                Lrec.append(s)
            if deg > record :
                record = deg
                Lrec = [s]
    return Lrec


def colorer4(LA) :
    n = len(LA)
    C = [-1 for s in range(n)]
    D = [len(LA[s]) for s in range(n)]
    while (-1 in C) :
        Ls = liste_satur(LA, C)
        dmax = max([D[s] for s in Ls])
        for s in Ls :
            if D[s] == dmax :
                winner = s
        colore_sommet(C, winner, LA)
        mise_a_jour(C)
    return C


#=============================================================================
#======================= utilitaire pour theorie des graphes =================
#=============================================================================


#constantes diverses 
largeur = 700
hauteur = 450
Nb, Echx, Echy = 30, 20, 20
NbVilles, NbRoutes = 0, 0
Palette = ["Red", "Green", "Yellow", "purple1", "Orange", "Magenta", "Brown", "LightBlue"]


#modules a importer
from tkinter import * #comment echapper a ca
from time import sleep
from random import *
Fen = Tk() #fenetre generale
#canevas de visalisation du graphe
Can = Canvas(Fen, width=largeur, height=hauteur, bg="bisque2")
Can.grid(row=0,column=0)
#canevas de visualisation de la matrice d'adjacence
Matrix = Canvas(Fen, width=(Nb+1)*Echx, height=hauteur, bg="Grey91")
Matrix.grid(row=0,column=1)
Matrix.create_text(15,hauteur-30,anchor=W,text="Pour creer une route, cliquez sur sa case sur le tableau ci-dessus.")
Matrix.create_text(15,hauteur-20,anchor=W,text="Pour effacer une route, choisissez aussi sa case, mais utilisez clic droit.")
Matrix.create_text(15,hauteur-10,anchor=W,text="Pour déplacer une ville, cliquez dessus.")

#listes diverses
Villes, Routes, Tab, M = [], [], [], []

 
def VilleNouvelle() :
    #pour chaque creation de ville, on agrandit la matrice d'adjacence et on l'affiche sur Matrix
    global NbVilles
    NbVilles +=1
    Matrix.create_rectangle(2,NbVilles*Echy+2,Echx+2,(NbVilles+1)*Echy+2)
    for k in range(NbVilles) :
        Matrix.create_rectangle((NbVilles)*Echx+2,k*Echy+2,(NbVilles+1)*Echx+2,(k+1)*Echy+2)
    Matrix.create_rectangle((NbVilles)*Echx+2,(k+1)*Echy+2,(NbVilles+1)*Echx+2,(k+2)*Echy+2,fill="DarkGrey")    
    Matrix.create_text((0.5+NbVilles)*Echx+2,Echy/2+2,text=chr(NbVilles+64))    
    Matrix.create_text(Echx/2+2,(0.5+NbVilles)*Echy+2,text=chr(NbVilles+64))
    for ligne in Tab :
        ligne.append(None)
    Tab.append([None]*NbVilles)
    for ligne in M :
        ligne.append(0)
    M.append([0]*NbVilles)
    for ligne in Routes :
        ligne.append(None)
    Routes.append([None]*NbVilles)


#classes diverses d'objets    
class ville :
    #une ville est un sommet du graphe
    #avec abscisse et ordonnee
    #plus un rayon et une couleur (par defaut) pour la visualisation par l'objet dessin
    def __init__(self, x=22, y=22, rayon=20, distance=0,couleur = "LightBlue") :
        global NbVilles
        self.x, self.y = x, y #coordonnees initiales
        self.rayon = rayon
        self.couleur = couleur
        self.index = NbVilles
        self.distance = distance
        VilleNouvelle()
        self.dessin = Can.create_oval(self.x-self.rayon, self.y-self.rayon, self.x+self.rayon, self.y+self.rayon, fill="White")
        self.info  = Can.create_text(self.x, self.y, text=chr(self.index+65), font = "Garamond 20 bold", fill="Black")
        Can.update()
        
    def actualise_couleur(self, couleur) :
        self.couleur = Palette[couleur]
        Can.itemconfig(self.dessin, fill = Palette[couleur])
        
class route :
    #une route est une arete (orientee), qui relie donc deux villes : depart et arrivee
    #plus une couleur et une information supplementaire eventuelle
    def __init__(self, depart, arrivee, epaisseur=2, couleur = "Black",valeur=1):
        self.depart = depart
        self.arrivee = arrivee
        self.epaisseur = epaisseur
        self.valeur = valeur
        self.couleur = couleur
        self.dessin = Can.create_line(depart.x,depart.y,arrivee.x,arrivee.y,width=self.epaisseur,fill=self.couleur)
        Can.update()

def CreerVille() :
    Villes.append(ville())
    Message.configure(text="Une nouvelle ville est visible en haut, vous pouvez la deplacer avec la souris.")
    
    

dx = largeur//len(Palette)
for k in range(len(Palette)) :
    Can.create_line(k*dx, hauteur, (k+1)*dx, hauteur, width = 5, fill = Palette[k])
Can.update()
    
CreeVille = Button(Fen, text="Creation d'une nouvelle ville", command = CreerVille)
CreeVille.grid(column = 0,row = 1)
Message = Label(Fen, text = "Utilitaire de creation de graphes.")
Message.grid(column = 0,row = 2)


#utilitaires du canevas de visualisation du graphe
def MouseDown(event) :
    #quand on clique sur une ville
    global ExisteVille, LaVille, SesRoutesD, SesRoutesA
    x, y = event.x, event.y
    ExisteVille = False
    for i in range(NbVilles) :
        v = Villes[i]
        if abs(v.x-x)<v.rayon and abs(v.y-y)<v.rayon :
            LaVille=v
            ExisteVille = True
            Index=i
    if ExisteVille : #on n'a pas tape dans le vide
        Can.itemconfig(LaVille.dessin, fill="Yellow")
        Can.lift(LaVille.dessin)
        Can.lift(LaVille.info)
       
        SesRoutesD, SesRoutesA = [], []
        for j in range(NbVilles) :
            if Index>j and M[Index][j] != 0 :
                SesRoutesD.append(Routes[Index][j])
                Can.itemconfig(Routes[Index][j].dessin,fill="Orange")
            if Index<j and M[j][Index] !=0 :
                SesRoutesA.append(Routes[j][Index])
                Can.itemconfig(Routes[j][Index].dessin,fill="Orange")
        
        
 
def MouseMove(event) :
    #quand on deplace une ville
    xm, ym = event.x, event.y
    PeutBouger = xm < largeur and ym < hauteur and xm > 0 and ym > 0
    if ExisteVille and PeutBouger :
        dx, dy = xm-LaVille.x, ym-LaVille.y
        Can.move(LaVille.dessin,dx,dy)
        Can.move(LaVille.info,dx,dy)
        Can.lift(LaVille.dessin)
        Can.lift(LaVille.info)
        LaVille.x, LaVille.y = xm, ym
        for r in SesRoutesD :
            Can.coords(r.dessin,xm,ym,r.arrivee.x,r.arrivee.y)
            r.x, r.y = xm, ym
        for r in SesRoutesA :
            Can.coords(r.dessin,r.depart.x,r.depart.y,xm,ym)
            r.x, r.y = xm, ym

def MouseUp(event) :
    #remise en couleur normale quand on relache
    Can.itemconfig(LaVille.dessin, fill=LaVille.couleur)
    for r in SesRoutesD :
        Can.itemconfig(r.dessin, fill = r.couleur)
    for r in SesRoutesA :
        Can.itemconfig(r.dessin, fill = r.couleur)
    Message.configure(text="")
    
        
#associaition des actions de souris aux procedures
Can.bind("<Button-1>", MouseDown)
Can.bind("<Button1-Motion>", MouseMove)
Can.bind("<Button1-ButtonRelease>", MouseUp)


#creation des routes
def ChoisisRoute(event) :
    x, y = event.x, event.y
    i = (x-2)//Echx-1 #recuperation des index
    j = (y-2)//Echy-1
    i, j = max(i,j), min(i,j) #symetrisation
    if j < i < NbVilles : #verification de la coherence
        if M[i][j]==0 : #cas de la creation d'une route
            M[i][j]+=1#aretes non orientees
            M[j][i]+=1#tableau symétrique
            Routes[i][j]=route(depart=Villes[i],arrivee=Villes[j])
            Tab[i][j]=Matrix.create_text((i+1.5)*Echx+2,(j+1.5)*Echy+2,text="1")
            Tab[j][i]=Matrix.create_text((j+1.5)*Echx+2,(i+1.5)*Echy+2,text="1")
        else : #cas du renforcement d'une route
            M[i][j]+=1
            M[j][i]+=1
            Matrix.itemconfig(Tab[i][j],text=str(M[i][j]))
            Matrix.itemconfig(Tab[j][i],text=str(M[i][j]))
            Routes[i][j].valeur+=1
            
            
def DetruisRoute(event) :
    x, y = event.x, event.y
    i = (x-2)//Echx-1 #recuperation des index
    j = (y-2)//Echy-1
    if j<i<NbVilles : #verification de la coherence
        if M[i][j]<2 : #cas de la destruction d'une route
            M[i][j]=0
            M[j][i]=0
            Can.delete(Routes[i][j].dessin)
            Can.delete(Routes[i][j].info)
            Routes[i][j]=None
            Matrix.itemconfig(Tab[i][j],text="")
            Matrix.itemconfig(Tab[j][i],text="")
        else : #cas de l'allegement d'une route
            M[i][j]-=1
            M[j][i]-=1
            Matrix.itemconfig(Tab[i][j],text=str(M[i][j]))
            Matrix.itemconfig(Tab[j][i],text=str(M[i][j]))
            Routes[i][j].valeur-=1
            
            
            

Matrix.bind("<Button-1>", ChoisisRoute)
Matrix.bind("<Button-3>", DetruisRoute)


def convert_adja(M) :
    LA = []
    for k in range(len(M)) :
        V = []
        for i in range(len(M)) :
            if M[i][k] :
                V.append(i)
        LA.append(V)
    return LA


def mise_a_jour(C) :
    for k in range(NbVilles) :
        Villes[k].actualise_couleur(C[k])
    Can.update()
    print(C)
    sleep(1)


def colore1() :
    mise_a_jour([-1]*NbVilles)
    colorer1(convert_adja(M))

def colore2() :
    mise_a_jour([-1]*NbVilles)
    L = list(range(NbVilles))
    shuffle(L)
    colorer2(L,convert_adja(M))

def colore3() :
    mise_a_jour([-1]*NbVilles)
    colorer3(convert_adja(M))

def colore4() :
    mise_a_jour([-1]*NbVilles)
    colorer4(convert_adja(M))

BoutonColore1 = Button(Fen,text="Colorisation 1, ordre alphabetique",command = colore1)
BoutonColore1.grid(row=1,column=1)
BoutonColore2 = Button(Fen,text="Colorisation 2, ordre aléatoire",command = colore2)
BoutonColore2.grid(row=2,column=1)
BoutonColore3 = Button(Fen,text="Colorisation 3, degré décroissant",command = colore3)
BoutonColore3.grid(row=3,column=1)
BoutonColore4 = Button(Fen,text="Colorisation 4, D-satur",command = colore4)
BoutonColore4.grid(row=4,column=1)
    
Fen.mainloop()
