Exercice 1 : OCamlgraph
OCamlgraph est une librairie d'algorithmes de graphes. Son principe est de proposer des foncteurs, qui prennent une interface représentant des graphes et produisent un module définissant un algorithme. On se propose d'écrire un mini OCamlgraph.
Proposez une interface pour les graphes orientés.
Proposez une interface pour un module contenant l'algorithme de parcours en profondeur. L'algorithme doit retourner la liste des sommets parcourus, dans l'ordre de leur découverte.
Écrivez un foncteur des graphes orientés vers les algorithmes de parcours en profondeur.
Tous les parcours suivent le même algorithme, mais avec une gestion différente des arcs en attente de traitement (la frontière). Comment utiliser cette idée pour écrire le programme de parcours une fois pour toutes, et ensuite pouvoir en déduire les divers algorithmes : parcours en largeur ou profondeur, algorithme de Dijkstra, etc.
