%%  Datei:  tiefensuche.pl
%%
%%  Programmierkurs Prolog (Sommersemester 2002),
%%  Material fuer Uebungsblatt 5, Aufgabe 5.3
%%
%%  Problemloesen durch Suche:
%%
%%        Tiefensuche mit Zyklenerkennung in Graphen
%%        ------------------------------------------
%%
%%  (Beispiel von den Folien vom Programmierkurs Prolog im 
%%  Sommersemster 1998 von Thorsten)
%%
%%  Zugrunde liegenden Repraesentation des Suchraums als
%%  Graph, bei dem Problemzustaende die Knoten und zulaessige
%%  Zustandsuebergaenge die Kanten darstellen:
%%
%%    start(Knoten)    Praedikat, das festlegt, welche
%%                       Knoten gültige Startknoten sind.
%%    kante(Q,Z)       Praedikat, das festlegt, ob es eine
%%                       direkte Kante von Q zu Z gibt.
%%    ziel(Knoten)     Praedikat, das festlegt, welche
%%                       Knoten gueltige Zielknoten sind.
%%
%%  Beispielgraph:
%%    start(a). start(g).
%%    kante(a,b). kante(a,c). kante(a,d).
%%    kante(b,d). kante(b,e). kante(b,i).
%%    ...
%%    ziel(h). ziel(i). ziel(j). ziel(m).

start(a). start(g).                                            % Startknoten
kante(a,b). kante(a,c). kante(a,d). kante(a,h). kante(a,j).    % Kanten
kante(b,d). kante(b,e). kante(b,i).
kante(c,d). kante(c,f). kante(c,g).
kante(e,j). kante(g,f). kante(i,f). kante(k,g). kante(k,m).
ziel(h). ziel(i). ziel(j). ziel(m).                            % Zielknoten


%%  Hilfspraedikate:

% not(X) :-                            % Nur mit Vorsicht zu benutzen!
%     (                                % In SWI-Prolog bereits vorhanden!
%      call(X) -> fail
%      ;
%      true
%     ).
%
% nonmember(Element,Liste) :-          % 'Element' und 'Liste' sollten keine Variablen
%     not(member(Element,Liste)).      % sein, sondern unbedingt instanziiert!

nonmember(_,[]):- !.
nonmember(Element,[Element|_]):- fail,!.
nonmember(Element,[Kopf|RestListe]):-
    Element \== Kopf, 
    nonmember(Element,RestListe),
    !.

% member(Element,[Element|_]):- !.     % in SWI-Prolog bereits vorhanden!
% member(Element,[Kopf|RestListe]):-
%     Element \== Kopf, 
%     member(Kopf,RestListe).


%%  Gegeben:  nachfolger/2.
%%  'nachfolger(K,N)' ist wahr, wenn 'N' ein Nachfolger von Knoten 'K' ist.

%%  Funktioniert nicht:
%
% nachfolger(Knoten,Nachfolger):-kante(Knoten,Nachfolger).

%%  Funktioniert:

nachfolger(Knoten,NachfolgerListe):-
    findall(Nachfolger,kante(Knoten,Nachfolger),NachfolgerListe).


%%  Algorithmus fuer Tiefensuche mit Zyklenerkennung:

tiefensuche(Ziel) :-
    start(Start),
    tiefensuche([Start],[],Ziel),
    ziel(Ziel).

tiefensuche([X|_],_,X).

tiefensuche([Y|Offen],Geschl,X) :-
    nonmember(Y,Geschl),
    nachfolger(Y,Nachf),
    append(Nachf,Offen,OffenNeu),
    tiefensuche(OffenNeu,[Y|Geschl],X).

tiefensuche([Y|Offen],Geschl,X) :-
    member(Y,Geschl),	
    tiefensuche(Offen,Geschl,X).


%%  Beispielaufruf:  tiefensuche(Z).
%%      Z = j ;
%%      Z = i ;
%%      Z = h ;
%%      Z = j ;
%%      No