# TP 19 (fichier à compléter) : Graphes
# BCPST1B 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% démarrage (exécuter une fois pour toutes)

# La bibliothèque NetworkX permet de manipuler des graphes, et notamment (pour nous) de les dessiner.
# On les crée à partir de nx.DiGraph() (graphe orienté) ou nx.Graph() (non-orienté) depuis une matrice d'adjacente (qui doit être un tableau numpy) ou un dictionnaire d'adjacence.
# Documentation pour dessiner :
# https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx.html
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# dessine un graphe orienté donné par matrice d'adjacence
def dessiner(M):
    MM = np.array(M)
    G = nx.DiGraph(MM)
    nx.draw_networkx(G, arrows=True, arrowsize=20, node_size=500, node_color="powderblue", font_size=12, linewidths=1, width=1, edgecolors="black")
    plt.box(False)
    plt.show()

#%% exemple partie II.1 : une matrice d'adjacence

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
dessiner(M)

#%% exemple partie II.1 : carte de France

trains = {"Paris": ["Versailles", "Lyon", "Angers", "Besançon", "Clermont"], "Versailles": ["Paris"], "Lyon": ["Paris", "Marseille", "Grenoble", "Besançon"], "Angers": ["Paris"], "Besançon": ["Paris", "Lyon"], "Clermont": ["Paris"], "Marseille": ["Lyon", "Nice"], "Grenoble": ["Lyon"], "Nice": ["Marseille"]}

positions = {"Paris": (0, 0), "Versailles": (-0.12, -0.34), "Lyon": (0.3, -0.4), "Angers": (-0.3, -0.35), "Grenoble": (0.5, -0.63), "Marseille": (0.36, -1.1), "Nice": (0.52, -1.0), "Clermont": (0.03, 0.35), "Besançon": (0.53, -0.25)}

G = nx.DiGraph(trains)
nx.draw_networkx(G, arrows=False, node_size=2000, font_size=8, font_color="blue", font_weight="bold", node_color="pink", linewidths=1, edgecolors="black", pos=positions)
plt.box(False)
plt.show()

# Votre ville n'est pas dans la liste ? Ajoutez-là, avec sa position !

#%% exercice 1.1

def liste_vers_matrice(L):
    n = len(L)
    M = [[0 for _ in range(n)] for _ in range(n)]
    ...
    return M

L = [[0, 1, 2], [0, 2], [3], [1, 2]]
print(liste_vers_matrice(L))

#%% exercice 1.2

def matrice_vers_liste(M):
    n = len(M)
    L = [[] for _ in range(n)]
    ...
    return L

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
print(matrice_vers_liste(M))

#%% exercice 2

def graphe_complet(n):
    M = [[0 for _ in range(n)] for _ in range(n)]
    ...
    return M

M = graphe_complet(5)
dessiner(M)

#%% exercice 3

def graphe_cyclique(n):
    M = [[0 for _ in range(n)] for _ in range(n)]
    ...
    return M

M = graphe_cyclique(6)
dessiner(M)

#%% exercice 4

def graphe_biparti_complet(n, p):
    M = [[0 for _ in range(n+p)] for _ in range(n+p)]
    ...
    return M

M = graphe_biparti_complet(3, 4)
dessiner(M)

#%% exercice 5.1

def degré_sortant(M, x):
    ...

# exemple : celui de la section II.1
M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
for x in range(len(M)):
    print("Sommet", x, "degré sortant", degré_sortant(M, x))

#%% exercice 5.2

def degré_entrant(M, x):
    ...

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
for x in range(len(M)):
    print("Sommet", x, "degré entrant", degré_entrant(M, x))

#%% exercice 5.3

def degré(M, x):
    ...

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
for x in range(len(M)):
    print("Sommet", x, "degré", degré(M, x))

#%% exercice 5.4

def degré_total(M):
    ...

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
print(degré_total(M))

#%% exercice 6

def est_chemin_possible(M, C):
    ...

M = [[1, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 0]]
C = [0, 1, 2, 3, 1, 2]
print(est_chemin_possible(M, C))
D = [0, 1, 2, 0, 1]
print(est_chemin_possible(M, D))

#%% exercice 10

...
