import numpy
import scipy
import matplotlib
from pylab import *
from math import * 
import random
import matplotlib.patches as mpatches

############ question 1)

###### a) 

# Ces matrices comportent exclusivement des 0 et des 1, avec des 0 sur la diagonale et sont symétriques, car les arètes {i,j} et [j,i} sont identiques.

###### b)

# Le terme (A^k)_{ij} est la somme de tous les produits a_{i, i_1}a_{i_1,i_2}\cdots a_{i_{k-2},i_{k-1}} a_{i_{k-1} j} de tous les produits possibles sur k termes. Il y a autant de chemins possibles allant de i vers j que de possibilités d'effectuer de tels produits a_{i, i_1}a_{i_1,i_2}\cdots a_{i_{k-2},i_{k-1}} a_{i_{k-1} j} ne comportant que des 1. Les indices i=j portant sur la sommation correspondent à une stagnation sur le sommet i avant éventuellement de transiter cers un autre sommet.

##### c)

# Si G est connexe, pour tout i entre 1 et j, il existe au moins un chemin de longueur inférieure ou égale à n reliant i à j (transitant dans le pire des cas par tous les sommets et sinon stagnant parfois sur certains sommets (en utilisant les coefficients diagonaux égaux à 1) : tous les coefficients de A^n sont strictement positifs.

# Si tous les coefficients de A^n sont strictement positifs, pour tous sommets i et j, on peut transiter de i vers j en un chemin de longueur inférieure ou égale à n. Tous les sommets sont reliables les uns aux autres.

############ question 2)

##### a)

def Mat_Graph(matrice) :
    n=list(matrice.shape)[0]    # nombre de lignes, on aurait pu faire len(matrice)
    figure()
    SommetsX=[cos(2*pi*k/n) for k in range(n)]
    SommetsY=[sin(2*pi*k/n) for k in range(n)]
    plot(SommetsX,SommetsY,"ro")
    axis([-1.2,1.2,-1.2,1.2])
    for i in range(n) :
        for j in range(i+1,n) :
            if matrice[i,j]==1 :
                plot([SommetsX[i],SommetsX[j]],[SommetsY[i],SommetsY[j]],"b-")
    show()


##### b)

def CreationMat_Adj(n) :
    A=ones((n,n))  # initialisation à la matrice ne comportant que des 1
    for i in range(n) :
        for j in range(i+1,n) :
            Coeff=randint(2)
            A[i,j],A[j,i]=Coeff,Coeff   # remplissage symétrique
    return A
    
#print(CreationMat_Adj(8))

#Mat_Graph(CreationMat_Adj(8))

##### c) 


# méthode 1) : on voit immédiatement si le graphe est connexe

# méthode 2) : on implémente une procédure pour calculer A^n, puis tester s'il y a des coefficients nuls das A^n

def Test_Coeff_Nul(matrice) : #test = True si matrice n'a aucun coefficient nul et False sinon
    Test=True   
    i,j=0,0
    n=len(matrice)  # nombre de lignes
    for i in range(n) :
        for j in range(n) :
            if matrice[i,j]==0 :
                Test=False
                break
        if Test==False :
            break
    return Test

#A=array([[1,20,2],[10,1,3],[2,2,3]])
#print(Test_Coeff_Nul(A))

def Puissance(matrice,exposant) :   # calcule matrice à l'exposant exposant
    A=matrice
    for i in range(1,exposant) :
        A=dot(matrice,A)
    return A

#n=5
#A= CreationMat_Adj(n)
#print("La matrice est : ")
#print(A)
#print("Le graphe associé est :")
#Mat_Graph(A)
#print("La matrice A^n vaut :")
#B=Puissance(A,n)
#print(B)
#print("Cette matrice a-t-elle uniquement des coefficients non nuls ?")
#print("Réponse ", Test_Coeff_Nul(B))


############ question 3)

##### a)

# Le degré de i est le nombre de sommets adjacents à i. Il s'agit exactement du nombre de 1 figurant dans la i-ème ligne de la matrice A, en ayant soin d'enlever le coefficient diagonal (utile seulement pour obtenir des chemins stagnant au sommet i à un certain moment).

# Réponse : (Nombre de 1 dans la même ligne que le sommet i) - 1

def Calcul_Deg(matrice,i) :
    return len([matrice[i,j] for j in range(n) if matrice[i,j]==1])-1
    
#n=10
#A= CreationMat_Adj(n)
#Mat_Graph(A)
#print(Calcul_Deg(A,6))

##### b)

def Ordonne_Deg(matrice) :
    Liste_Deg=[Calcul_Deg(matrice,i) for i in range(n)]
    Liste_Temp=[[i,Liste_Deg[i]] for i in range(n)] # l'utilisation d'un dictionnaire poserait pb car en enlevant une occurrence de clé, on pourrait enlever plusieurs entrées du dictionnaire, ce qui ne se produit pas dans une liste
    Liste_Deg.sort(reverse=True)    # ordonne les degrés en décroissant
    Liste_Infos=[]
    for i in range(n) :
        Deg=Liste_Deg[i]
        p=0 # fait office de compteur 
        for j in range(n-p) :   # n-p=len(Liste_Temp)
            if Liste_Temp[j][1]==Deg : # détection du sommet de degré Deg
                Liste_Infos.append(Liste_Temp[j])
                Liste_Temp.remove(Liste_Temp[j])  # on gère une file d'attente...
                p=p+1
                break
    return Liste_Infos

#n=6
#A= CreationMat_Adj(n)
#Mat_Graph(A)
#print("")
#print(Ordonne_Deg(A))


############ question 4)

##### a)

def Color_WP(matrice) :
    Sommets_Ord=[S[0] for S in Ordonne_Deg(matrice)]
    Liste_Sommets_Couleurs=[]
    Couleur=0
    while Sommets_Ord!=[] : # tant que la fille d'attente est non vide
        Sommet_Etudie=Sommets_Ord[0]
        Liste_Sommets_Couleurs.append([Sommet_Etudie,Couleur])
        Sommets_Ord.remove(Sommet_Etudie)   # on retire de la file d'attente
        Liste_Temp=[]   # prépare les éléments à enlever dans Sommets_Ord, sans y toucher pour l'instant
        for S in Sommets_Ord :
            Test=True
            for T in [U[0] for U in Liste_Sommets_Couleurs if U[1]==Couleur] :   #on ne teste que les sommets avec la dernière couleur
                if matrice[S,T]==1 :    # on a une adjacence : on laisse tombre le sommet S
                    Test=False
                    break
            if Test :   # test réussi : on peut incorporer S avec la couleur Couleur
                Liste_Sommets_Couleurs.append([S,Couleur])
                Liste_Temp.append(S) # liste des sommets coloriés avec la dernière couleur sauf le premier sommet ainsi colorié car il s'agit du Sommet_Etudie
        for S in Liste_Temp :
            Sommets_Ord.remove(S)   # on enlève les éléments de la file d'attente pour permettre dans la boucle for S in Sommets_Ord : de visiter tous les termes
        Couleur=Couleur+1   # on passe à la couleur suivante
    ## on remet à jour la procédure graphique 
    Codage_Couleurs=["#FF99CC","#9999FF","#FFFF33","#CCFF33","#66FFFF","cyan","orange","gold","purple"]
    n=list(matrice.shape)[0]    # nombre de lignes, on aurait pu faire len(matrice)
    figure()
    SommetsX=[cos(2*pi*k/n) for k in range(n)]
    SommetsY=[sin(2*pi*k/n) for k in range(n)]
    ax = subplot(111, aspect=1)
    for S in Liste_Sommets_Couleurs :
        c = mpatches.Circle((SommetsX[S[0]],SommetsY[S[0]]), 0.1, fc=Codage_Couleurs[S[1]], lw=1)  # fc = fillcolor; lw=linewidth
        ax.add_patch(c)
        axis([-1.2,1.2,-1.2,1.2])
    for i in range(n) :
        for j in range(i+1,n) :
            if matrice[i,j]==1 :
                plot([SommetsX[i],SommetsX[j]],[SommetsY[i],SommetsY[j]],"k-")  # tracé des arètes
    show()
    ##
    print("")   # passage à la ligne
    print("Le graphe est coloriable en ", Liste_Sommets_Couleurs[-1][1]+1, " couleurs.")

##### b)

#n=8
#A=eye(8,8,1)
#A[0,3]=1
#A[0,7]=1
#A[1,6]=1
#A[2,5]=1
#A[4,7]=1
#A=A+A.transpose()
#A=A+eye(8,8)
#print(A)
#Mat_Graph(A)
#Color_WP(A)

n=10
A= CreationMat_Adj(n)
#A=eye(n,n)
#print(A)
#Color_WP(A) 


############ question 5)

# On tranpose habituellement le problème de coloriage de carte en un problème de coloriage de graphe (dual) de la façon suivante :
    # chaque régions de la carte constitue un sommet
    # deux régions ayant une frtontière commune correspondront à deux sommets adjacents
# Les régions deviennent alors des sommets et les frontières des arètes.


############ question 6)


##### a)

# Il s'agit d'une matrice de taille 11*11 à 121 coefficients. Le plus simple est déjà de prendre une feuille de papier, puis d'écrire cette matrice.

def Matrice_Carte() :
    A=zeros((11,11))    # on remplit de 0
    A[0,1]=1    # on construit la matrice au-dessus de la diagonale
    A[0,4]=1
    A[0,9]=1
    A[1,5]=1
    A[1,7]=1
    A[2,3]=1
    A[2,4]=1
    A[3,5]=1
    A[4,5]=1
    A[5,6]=1
    A[5,8:]=1
    A[6,7]=1
    A[7,8:]=1
    A=A+A.transpose()
    A=A+eye(11,11)
    return A

#print(Matrice_Carte())


##### b)

#n=11
#Mat_Graph(Matrice_Carte())
#Color_WP(Matrice_Carte())

##### c) 

# On a ici un résultat optimal de coloriage. Bien évidemment, en modifiant la carte, on peut avoir une configuration en quatre couleurs de façon optimale.


############ question 7)

#Voici une carte comportant quatre régions qui se touchent toutes les unes aux autres.

from tkinter import *

carte=Tk()

titre=Label(carte,text="Une carte coloriée en quatre couleurs")
titre.pack()
can = Canvas(carte, width =700, height =400, bg ='white')
can.pack()
can.create_rectangle(50,50,650,350,fill="#FFFF22")
can.create_rectangle(150,100,350,200,fill="#FF37FF")
can.create_rectangle(350,100,550,200,fill="#82FF04")
can.create_rectangle(250,200,450,300,fill="#2492FF")
bouton_quitter = Button(carte, text="Quitter", command=carte.quit)
bouton_quitter.pack()
#carte.mainloop()
carte.destroy()

# Voici la matrice associée à cette carte :

#n=4
#Carte_4couleurs=ones((4,4))
#print(Carte_4couleurs)
#Mat_Graph(Carte_4couleurs)
#Color_WP(Carte_4couleurs)

# L'algorithme semble assez performant, optimal pour l'instant sur les exemples choixis...