kante(i,j).
kante(j,a).
kante(i,a).
kante(a,b). kante(a,c). kante(b,d). kante(c,e).
kante(d,a). %%
kante(d,e).
start(i). ziel(X) :- member(X,[e]).

graph1([k(i,j),k(j,a),k(a,b),k(a,c)]).

:- prolog_flag(redefine_warnings, _Old, off).
hanoi :- consult('/Documents/Kurse/STUPS/Prolog/L11_Hanoi.pl').
bauer :- consult('/Documents/Kurse/STUPS/Prolog/L11_bauerziege.pl').
acht :- consult('/Documents/Kurse/STUPS/Prolog/L11_8puzzle.pl').
rom :- consult('/Documents/Kurse/STUPS/Prolog/L11_roumania.pl').

/* Tiefensuche: einfache Version */

dfs1 :- start(S), dfs1(S).
dfs1(S) :- ziel(S).
dfs1(S) :- kante(S,S2), dfs1(S2).
		


/* Tiefensuche: mit Pfad */
		
dfs(Pfad) :- start(S), dfs(S,Pfad).
dfs(S,[S]) :- ziel(S).
dfs(S,[S|Rest]) :- kante(S,S2), dfs(S2,Rest).

/* Tiefensuche: mit History Pfad */
		
dfs2(Pfad) :- start(S), dfs2(S,Pfad,[S]).
dfs2(S,[S],_) :- ziel(S).
dfs2(S,[S|Rest],Hist) :-
   kante(S,S2),  \+ member(S2,Hist),
   dfs2(S2,Rest,[S2|Hist]).


/* Version mit globaler Liste der gesehenen Zustände */
% statistics(runtime,_),dfs3(P),statistics(runtime,[_,T]).
:- dynamic visited/1.
dfs3(Pfad) :- start(S), retractall(visited(_)),
   dfs3(S,Pfad).
dfs3(S,[S]) :- ziel(S).
dfs3(S,[S|Rest]) :- \+ visited(S),
  assert(visited(S)),
  kante(S,S2), dfs3(S2,Rest).

btassert(X) :- assert(X).
btassert(X) :- retract(X),fail.

/* Version mit AVL Baum */

:- use_module(library(avl)).
dfsa(Pfad) :- start(S), empty_avl(E),dfsa(S,Pfad,E).
dfsa(S,[S],_) :- ziel(S).
dfsa(S,[S|Rest],Hist) :- \+ avl_fetch(S,Hist),
   kante(S,S2), avl_store(S,Hist,true,NewHist),
   dfsa(S2,Rest,NewHist).

/* Iterative Deepening */
list([]). list([_|T]) :- list(T).
idfs(Pfad) :- list(Pfad), dfs(Pfad).


/* Breiten Suche */

:- use_module(library(queues)).

bfs(P) :- empty_queue(EQ), retractall(visited(_)),
          start(S),
          queue_append(EQ,[S],Q), bfs1(Q,P).

bfs1(Q,Path) :- append_queue([H],RestQ,Q),
   portray_queue(Q),nl, %
   (  ziel(H), path(H,Path)
    ; findall(Y,kante2(H,Y),Succs),
      queue_append(RestQ,Succs,Q2),
      bfs1(Q2,Path)
   ).
:- dynamic bfs_visited/2.
kante2(H,Y) :- kante(H,Y), \+ bfs_visited(Y,_),
  assert(bfs_visited(Y,H)).

path(X,[X]) :- start(X).
path(X,[X|T]) :- bfs_visited(X,Y), path(Y,T).
/* ---------------------------------------------------------------------- */   


print_graph_header(Type) :-
    print('digraph '), print(Type), print(' {'),nl,
   % print('graph [orientation=landscape, page="8.5, 11",ratio=fill,size="7.5,10"];'),nl,
    print(' graph [page="8.5, 11",ratio=fill,size="7.5,10"];'),
    nl.

print_graph_footer :-  print('}'),nl.   
    
    
    
print_graph :- retractall(state(_,_,_,_)),retract(nr(_)), assert(nr(1)),
   print_graph_header('Lecture11Suche'),fail.
print_graph :- start(S), get_state_nr(S,box,blue,_),nl,fail.
print_graph :- ziel(S), get_state_nr(S,diamond,orange,_),
 % print(' [shape=diamond,style=filled,color=orange];'),nl,
 fail.
print_graph :-   kante(X,Y),
   printstate(X), print(' -> '), printstate(Y), print(';'),nl,
   fail.
print_graph :- state(X,Nr,S,C),
 print_node_decl(Nr,S,C,X),fail.
print_graph :- 
  print_graph_footer.

:- dynamic state/4, nr/1.
nr(1).
printstate(X) :- get_state_nr(X,ellipse,green,Nr), print(Nr).

get_state_nr(X,S,C,Nr) :-  state(X,Nr,_,_),!.
get_state_nr(X,S,C,Nr) :-  retract(nr(Nr)), N1 is Nr+1,
      assert(state(X,Nr,S,C)), assert(nr(N1)).

printq(X) :- print(''''),print(X),print('''').

print_node_decl(X,S,C,L) :- print(X), print(' [shape='),print(S),
 print(',color='),print(C),print(',label="'),print(L),print('"];'),nl.
print_node_decl(X,L) :- print(X), print('[label="'),print(L),pritn('"]'),nl.


:- use_module(library(system3)).
pg :- tell('~/Desktop/tmp2/L11_Suche_graph.dot'), print_graph, told,
      system('open ~/Desktop/tmp2/L11_Suche_graph.dot').