# Les graphes du cours

G1 = {1: [2], 2: [1, 4, 5], 3: [4], 4: [2, 3, 5, 6], 5: [2, 4], 6: [4, 6]}
M1 = [[0, 1, 0, 0, 0, 0],
      [1, 0, 0, 1, 1, 0],
      [0, 0, 0, 1, 0, 0],
      [0, 1, 1, 0, 1, 1],
      [0, 1, 0, 1, 0, 0],
      [0, 0, 0, 1, 0, 1]]

G2 = {1: [3], 2: [4], 3: [5], 4: [], 5: [1]}
M2 = [[0, 0, 1, 0, 0],
      [0, 0, 0, 1, 0],
      [0, 0, 0, 0, 1],
      [0, 0, 0, 0, 0],
      [1, 0, 0, 0, 0]]

G3 = {1: {2: 7, 3: 10}, 2: {1: 7, 3: 6, 4: 5, 5: 3}, 3: {1: 10, 2: 6, 5: 4},
      4: {2: 5}, 5: {2: 3, 3: 4}}
M3 = [[0, 7, 10, 0, 0],
      [7, 0, 6, 5, 3],
      [10, 6, 0, 0, 4],
      [0, 5, 0, 0, 0],
      [0, 3, 4, 0, 0]]


############################## Exercice 1 ##############################

# 1)

{'A': ['B', 'D'], 'B': ['C'], 'C': [], 'D': ['E', 'F'], 'E': ['A'], 'F': ['E'],
 'G': ['E']}

# 2)

[[0, 1, 0, 1, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 1, 0],
 [1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 1, 0, 0]]

# 3)

# En profondeur à partir de A : A - B - C - D - E - F
# En profondeur à partir de G : G - E - A - B - C - D - F
# En largeur à partir de A : A - B - D - C - E - F
# En largeur à partir de G : G - E - A - B - D - C - F


############################## Exercice 2 ##############################


# 2) {1: [3, 5], 2: [4], 3: [1, 2], 4: [1], 5: [4]}

# 3)

def inverse(G):
    G_inv = {}
    for sommet in G:
        L = []
        for s in G:
            if sommet in G[s]:
                L.append(s)
        G_inv[sommet] = L
    return G_inv

# ou avec un dictionnaire par compréhension :

def inverse(G):
    return {sommet: [s for s in G if sommet in G[s]] for sommet in G}


############################## Exercice 3 ##############################

# 1) a)

def est_chemin(G, chemin):
    for i in range(len(chemin)-1):
        if chemin[i+1] not in G[chemin[i]]:
            return False
    return True

# 1) b) Attention au décalage des indices (sommets 1, 2, ... -> lignes 0, 1, ...)

def est_chemin(M, chemin):
    for i in range(len(chemin)-1):
        if M[chemin[i]-1][chemin[i+1]-1] == 0:
            return False
    return True

# 2) a)

def poids(G, chemin):
    p = 0
    for k in range(len(chemin)-1):
        s1, s2 = chemin[k], chemin[k+1]
        if s2 in G[s1]:
            p += G[s1][s2]
        else:
            return -1
    return p

# 3) b)

def poids(M, chemin):
    p = 0
    for k in range(len(chemin)-1):
        s1, s2 = chemin[k], chemin[k+1]
        if M[s1-1][s2-1] != 0:
            p += M[s1-1][s2-1]
        else:
            return -1
    return p


############################## Exercice 4 ##############################

# 1)

def matrice_adjacence(G):
    n = len(G)
    M = []
    for i in range(n):
        ligne = []
        for j in range(n):
            if j+1 in G[i+1]:
                ligne.append(1)
            else:
                ligne.append(0)
        M.append(ligne)
    return M

# ou pour les amateurs de listes par compréhension (int(True)=1, int(False)=0) :

def matrice_adjacence(G):
    return [[int(j+1 in G[i+1]) for j in range(len(G))] for i in range(len(G))]

# 2)

def listes_adjacence(M):
    G = {}
    n = len(M)
    for i in range(n):
        voisins = []
        for j in range(n):
            if M[i][j] == 1:
                voisins.append(j+1)
        G[i+1] = voisins
    return G

# ou :

def listes_adjacence(M):
    return {i+1: [j+1 for j in range(len(M)) if M[i][j] == 1] for i in range(len(M))}


############################## Exercice 5 ##############################

G5 = {1: [2, 5], 2: [1, 5, 6], 3: [4, 8], 4: [3, 8], 5: [1, 2, 6], 6: [2, 5],
      7: [], 8: [3, 4]}

# 1) L'idée est de parcourir le graphe (en largeur ou en profondeur) à partir du
# sommet donné. Les sommets visités forment la composante connexe cherchée.

from collections import deque

def composante_connexe(G, sommet): # avec un parcours en largeur
    visites = {sommet}
    file = deque([sommet])
    while file:
        s = file.popleft()
        for voisin in G[s]:
            if voisin not in visites:
                file.append(voisin)
                visites.add(voisin)
    return list(visites)

def composante_connexe(G, sommet): # avec un parcours en profondeur (itératif)
    visites = set()
    pile = [sommet]
    while pile:
        s = pile.pop()
        if s not in visites:
            visites.add(s)
            for voisin in G[s]:
                if voisin not in visites:
                    pile.append(voisin)
    return list(visites)

# 2) Il suffit de vérifier si la composante connexe d'un sommet quelconque du
# graphe forme le graphe tout entier.

def est_connexe(G):
    sommets = list(G)
    return composante_connexe(G, sommets[0]) == sommets

# 3)

def composantes_connexes(G):
    composantes = []
    visites = set() # sommets dont on a déjà calculé la composante connexe
    for s in G:
        if s not in visites:
            composante = composante_connexe(G, s)
            for t in composante:
                visites.add(t)
            composantes.append(composante)
    return composantes


############################## Exercice 6 ##############################

# 1)

fichier = 'mots.txt'  # à modifier si nécessaire
f = open(fichier)
mots = f.read().split(';')
f.close()

MOTS = [mot for mot in mots if len(mot) == 3]

# 2) La fonction du TP 8, adaptée aux mots de trois lettres :

def voisins(mot):
    L = []
    for m in MOTS:
        nb = 0  # nombre de lettres identiques dans m et mot
        for i in range(3):
            if m[i] == mot[i]:
                nb += 1
        if nb == 2:
            L.append(m)
    return L

# 3)

def creer_graphe():
    G = {}
    for mot in MOTS:
        G[mot] = voisins(mot)
    return G

# ou :

def creer_graphe():
    return {mot: voisins(mot) for mot in MOTS}

# 4) a)

G = creer_graphe()
print(len(G))    # nombre de sommets
nb_total_voisins = sum(len(G[mot]) for mot in G)
print(nb_total_voisins // 2)   # nombre d'arêtes
print(nb_total_voisins / len(G))   # nombre moyen de voisins

# 4) b)

for mot in G:
    if G[mot] == []:
        print(mot)

# 4) c)

composantes = composantes_connexes(G)
print(len(composantes))
print(max(len(comp) for comp in composantes))

# 5) On reprend la fonction vue en cours en remplaçant G[smin][v] par 1 :

from heapq import heappop, heappush

def chemin(depart, arrivee):
    d = {depart: 0}      # dictionaire des distances au sommet de départ
    pred = {}            # dictionaire des prédécesseurs
    visites = set()
    file = [(0, depart)]
    
    # Construction du dictionaire des distances
    while file and arrivee not in visites:
        dmin, smin = heappop(file) # point le plus proche du depart
        if smin not in visites:
            visites.add(smin)
            for v in G[smin]:
                S = dmin + 1
                if v not in d or S < d[v]:
                    d[v] = S
                    pred[v] = smin
                    heappush(file, (S, v))

    # Recherche du plus court chemin
    assert arrivee in visites, "Pas de chemin"
    chem = [arrivee]
    s = arrivee
    while s != depart:
        s = pred[s]
        chem.append(s)
    return chem[::-1]