Implémentation et parcours de graphe en OcamL

Le graphe sera définie comme suit en camL

type graphe  = (int * int list) list;;

On a simplifié en supposant que les sommets étaient représentés par des entiers, mais il est possible d'utiliser une définition plus générale.

Pour créer un graphe, il suffit par exemple de faire :

let gtest =[(1,[2;4]); (2,[1;3]); (3,[]); (4,[])];;

Afin de simplifier le code du parcours, nous allons utiliser une fonction permettant de déterminer la liste des voisins d'un sommet. Nous avons déjà précisé précédemment la manière dont on pouvait s'y prendre pour réaliser cela.

let rec getVoisins g sommet = 
  match g with
  [] -> failwith "Accès à un sommet non existant"
 |(s, voisins)::reste -> if s = sommet then 
                               voisins
                        else  
                               getVoisins reste sommet;;

Nous allons définir une fonction permettant de savoir si un élément est dans une liste. Pour cela, nous utiliserons la fonction mem du module List. Cette fonction servira notamment à déterminer si un élément a déjà été visité ou non.

let isinListe liste element= List.mem element liste;;

Nous allons écrire à présent la fonction principale de parcours (qui est écrite de manière générale) qui dépend d'une fonction d'ajout : fAjout. Pour faire le lien avec la partie précédente, cette fonction est la fonction ensembleUnion. La différence par rapport à l'algorithme est que l'on passe en argument une fonction fTraitement qui réalise un traitement sur un sommet.

(* Le parcours *)
 (* 
    g correspond au graphe,
    aetevisite est la liste des sommets visité
    avisiter sont les sommets à visiter
    fAjout la fonction
    fTraitement la fonction qui traite le sommet
 *)
let rec parcours g aetevisite avisiter fAjout fTraitement =
   match avisiter with 
     [] -> ()
     |sommetCourant::reste ->  
            if (isinListe aetevisite sommetCourant) then 
	         parcours g aetevisite reste fAjout fTraitement                 
            else
             begin
              fTraitement sommetCourant;
 
              let voisins = getVoisins g sommetCourant 
              in
 
              let resteavisiter = fAjout reste voisins 
              in
 
              let cequiaetevisite = sommetCourant::aetevisite 
              in
 
                 parcours g cequiaetevisite resteavisiter fAjout fTraitement
             end
   ;;

Comme nous l'avons vu dans la partie précédente, le parcours en largeur se fait à l'aide d'une file. Cela nous incite ainsi à utiliser comme fonction fAjout une fonction enfilant les éléments à la fin de la liste. Le code est le suivant :

let enfiler file listelement=
  file@listelement;;

À présent, nous pouvons simplement écrire la fonction de parcours en largeur.

let parcoursLargeur g sommet fTraitement =
  parcours g [] [sommet] enfiler fTraitement;;

De la même manière que précédemment, comme la fonction fAjout est implémentée par une pile, nous allons créer une fonction ajoutant une liste d'élément en début de liste.

let empiler pile listelement=
  listelement@pile;;

Il ne nous reste plus que la fonction principale.

let parcoursProfondeur g sommet fTraitement= 
 parcours g [] [sommet]  empiler fTraitement;;