À 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 :
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 :
% 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 :
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 :
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.