(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) open Graph (* *Attention* On suppose ici que les sommets sont séparés en pairs et impairs, i.e. tout arc relie deux sommets de parités différentes. Dans le code ci-dessous, on note `x` les sommets pairs et `y` les sommets impairs. *) (* Code tiré de l'excellent ouvrage "Programmation Efficace" de Christoph Dürr et Jill-Jênn Vie *) let maximum_matching (g: graph) : (int * int) list = let n = size g in let m = Array.make n (-1) in (* couplage y -> x *) (* `augment x` tente de construire un chemin augmentant depuis `x` *) let rec augment x visited = let visit y = not visited.(y) && (visited.(y) <- true; (m.(y) = -1 || augment m.(y) visited) && (m.(y) <- x; true)) in List.exists visit (succ g x) in (* on appelle `augment` depuis tous les sommets pairs *) for i = 0 to (n - 1) / 2 do ignore (augment (2 * i) (Array.make n false)) done; (* on renvoie la liste des arcs formant le couplage *) let rec build acc y = if y >= n then acc else build (if m.(y) = - 1 then acc else (m.(y), y) :: acc) (y + 2) in build [] 1