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

Pierre Caboche

Cet article présente quelques algorithmes sur les graphes, ainsi que leur implémentation en Prolog.

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

- Auteur : Pierre Caboche

- Parution : 17 novembre 2006

- Licence : 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.

Sommaire

- À propos de cet article

- A qui s'adresse cet article?

- Pourquoi cet article?

- 1. Graphes: généralités

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

- 1-2. Applications

- 1-3. Représentation choisie

- 1-3-1. Les arcs

- 1-3-2. Les noeuds

- 1-3-3. Prédicats

- 2. Parcours d'un graphe

- 3. Algorithmes de recherche du plus court chemin

- 3-1. Algorithme de Dijkstra

- 3-1-1. Principe de l'algorithme

- 3-1-2. Implémentation

- 3-1-3. Discussion sur l'implémentation

- 3-2. Algorithme de Bellman-Ford

- 3-2-1. Différences avec Dijsktra

- 3-2-2. Implémentation

- 4. Arbre de recouvrement minimal

- 4-1. Définition

- 4-2. Algorithme de Jarnik (ou Prim)

- 4-2-1. Principe de l'algorithme

- 4-2-2. Implémentation

- 4-3. Algorithme de Kruskal

- 4-3-1. Principe de l'algorithme

- 4-3-2. Implémentation

- 4-4. Différences entre Jarnik et Kruskal

- Conclusion

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

3 - Algorithmes de recherche du plus court chemin

3-1 - Algorithme de Dijkstra

L'algorithme de Dijkstra permet de trouver le chemin le plus court entre 2 points d'un graphe. Pour ce faire, il détermine le chemin le plus court entre 1 point et n'importe quel autre point du graphe, jusqu'à ce qu'il tombe sur le point d'arrivée recherché (ou s'il n'y a plus de point à visiter, c'est qu'il n'existe pas de chemin entre les points considérés).

L'algorithme de Dijkstra ne s'applique que dans le cas d'un graphe orienté et pour lequel le poids des arcs est non négatif (ce qui constitue la majorité des graphes).

Il est très facile de transformer un graphe non-orienté en graphe orienté. Par contre, si le poids des arcs est susceptible d'être négatif, il faut utiliser l'algorithme de Bellman-Ford.

3-1-1 - Principe de l'algorithme

Voici le fonctionnement de l'algorithme de Dijkstra :

1. On construit un graphe G' uniquement composé du point de départ

2. On fait la liste des arcs tels que

- le point de départ appartienne à G'

- le point d'arrivée appartienne à G (notre graphe de départ) mais pas à G'

3. Si la liste est vide, on s'arrête (il n'existe pas de chemin entre les points considérés)

4. A partir de cette liste, on sélectionne l'arc qui minimise la distance entre le point de départ et le nouveau point

5. On ajoute cet arc à G', ce qui ajoute également un point au graphe. On garde une trace du chemin ayant permis d'arriver au nouveau point

6. Si le point fraîchement ajouté correspond au point d'arrivée recherché, on s'arrête et on retourne le chemin complet (qui est le chemin le plus court).

7. Sinon, retour en 2.

3-1-2 - Implémentation

Pour l'implémentation, nous représenterons chaque chemin de la manière suivante: DistanceChemin-CheminInversé.

Les chemins étant inversés, pour un chemin donné, on a directement accès au dernier point visité, celui-ci se trouvant en tête de liste. Ce n'est qu'à la fin de l'algorithme qu'on inversera la liste pour avoir le chemin dans le bon sens.

Par ailleurs, le fait de mettre sous cette forme (la distance en premier) permet de trier les chemins par ordre croissant grâce au prédicat keysort/2, ce qui facilite l'implémentation.

Voici une implémentation de l'algorithme de Dijkstra en Prolog :

Algorithme de Dijkstra

%
% Dijkstra
%   + Start        : Point de départ
%   + Finish       : Point de d'arrivée
%   - ShortestPath : Chemin le plus court
%   - Len          : Longueur de ce chemin
%

dijkstra(Start, Finish, ShortestPath, Len) :-
dijk( [0-[Start]], Finish, RShort, Len),
reverse(RShort, ShortestPath).

% Le dernier point visité est le point d'arrivée => on s'arrête
%

dijk( [ Len-[Fin|RPath] |_], Fin, [Fin|RPath], Len) :- !.

dijk( Visited, Fin, RShortestPath, Len) :-
% Recherche du meilleur candidat (prochain point à ajouter au graphe)
%   et appel récursif au prédicat
%

bestCandidate(Visited, BestCandidate),
dijk( [BestCandidate|Visited], Fin, RShortestPath, Len).

%
% Recherche toutes les arrêtes pour lesquelles on a:
%  - un point dans le graphe (visité)
%  - un point hors du graphe (candidat)
%
% Retourne le point qui minimise la distance par rapport à l'origine
%

bestCandidate(Paths, BestCandidate) :-

% à partir d'un point P1 :

findall(
NP            % on fait la liste de tous les points P2 tels que:
,
(
member( Len-[P1|Path], Paths),  % - le point P2 a déjà été visité
arc(P1,P2,Dist),                % - il existe un arc allant de P1 à P2, de distance Dist
\+isVisited(Paths, P2),         % - le point P2 n'a pas encore été visité

NLen is Len+Dist,               % on calcule la distance entre l'origine et le point P2

NP=NLen-[P2,P1|Path]            % on met chaque élément de la liste sous la forme: Distance-Chemin
% pour pouvoir les trier avec le prédicat keysort/2
)
,
Candidates
),

% On trie et on retient le chemin le plus court
minimum(Candidates, BestCandidate).

%
% Sort le meilleur candidat parmi une liste de candidats
% (= celui de chemin le moins long)
%

minimum(Candidates, BestCandidate) :-
keysort(Candidates, [BestCandidate|_]).

%
% Teste si un point P a déjà été visité
%

isVisited(Paths, P) :-
memberchk(_-[P|_], Paths).

3-1-3 - Discussion sur l'implémentation

L'implémentation en Prolog est finalement relativement simple.

L'étape 2, par exemple, est effectuée par le prédicat bestCandidate/2. Dans ce prédicat, pour chaque point déjà visité, on fait la liste des arcs partant de ce point et amenant à un point qui ne fait pas déjà partie du graphe en construction. Grâce au keysort, on détermine le chemin le plus court depuis l'origine (étape 4). Si aucun chemin n'est trouvé, le prédicat échoue (étape 3). Ceci se traduit en Prolog par:

% à partir d'un point P1 :

findall(
NP            % on fait la liste de tous les points P2 tels que:
,
(
member( Len-[P1|Path], Paths),  % - le point P2 a déjà été visité
arc(P1,P2,Dist),                % - il existe un arc allant de P1 à P2, de distance Dist
\+isVisited(Paths, P2),         % - le point P2 n'a pas encore été visité

NLen is Len+Dist,               % on calcule la distance entre l'origine et le point P2

NP=NLen-[P2,P1|Path]            % on met chaque élément de la liste sous la forme: Distance-Chemin
% pour pouvoir les trier avec le prédicat keysort/2
)
,
Candidates
),

% On trie et on retient le chemin le plus court
keysort(Candidates, [BestCandidate|_]).

Il s'agit là de l'étape la plus difficile de l'algorithme, et pourtant c'est une traduction mot pour mot de la description de l'algorithme...

Optimisations possibles :

Pour faciliter l'implémentation, concernant la recherche du chemin le plus court, nous avons implémenté le prédicat minimum/2 de la manière suivante :

minimum(Candidates, BestCandidate) :-
keysort(Candidates, [BestCandidate|_]).

Il s'agit donc d'un tri à la suite duquel on ne garde que le premier élément de la liste (donc le minimum). L'algorithme de tri est de complexité O(n^2), alors que la recherche d'un minimum est de complexité O(n) seulement. L'implémentation n'est donc pas optimale. Cependant, il faut garder à l'esprit que l'algorithme de tri est implémenté à bas niveau en Prolog, rendant le tri plus performant.

Dans le cas précédent, nous nous sommes intéressés aux performances concernant la vitesse. Cette implémentation nécessite l'utilisation de listes, consommatrices de mémoire. Dans le cas de graphes présentant de nombreux arcs, on souhaite économiser la mémoire. Pour ce faire, nous n'allons pas utiliser de listes. A la place, nous allons donner une définition formelle (en programmation logique) du chemin le plus court en 2 points.

La modification a lieu dans le prédicat bestCandidate/2. Dans l'implémentation suivante, nous vous recommandons de prêter une attention particulière aux commentaires, qui décrivent de manière formelle comment on définit la solution:

Optimisation pour la mémoire

bestCandidate(Paths, BestCandidate) :-

% Soient les points P1 et P2
% tels que :

member( Len1-[P1|Path1], Paths),  % - le point P1 a déjà été visité
arc(P1,P2,Dist1),                 % - il existe un arc allant de P1 à P2
\+isVisited(Paths, P2),           % - le point P2 n'a pas encore été visité

NLen1 is Len1 + Dist1,            % NLen1 = Dist(Origine, P2)

% L'arc P1->P2 est tel que :

forall(
% Pour tout arc P3->P4
% tel que :

(
member( Len2-[P3|_], Paths),  % - le point P3 a déjà été visité
arc(P3,P4,Dist2),             % - il existe un arc allant de P3 à P4
\+isVisited(Paths, P4),       % - le point P4 n'a pas encore été visité

NLen2 is Len2 + Dist2         % NLen2 = Dist(Origine, P4)
)
,

% On cherche à obtenir :
% P2 fournit le chemin le plus court depuis l'origine

NLen1 =< NLen2

),

% En cas d'ex-aequo, on ne garde qu'une seule solution
!,

BestCandidate = NLen1-[P2,P1|Path1].

Dans cette implémentation, on compare chaque candidat avec tous les autres candidats et on s'arrête dès que l'on a trouvé le point qui fournit le chemin le plus court. Dans le pire des cas la complexité est donc en O(n^2) (même si en fait la recherche s'interrompt dès qu'un minimum est trouvé). Cependant, cette implémentation n'utilise pas de liste, requiert donc moins de mémoire et conviendra particulièrment bien aux graphes de taille importante.

Cette dernière implémentation illustre la manière dont on programme en Prolog : plutôt que de décrire les différentes étapes de résolution d'un algorithme (le "comment ?" de "comment trouver la solution ?"), on s'attache à décrire de manière formelle ce qu'est une solution (le "quoi ?": "qu'est-ce qu'une solution ?").

Afin de mieux comprendre cette implémentation, nous vous invitons à vous référer au cours portant sur Prolog et l'Algèbre Relationnelle, et plus particulièrement cette partie.

3-2 - Algorithme de Bellman-Ford

3-2-1 - Différences avec Dijsktra

L'algorithme de Dijkstra ne s'applique que dans le cas d'un graphe pour lequel le poids des arcs est non négatif, ce qui constitue la majorité des graphes (cartes routières, réseaux divers...). Pour les graphes dont le poids des arcs peut être négatif, on doit avoir recours à l'algorithme de Bellman-Ford

L'algorithme de Bellman-Ford est moins rapide que l'algorithme de Dijkstra. Aussi, dans la majorité des cas (graphes dont le poids des arcs est non négatif), on utilisera Dijkstra.

3-2-2 - Implémentation

Nous ne proposons pas d'implémentation pour Bellman-Ford car pour l'instant, nous n'avons pas eu de question à ce sujet sur le forum Prolog de developpez...

4 - Arbre de recouvrement minimal

4-1 - Définition

Un arbre de recouvrement est un arbre qui permet de relier les points d'un graphe G de telle sorte que pour tout couples (A, B) de point du graphe G, il existe un chemin permettant de relier A à B.

Un arbre de recouvrement minimal est un arbre de recouvrement dont le poids total (la somme des poids de ses arcs) est minimal (il n'existe pas d'arbre de recouvrement de poids plus faible). Le terme "arbre de recouvrement minimal" est parfois abrégé MST, pour Minimum Spanning Tree.

L'intérêt d'un arbre de recouvrement minimal est le suivant: Imaginons que l'on souhaite relier plusieurs villes entre elles à un réseau quelconque (gaz, électricité, téléphone...). Un graphe représente les liaisons possibles entre chacune de ces villes avec le coût que représente la liaison entre ces villes. La recherche de l'arbre de recouvrement minimal servira à de déterminer le réseau qui permettra de relier toutes les villes entre elles avec un coût minimal.

Pour trouver l'arbre de recouvrement minimal, on dispose de 2 algorithmes: Jarnik et Kruskal.

4-2 - Algorithme de Jarnik (ou Prim)

4-2-1 - Principe de l'algorithme

L'algorithme connu sous le nom d' "algorithme de Prim" (bien qu'en fait découvert par Jarnik 27 ans avant Prim) ressemble beaucoup, dans son principe, à l'algorithme de Dijkstra, même si la finalité est différente (trouver l'arbre de recouvrement minimal, et non le chemin le plus court entre 2 points) :

1. On construit un graphe G' uniquement composé d'un point de départ

2. On fait la liste des arcs tels que

- le point de départ appartienne à G'

- le point d'arrivée appartienne à G (notre graphe de départ) mais pas à G'

3. Si la liste est vide, on s'arrête (on a fini de construire l'arbre de recouvrement minimal)

4. A partir de cette liste, on sélectionne l'arc de poids le plus faible (afin de minimiser le poids du graphe)

5. On ajoute cet arc à G', ce qui ajoute également un point à l'arbre en construction

6. Retour en 2.

4-2-2 - Implémentation

Voici l'implémentation de cet algorithme :

Algorithme de Prim

prim(Depart, ARM) :-
prim1([Depart], [], ARM).

prim1(Visite, Temp, ARM) :-
% On recherche tous les arcs P1->P2 tels que :
% - P1   appartient     à Visite
% - P2 n'appartient pas à Visite

findall(
Poids-(P1,P2)
,
( member(P1, Visite), arc(P1,P2,Poids), \+member(P2, Visite) )
,
Candidates
),

% On évalue les candidats
prim2(Candidates, Visite, Temp, ARM).

prim2([], _, Temp, ARM) :-
% Il n'y a plus de candidat -> on a fini, on retourne l'ARM
!,
reverse(Temp, ARM).

prim2(Candidates, Visite, Temp, ARM) :-

% Recherche du meilleur candidat P2
keysort(Candidates, [_-(P1,P2)|_]),

prim1([P2|Visite], [ P1-P2 | Temp], ARM).

4-3 - Algorithme de Kruskal

4-3-1 - Principe de l'algorithme

L'algorithme de Kruskal fonctionne de la façon suivante :

1. On part d'un graphe vide G'

2. On dresse la liste des arcs de G, triés par poids croissant

3. On parcourt ensuite la liste triée :

- si la liste ne contient plus d'élément, on a terminé et l'algorithme s'arrête

- si les deux points de l'arc ont déjà été visités, on ignore l'arc et on examine les arcs suivants

- sinon, on ajoute l'arc à l'arbre en construction, on ajoute les points de l'arc à la liste des points visités et on on examine les arcs suivants

4-3-2 - Implémentation

Voici l'implémentation de l'algorithme de Kruskal :

Algorithme de Kruskal

kruskal(ARM) :-
findall(
Poids-(P1,P2)
,
arc(P1,P2,Poids)
,
Arcs
),
keysort(Arcs, ArcsTries),
krusk(ArcsTries, [], ARM).

krusk([], _, []) :-
!.

krusk([_-(P1,P2)|Q], Visite, ARM) :-
memberchk(P1, Visite),
memberchk(P2, Visite),
!,
krusk(Q, Visite, ARM).

krusk([_-(P1,P2)|Q], Visite, [P1-P2|ARM]) :-
union([P1,P2], Visite, Visite2),
krusk(Q, Visite2, ARM).

4-4 - Différences entre Jarnik et Kruskal

Voici quelques unes des différences entre les algorithmes de Jarnik et Kruskal :

- Jarnik construit l'arbre de recouvrement minimal (ARM) en commençant par un point quelconque du graphe, alors que Kruskal construit l'ARM à partir des arêtes

- Dans le cas d'un graphe disjoint, Jarnik retournera l'ARM dans lequel appartient le point de départ, alors que Kruskal renverra tous les arbres de recouvrement minimal (constituant ainsi une forêt d'arbres)

Le choix d'un de ces 2 algorithmes découle le plus souvent du choix de la représentation du graphe. La plupart des représentations permettent, pour un point donné, d'accéder à la liste des points voisins mais ne permettent pas de dresser rapidement la liste des arêtes du graphes (c'est le cas, par exemple, avec une liste d'adjacences), pourtant nécessaire à Kruskal. Dans ce cas, on privilégie donc Jarnik.

Dans ce tutoriel, nous avons utilisé une représentation nous permettant d'avoir directement accès aux arêtes du graphe. Nous privilégierons donc l'algorithme de Kruskal pour ses nombreux avantages (algorithme simple à comprendre, simple à mettre en place, code concis, plus rapide car effectuant moins de tris, algorithme applicable sans modification au cas d'un graphe disjoint).

Conclusion

Dans ce cours, nous avons donné une implémentation Prolog de quelques algorithmes courants de la théorie des graphes (Dijkstra, Kruskal...). Concernant l'implémentation, nous avons choisi d'être le plus neutre et le plus général possible.

Les applications de la théorie des graphes sont nombreuses et le prédicat arc/3 est une généralisation de toutes sortes de relations dans différents contextes. Aussi nous invitons nos lecteurs à bien comprendre les algorithmes et les implémentations présentés dans cet article afin de les adapter au mieux en fonction de leurs besoins.