IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Implémentation et parcours de graphe en OcamL


précédentsommairesuivant

V. Programmation et sources

V-A. Type graphe

Le graphe sera définie comme suit en camL

Définition du type
Sélectionnez
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 :

Création
Sélectionnez
let gtest =[(1,[2;4]); (2,[1;3]); (3,[]); (4,[])];;

V-B. Détermination des voisins d'un sommet

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.

Récuperation des voisins
Sélectionnez
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;;

V-C. Appartenance à une liste

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.

Appartenance à une liste
Sélectionnez
let isinListe liste element= List.mem element liste;;

V-D. Programme de parcours

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.

Parcours
Sélectionnez
(* 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
   ;;

V-E. Parcours en largeur

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 :

Fonction d'ajout de sommet
Sélectionnez
let enfiler file listelement=
  file@listelement;;

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

Parcours en largeur
Sélectionnez
let parcoursLargeur g sommet fTraitement =
  parcours g [] [sommet] enfiler fTraitement;;

V-F. Parcours en profondeur

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.

Fonction d'ajout de sommet
Sélectionnez
let empiler pile listelement=
  listelement@pile;;

Il ne nous reste plus que la fonction principale.

Parcours en profondeur
Sélectionnez
let parcoursProfondeur g sommet fTraitement= 
 parcours g [] [sommet]  empiler fTraitement;;

VI. Sources complètes

Sources, version OcamL
Sélectionnez
type graphe  = (int * int list) list;;
 
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;;
 
 
let isinListe liste element= List.mem element liste;;
 
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
   ;;
 
 
let enfiler file listelement=
  file@listelement;;
let empiler pile listelement=
  listelement@pile;;
 
let parcoursProfondeur g sommet fTraitement= 
 parcours g [] [sommet]  empiler fTraitement;;  
 
let parcoursLargeur g sommet fTraitement =
  parcours g [] [sommet] enfiler fTraitement;;

Le code source est également disponible pour camL Light : source caml Lightsource caml Light

VII. Exemple d'application

Par exemple, l'exécution sur le graphe 3 donne le résultat suivant.

Exemple
Sélectionnez
let graphe3  = [(0, [1;2;3]); (1, [4;5]); (2, []); (3, []); (4, []);(5, [6]); (6,[])];;
 
parcoursLargeur graphe3 0 print_int;;
#0123456- : unit = ()
 
parcoursProfondeur graphe3 0 print_int;;
#0145623- : unit = ()

précédentsommairesuivant

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Florent HUMBERT. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.