% Base de connaissance d'un graphe avec cycle

arc(a,b,2).
arc(b,a,3).
arc(a,g,6).
arc(b,e,2).
arc(b,c,7).
arc(g,e,1).
arc(g,h,4).
arc(e,f,2).
arc(f,c,3).
arc(f,h,2).
arc(c,d,3).
arc(h,d,2).



%   -----------VERSION 1 (accu + not)----------------
% Pour pouvoir détecter les cycles,
% on rajoute un accumulateur des sommets par lesquels on
% est déjà passé, qu'on initialise à [X]
% Option d'affichage (reverse permet de mettre le chemin
% dans le bon ordre)

chemin(X,Y,S):- ch(X,Y,[X],R),reverse(R,S).

% Quand on termine le chemin, on rajoute juste le dernier
% sommet à l'accumulateur L s'il ne forme pas de cycle
% et on obtient le chemin [Y|L]

ch(X,Y,L,[Y|L]) :-
	arc(X,Y,_),
	not(member(Y,L)).

% Avant de choisir un sommet Z à explorer (successeur de Y),
% On s'assure qu'on ne l'a pas déjà exploré pour
% éviter les cycles.

ch(X,Y,L,R) :-
	arc(X,Z,_),
	not(member(Z,L)),
	ch(Z,Y,[Z|L],R).


%   -----------VERSION 2 (iterative deepening)----------------
chemin_id(X,Y,L):-
	length(L,_N),
	cheminbis(X,Y,L).

cheminbis(X,Y,[X,Y]):-
	arc(X,Y,_).

cheminbis(X,Y,[X|L]):-
	arc(X,Z,_),	
	cheminbis(Z,Y,L).