## Exercice 1 : Représentation des graphes


sommets=[k for k in range(4)]
arcs1=[(0,1),(1,2),(2,3),(3,0)]
arcs2=[(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]
G1=[sommets,arcs1]
G2=[sommets,arcs2]

import networkx as nx
import matplotlib.pyplot as plt

RG1=nx.DiGraph()
RG1.add_nodes_from(G1[0])
RG1.add_edges_from(G1[1])
#nx.draw(RG1,with_labels=True,node_color='cyan')
#plt.show()

RV=nx.Graph()
RV.add_nodes_from(Villes[0])
RV.add_edges_from(Villes[1])
#nx.draw(RV,with_labels=True,node_color='cyan')
#plt.show()

import numpy as np

def matrice_adjacence(G):
    sommets,arcs=G[0],G[1]
    n=len(sommets)
    M=np.zeros((n,n))
    for a in arcs:
        M[a[0],a[1]]=1
    return M

def voisins(G,k):
    voisins=[]
    aretes=G[1]
    for a in aretes:
        if a[0]==k:
            voisins.append(a[1])
        elif a[1]==k:
            voisins.append(a[0])
    return voisins

print(voisins(Villes,'Toulouse'))

## Exercice 2 : Longueur d'un trajet

sommets=[k for k in range(4)]
arcs3=[(0,1,8),(1,2,10),(0,2,5),(2,3,7),(1,3,4),(3,2,2)]
G3=[sommets,arcs3]

# RG3=nx.DiGraph()
# RG3.add_nodes_from(G3[0])
# RG3.add_weighted_edges_from(G3[1])
#
# pos=nx.spring_layout(RG3)
# w = nx.get_edge_attributes(RG3, "weight")
# nx.draw_networkx(RG3,pos,with_labels=True,node_color='cyan')
# nx.draw_networkx_edge_labels(RG3,pos,edge_labels=w)
# plt.show()

RVp=nx.Graph()
RVp.add_nodes_from(Villes_ponderees[0])
RVp.add_weighted_edges_from(Villes_ponderees[1])

pos=nx.spring_layout(RVp)
w = nx.get_edge_attributes(RVp, "weight")
nx.draw_networkx(RVp,pos,with_labels=True,node_color='cyan')
nx.draw_networkx_edge_labels(RVp,pos,edge_labels=w)
plt.show()

def longueur(G,trajet):
    n=len(trajet)
    arcs=G[1]
    n_a=len(arcs)
    l=0
    for k in range(n-1):
        if trajet[k][1]!=trajet[k+1][0]:
            return False
        for a in arcs:
            if trajet[k]==(a[0],a[1]):
                l+=a[2]
    for a in arcs:
        if trajet[n-1]==(a[0],a[1]):
            l+=a[2]
    return l

trajet=[(0,1),(1,3),(3,2)]
print(longueur(G3,trajet))


## Exercice 3 : Parcours en profondeur


def voisins_restants(G,s,parcours):
    R=[]
    for v in voisins(G,s):
        if not(v in parcours):
            R.append(v)
    return R

def parcours_en_profondeur(G,k):
    parcours=[k]
    pile=[k]
    c=k
    R=voisins_restants(G,c,parcours)
    while(c!=k or R!=[]):
        if R!=[]:
            c=R[0]
            parcours.append(c)
            pile=[c]+pile
            R=voisins_restants(G,c,parcours)
        else:
            c=pile.pop(0)
            R=voisins_restants(G,c,parcours)
    return parcours

print(parcours_en_profondeur(Villes,'Toulouse'))

sommets=[k for k in range(12)]
aretes=[(0,1),(1,5),(4,5),(4,8),(8,9),(9,10),(2,6),(6,7),(6,10),(3,7),(7,11)]
labyrinthe=[sommets,aretes]

RL=nx.Graph()
RL.add_nodes_from(labyrinthe[0])
RL.add_edges_from(labyrinthe[1])
# nx.draw(RL,with_labels=True,node_color='cyan')
# plt.show()

def sortir(G,k):
    parcours=[k]
    pile=[k]
    chemin=[k]
    c=k
    R=voisins_restants(G,c,parcours)
    while(c!=sortie):
        if R!=[]:
            c=R[0]
            parcours.append(c)
            pile=[c]+pile
            chemin.append(c)
            R=voisins_restants(G,c,parcours)
        else:
            c=pile.pop(0)
            R=voisins_restants(G,c,parcours)
            if R==[]:
                chemin.pop(-1)
    return chemin

sortie=3
print(sortir(labyrinthe,0))

## Exercice 4 : Parcours en largeur


def parcours_en_largeur(G,k):
    parcours=[k]
    file=voisins_restants(G,k,parcours)
    while(file!=[]):
        c=file.pop(0)
        parcours.append(c)
        file=file+voisins_restants(G,c,parcours+file)
    return parcours

print(parcours_en_largeur(Villes,'Toulouse'))

## Exercice 5 : Coloration d'un graphe

sommets=[k for k in range(7)]
arcs=[(0,1),(0,2),(0,6),(0,4),(0,5),(1,2),(2,3),(2,6),(3,4),(3,6),(4,6),(4,5)]
C=[sommets,arcs]

RC=nx.Graph()
RC.add_nodes_from(C[0])
RC.add_edges_from(C[1])
# nx.draw(RC,with_labels=True,node_color='cyan')
# plt.show()

def degre(G,k):
    aretes=G[1]
    d=0
    for a in aretes:
        if a[0]==k or a[1]==k:
            d+=1
    return d

print(degre(C,0))

def trier(G):
    sommets=G[0]
    n=len(sommets)
    for i in range(n-1,0,-1):
        for j in range(i):
            if degre(G,sommets[j+1])>degre(G,sommets[j]):
                sommets[j],sommets[j+1]=sommets[j+1],sommets[j]
    return sommets

print(trier(C))

def colorer(G):
    T=trier(G)
    WP=[]
    c=0
    while(T!=[]):
        WP.append((T.pop(0),c))
        for k in T:
            b=True
            for v in voisins(G,k):
                if (v,c) in WP:
                    b=False
            if b:
                T.remove(k)
                WP.append((k,c))
        c+=1
    return WP

print(colorer(C))

## Exercice 6 : Algorithme de Dijkstra

def init_dijkstra(G,s0):
    n=len(G[0])
    H=[[s0],[]]
    D=n*[np.inf]
    D[s0]=0
    return(H,D)

def suivant_dijkstra(G,H):
    if len(H[0])==len(G[0]):
        return (-1,-1,np.inf)
    else:
        d=np.inf
        for g in G[0]:
            if not(g in H[0]):
                for h in H[0]:
                    for a in G[1]:
                        if (a[0],a[1])==(g,h) or (a[0],a[1])==(h,g):
                            if a[2]<d:
                                p,s,d=h,g,a[2]
    return (p,s,d)

def maj_dijkstra(G,H,D,p,s,d):
    H2=[H[0]+[s],H[1]]
    D2=D
    D2[s]=D[p]+d
    for k in H[0]:
        for a in G[1]:
            if (a[0],a[1])==(k,s) or (a[0],a[1])==(s,k):
                H2[1].append(a)
                D2[k]=min(D2[k],D2[s]+a[2])
                D2[s]=min(D2[s],D2[k]+a[2])
    return(H2,D2)

def dijkstra(G,s0):
    (H,D)=init_dijkstra(G,s0)
    (p,s,d)=suivant_dijkstra(G,H)
    while s!=-1:
        (H,D)=maj_dijkstra(G,H,D,p,s,d)
        (p,s,d)=suivant_dijkstra(G,H)
    return D

sommets=[k for k in range(4)]
arcs3=[(0,1,8),(1,2,10),(0,2,5),(2,3,2),(1,3,4)]
G3=[sommets,arcs3]

print(dijkstra(G3,0))

## Exercice 7 : Algorithme de Floyd-Warshall


def matrice_adjacence2(G):
    sommets,aretes=G[0],G[1]
    n=len(sommets)
    M=np.zeros((n,n))
    for i in range(n):
        for j in range(n):
            M[i,j]=np.inf
        M[i,i]=0
    for a in aretes:
        M[a[0],a[1]]=a[2]
        M[a[1],a[0]]=a[2]
    return M

def floyd_warshall(G):
    n=len(G[0])
    D=matrice_adjacence2(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i,j]=min(D[i,j],D[i,k]+D[k,j])
    return D

print(floyd_warshall(G3))