Tri Topologique (Algorithme de Kahn)

Le but de cet exercice est d'implémenter l'algorithme de Kahn pour obtenir le tri topologique d'un graphe orienté acyclique (DAG). Le graphe est représenté par un tableau de listes d'entiers (int list array), où l'indice correspond au sommet, et la liste contient ses successeurs (voisins sortants).

1. 1

   Indice

   Parcourez chaque nœud du graphe et itérez sur ses voisins pour incrémenter leurs degrés dans le tableau des degrés.
   Calculer les degrés entrants : Écrire une fonction calculer_degres_entrants : int list array -> int array qui prend un graphe et renvoie un tableau contenant le nombre d'arêtes pointant vers chaque sommet (degré entrant). Par exemple let g = [|[1; 2]; [3]; [3]; []|] in calculer_degres_entrants g renvoie [|0; 1; 1; 2|].
2. 2

   Indice

   Parcourez le tableau des degrés à l'envers (de la fin vers le début) et ajoutez les indices valant 0 dans une liste pour les avoir dans l'ordre croissant.
   Trouver les sources : Écrire une fonction trouver_sources : int array -> int list qui prend le tableau des degrés entrants et renvoie la liste des sommets ayant un degré entrant de 0 (triée par ordre croissant). Par exemple let deg = [|0; 1; 1; 2|] in trouver_sources deg renvoie [0].
3. 3

   Indice

   Décrémentez le degré de chaque voisin, et si ce degré tombe exactement à zéro, ajoutez ce voisin à la liste des nouvelles sources.
   Mettre à jour les degrés : Écrire une fonction mettre_a_jour_degres : int list array -> int array -> int -> int list qui prend le graphe, le tableau des degrés entrants et un sommet u. La fonction doit décrémenter le degré de tous les voisins de u dans le tableau, et renvoyer la liste des voisins dont le degré vient de devenir exactement 0. Par exemple, si d = [|0; 1; 1; 2|], l'appel mettre_a_jour_degres g d 0 renvoie [1; 2] et modifie d en [|0; 0; 0; 2|].
4. 4

   Indice

   Utilisez le filtrage de motif (pattern matching) sur la liste des sources. Si elle est vide, renvoyez l'accumulateur renversé.
   Traiter les sources : Écrire une fonction récursive traiter_sources : int list array -> int array -> int list -> int list -> int list qui prend le graphe, le tableau des degrés, la liste des sources actuelles, et un accumulateur. À chaque étape, elle extrait une source, met à jour les degrés, ajoute les nouvelles sources trouvées à la liste des sources à traiter, et ajoute le sommet traité à l'accumulateur. Quand il n'y a plus de sources, elle renvoie l'accumulateur renversé. Par exemple traiter_sources g [|0; 0; 0; 2|] [1; 2] [0] renvoie [0; 1; 2; 3].
5. 5

   Indice

   Enchaînez les fonctions précédentes. Si la longueur de la liste finale n'est pas égale au nombre de sommets, alors le graphe contient un cycle (déclenchez une erreur).
   Trier topologiquement : Écrire une fonction trier_topologiquement : int list array -> int list qui orchestre les fonctions précédentes. Si la liste finale ne contient pas tous les sommets du graphe, levez une exception avec failwith "Cycle detecte". Par exemple trier_topologiquement g renvoie [0; 1; 2; 3].