#### TP n°12: Introduction aux graphes ####
#################


### PREMIÈRE APPROCHE AVEC LA LIBRAIRIE NETWORKX ###

## Question 1 : Création d'un graphe
import networkx
g=networkx.Graph()
S=['A','B','C','D','E','F','G','H','I','J','K','L']
for i in range(len(S)):
    g.add_node(S[i])
g.add_edge('A','B')
g.add_edge('A','C')
g.add_edge('B','D')
g.add_edge('A','F')
g.add_edge('B','C')
g.add_edge('D','F')
g.add_edge('E','G')
g.add_edge('F','G')
g.add_edge('F','H')
g.add_edge('I','J')
g.add_edge('J','K')
g.add_edge('K','I')
g


## Question 2 : Informations sur les nœuds
print(g.degree('A'))
print(list(g.neighbors('A')))
print(list(g.nodes()))
## Question 3 : Parcours en largeur
def parcours_en_largeur(g:networkx.Graph,initial:str) -> list:
    noeuds_visites=[initial]
    parcours=[]
    file=[initial]
    while len(file)>0:
        n=file.pop(0)
        parcours.append(n)
        voisins=list(g.neighbors(n))
        for i in range(len(voisins)):
            v=voisins[i]
            if not(v in noeuds_visites):
                noeuds_visites.append(v)
                file.append(v)
    return parcours
    
print(parcours_en_largeur(g,'A'))
print(parcours_en_largeur(g,'H'))
print(parcours_en_largeur(g,'I'))
## Question 4 : Parcours en profondeur
def parcours_en_profondeur(g:networkx.Graph,noeuds_visites:list,initial:str)->list:
    noeuds_visites.append(initial)
    voisins=list(g.neighbors(initial))
    for i in range(len(voisins)):
         if not(voisins[i] in noeuds_visites):
            parcours_en_profondeur(g,noeuds_visites,voisins[i])
    return noeuds_visites
    
print(parcours_en_profondeur(g,[],'A'))
print(parcours_en_profondeur(g,[],'H'))
print(parcours_en_profondeur(g,[],'I'))
## Question 5 : Composantes connexes
def composantes_connexes(g:networkx.Graph)->list:
    noeuds_non_visites=list(g.nodes)
    cc=[]
    while len(noeuds_non_visites)>0:
        parcours=parcours_en_largeur(g,noeuds_non_visites[0])
        for i in range(len(parcours)):
            noeuds_non_visites.remove(parcours[i])
        cc.append(parcours)
    return cc
print(composantes_connexes(g))
### COLORIAGE D'UN GRAPHE ###




## Question 6 
def coloriage(A:list,ordre:list)->list:
    C=[None]*len(A) # création d'une nouvelle liste de couleurs ne contenant que des None
    for i in range(len(ordre)):
        lc=LISTE_COULEURS.copy() # clonage de la liste des couleurs
        # récupérer le ième noeud de la liste ordre
        noeud=ordre[i]
        # liste des voisins du ième noeud dans l'ordre
        voisins=A[noeud]
        # suppression des couleurs déjà utilisées
        for j in range(len(voisins)):
            v=voisins[j]
            if C[v] in lc:
                lc.remove(C[v])
        # affectation de la première couleur disponible au noeud considéré
        C[noeud]=lc[0]
    return C
O=[i for i in range(len(S))] # ordre 0,1,2,...
C1=coloriage(A,O)
print(C1)
dessine_carte(S,XY,C1)
## Question 7 
import numpy
D=[len(A[i]) for i in range(len(A))]
O=numpy.argsort(D)[::-1]
C2=coloriage(A,O)
dessine_carte(S,XY,C2)
### ALGORITHME DE DIJKSTRA ###

## Question 8 
A=[[1,3,4],[0,5],[5],[0,4],[0,3,5],[1,2,4]]
P=[[4,2,5],[4,3],[3],[2,5],[5,5,1],[3,3,2]]
## Question 9 
## Question 10 
def selectionne_noeud(distances:list,a_ignorer:list)->int:
    min=float("inf")
    nmin=-1
    for i in range(len(distances)):
        if a_ignorer[i]==False and distances[i]<min:
            min=distances[i]
            nmin=i
    return nmin
def dijkstra(A,P,debut,fin):
    l=len(A)
    distances=[float("inf")]*l
    distances[debut]=0
    origines=[-1]*l
    traites=[False]*l
    n=debut
    while n!=fin:
        n=selectionne_noeud(distances,traites)
        voisins=A[n]
        poids=P[n]
        for j in range(len(voisins)):
            v=voisins[j]
            if distances[n]+poids[j]<distances[v]:
                distances[v]=distances[n]+poids[j]
                origines[v]=n
        traites[n]=True
    n=fin
    chemin=[fin]
    while n!=debut:
        n2=origines[n]
        chemin=[n2]+chemin
        n=n2
    return (chemin,distances[fin])
print(dijkstra(A,P,0,2))
### GPS FRANÇAIS ###


## Question 11 
def trajet(g,debut,fin):
    noeuds=list(g.nodes())
    l=len(noeuds)
    distances=dict()
    origines=dict()
    traites=dict()
    routes=dict()
    for i in range(l):
        distances[noeuds[i]]=float("inf")
        origines[noeuds[i]]=-1
        traites[noeuds[i]]=False
        routes[noeuds[i]]=""
    distances[debut]=0
    n=debut
    while n!=fin:
        dmin=float("inf")
        for i in range(l):
            ni=noeuds[i]
            if traites[ni]==False and distances[ni]<dmin:
                n=ni
                dmin=distances[ni]
        arretes=list(g.edges(n,data=True))
        for j in range(len(arretes)):
            v=arretes[j][1]
            poids=arretes[j][2]["weight"]
            if distances[n]+poids<distances[v]:
                distances[v]=distances[n]+poids
                origines[v]=n
                routes[v]=arretes[j][2]["road"]
        traites[n]=True
    n=fin
    chemin=[fin]
    while n!=debut:
        n2=origines[n]
        chemin=[n2+" ( prendre "+routes[n]+")"]+chemin
        n=n2
    return (chemin,distances[fin])
print(trajet(g,"Saint-Étienne","Marseille"))
## Question 12 
def trajet2(g,debut,fin,a_eviter):
    noeuds=list(g.nodes())
    l=len(noeuds)
    distances=dict()
    origines=dict()
    traites=dict()
    routes=dict()
    for i in range(l):
        distances[noeuds[i]]=float("inf")
        origines[noeuds[i]]=-1
        traites[noeuds[i]]=False
        routes[noeuds[i]]=""
    for i in range(len(a_eviter)):
        traites[a_eviter[i]]=True
    distances[debut]=0
    n=debut
    while n!=fin:
        dmin=float("inf")
        for i in range(l):
            ni=noeuds[i]
            if traites[ni]==False and distances[ni]<dmin:
                n=ni
                dmin=distances[ni]
        arretes=list(g.edges(n,data=True))
        for j in range(len(arretes)):
            v=arretes[j][1]
            poids=arretes[j][2]["weight"]
            if distances[n]+poids<distances[v]:
                distances[v]=distances[n]+poids
                origines[v]=n
                routes[v]=arretes[j][2]["road"]
        traites[n]=True
    n=fin
    chemin=[fin]
    while n!=debut:
        n2=origines[n]
        chemin=[n2+" ( prendre "+routes[n]+")"]+chemin
        n=n2
    return (chemin,distances[fin])
print(trajet(g,"Saint-Étienne","Lille"))
print(trajet2(g,"Saint-Étienne","Lille",["Paris"]))
### LE JEU DU MORPION ###


## Question 13 
print(len(E))
nA=0
for i in range(len(A)):
    nA=nA+len(A[i])
print(nA)
## Question 14 

affiche_etat(3006)
print("Voisins:")
voisins=A[3006]
for i in range(len(voisins)):
    affiche_etat(voisins[i])
## Question 15 : Parcours du graphe
def parcours_morpion(initial:int)->list:
    noeuds_visites=[initial]
    parcours=[]
    file=[initial]
    while len(file)>0:
        n=file.pop(0)
        parcours.append(n)
        voisins=A[n]
        for i in range(len(voisins)):
            v=voisins[i]
            if not(v in noeuds_visites):
                noeuds_visites.append(v)
                file.append(v)
    return parcours
p=parcours_morpion(3006)
print(p)
for i in range(len(p)):
    affiche_etat(p[i])
## Question 16 
def est_termine(n:int)->bool:
    e=E[n]
    for i in range(9):
        if e[i]=="0":
            return False
    return True
for i in range(len(p)):
    print("État "+str(p[i]))
    if est_termine(p[i]): 
        print("Terminé")
    if est_gagne(p[i]):
        print("Gagné")
    if est_perdu(p[i]):
        print("Perdu")
## Question 17 
def victoire_impossible(n:int)->bool:
    p=parcours_morpion(n)
    for i in range(len(p)):
        if est_gagne(p[i]):
            return False
    return True
for i in range(len(E)):
    if E[i].count("0")==4 and victoire_impossible(i):
        print(i)
        affiche_etat(i)
## Question 18 
def nul_oblige(n:int)->bool:
    p=parcours_morpion(n)
    for i in range(len(p)):
        if est_gagne(p[i]) or est_perdu(p[i]):
            return False
    return True
for i in range(len(E)):
    if E[i].count("0")==3 and nul_oblige(i):
        print(i)
        affiche_etat(i)