Algorithmes sur les graphes en Prolog:
Dijkstra, Prim, Kruskal


précédentsommairesuivant

À propos de cet article

A qui s'adresse cet article?

Cet article s'adresse :

  • en priorité aux programmeurs Prolog qui cherchent une implémentation en Prolog des algorithmes les plus courants sur les graphes
  • aux programmeurs Prolog qui souhaitent en savoir plus sur ce langage et cherchent des exemples de programme
  • à toute personne s'intéressant à la théorie des graphes et cherchant des liens sur le sujet, avec des exemples d'implémentation

Pourquoi cet article?

Cet article a été écrit en réponse à certaines questions posées sur le forum Prolog de developpez.net concernant les implémentations en Prolog de certains algorithmes courants portant sur les graphes (ex: Dijkstra, Kruskal). C'est donc une sorte de FAQ améliorée.

Je n'ai pas la prétention de présenter de manière exhaustive l'ensemble des algorithmes portant sur les graphes et leur implémentation Prolog (ce serait beaucoup trop long !). Cet article ne couvre donc que les algorithmes qui ont été abordés sur le forum de développez.

Si vous cherchez une implémentation pour un algorithme en particulier portant sur les graphes et que celui-ci ne figure pas dans cet article, posez votre question sur le forum Prolog de developpez.net (n'oubliez pas de préciser que vous avez fait des recherches et que vous êtes tombé sur cet article, nous répondons plus volontiers aux personnes ayant fait des recherches avant ;-) ). Nous réfléchirons alors à votre problème et la solution trouvée viendra peut-être enrichir cet article. N'hésitez pas non plus à nous soumettre vos contributions.



1. Graphes: généralités

Cette section est un résumé très rapide de ce qu'est un graphe (ce résumé doit être juste suffisant pour pouvoir aborder les autres sections).

1.1. Qu'est-ce qu'un graphe?

Pour une introduction à la théorie des graphes (définitions, exemples), voir : La théorie des graphes de Romuald Perrot.



1.2. Applications

Les applications sont multiples :

  • réseaux en tous genres (réseaux routier, électrique, gazier, ferroviaire...)
  • diagrammes de dépendance (dépendances entre tâches, paquets linux...)
  • diagrammes d'états (ex: automates)
  • autres

Même l'exécution d'un programme Prolog peut être vue sous la forme d'un graphe !



1.3. Représentation choisie

Il existe de nombreuses manières de représenter un graphe (par exemple, à l'aide de listes d'adjacences), toutes répondant à un besoin différent.

Dans cet article, nous représenterons un graphe par ses arcs, au moyen de prédicats.



1.3.1. Les arcs

Un arc est caractérisé par

  • son point de départ
  • son point d'arrivée
  • son poids

Pour cela, nous définirons donc le prédcat arc/3 :

 
Sélectionnez
arc(b,c,5).
arc(a,b,5).
arc(a,c,8).
arc(c,d,5).
arc(b,e,12).



Les graphes décrits dans ce cours seront donc orientés. Pour représenter un graphe non-orienté, on procédera de la manière suivante :

 
Sélectionnez
% Les arcs non-orientés
arcBi(b,c,5).
arcBi(a,b,5).
arcBi(a,c,8).
...

arc(A,B,P) :- arcBi(A,B,P).
arc(A,B,P) :- arcBi(B,A,P).



1.3.2. Les noeuds

Pour cet article, nous n'aurons besoin de connaître que les arcs du graphe (nous n'aurons pas besoin de la liste des noeuds).

Cependant, à partir des arcs, on peut facilement déduire la liste des noeuds (points) du graphe :

 
Sélectionnez
noeud(N) :-
  noeud_1([], N).


noeud_1(Visite, N) :-
  ( arc(P,_,_) ; arc(_,P,_) ),
  \+memberchk(P, Visite),
  !,
  noeud_2(P, [P|Visite], N).


noeud_2(N, _, N).

noeud_2(_, Visite, N) :-
  noeud_1(Visite, N).



Si on souhaite en plus que les noeuds soient triés selon l'ordre standard du Prolog, on peut procéder ainsi :

 
Sélectionnez
noeudOrd(N) :-
  setof(
    X
  ,
    Y^P ^ ( arc(X,Y,P) ; arc(Y,X,P) )
  ,
    L
  ),

  member(N, L).



1.3.3. Prédicats

Les prédicats décrits dans ce cours accèderont aux données du graphe (les arcs et leur poids) directement en consultant la base de connaissance (par le biais du prédicat arc/3).

Les prédicats définis dans ce cours ne modifieront pas la base de connaissance (pas de création de nouveaux graphes). A la place, ils retourneront leur résultat sous forme de liste (pour Dijkstra: chemin le plus court entre 2 points; pour Prim et Kruskal: liste des arcs appartenant à l'arbre de recouvrement minimal).

On considère donc que la base de connaissance n'est accessible qu'en lecture seule par nos algorithmes.

Il est laissé à la discretion du lecteur de modifier les sources afin de l'adapter à son propre besoin (ex: pouvoir définir plusieurs graphes, pouvoir modifier ces graphes en accédant à la base de connaissance, etc).



2. Parcours d'un graphe

Les différents types de parcours d'un graphe (profondeur, largeur, profondeur bornée, avec heuristique) devront faire l'objet d'un nouvel article, commun avec la recherche de solutions à un problème.




précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2006 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et 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.