/* This is the AO* program. It works on the graph */
/* given in the text. To run the program type ao. */
/* The output will go to file f. So please ensure */
/* that you do not own such a file.               */

startnode(n0).
termnode(n7).
termnode(n8).
h(n0,0,unsolved).
h(n1,2,unsolved).
h(n2,4,unsolved).
h(n3,4,unsolved).
h(n4,1,unsolved).
h(n5,1,unsolved).
h(n6,2,unsolved).
h(n7,0,unsolved).
h(n8,0,unsolved).
edge(n0,[n1],1).
edge(n0,[n4,n5],2).
edge(n1,[n2],1).
edge(n1,[n3],1).
edge(n2,[n3],1).
edge(n2,[n4,n5],2).
edge(n3,[n5,n6],2).
edge(n4,[n5],1).
edge(n4,[n8],1).
edge(n5,[n6],1).
edge(n5,[n7,n8],2).
edge(n6,[n7,n8],2).

initgraph(N,E) :- startnode(Sn),
                  h(Sn,C,_),
                  N = [[Sn,C]],
                  E = [].

member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

findall(X,G,_) :- asserta(found(mark)),
                  call(G),
                  asserta(found(X)),
                  fail.
findall(_,_,L) :- collect_found([],M),!,L = M.
collect_found(S,L) :- getnext(X), ! , collect_found([X|S],L).
collect_found(L,L).
getnext(X) :- retract(found(X)), ! , X \== mark.

append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

delete(_,[],[]).
delete(X,[X|L],M) :- !,delete(X,L,M).
delete(X,[Y|L1],[Y|L2]) :- delete(X,L1,L2).

intersection([],X,[]).
intersection([X|R],Y,[X|Z])
  :- member(X,Y),!,
     intersection(R,Y,Z).
intersection([X|R],Y,Z)
  :- intersection(R,Y,Z).


get_all_out_nodes([[[X|N3],m]|T],X,N3).
get_all_out_nodes([H|T],X,N3) :- get_all_out_nodes(T,X,N3).

out_marked_edges([],X) :- fail.
out_marked_edges([[[X|_],m]|T],X).
out_marked_edges([H|T],X) :- out_marked_edges(T,X).

deletefirst([_|L],L).

select(N,E,N1,Node) :- N1 = [X|_],
                       not out_marked_edges(E,X),!,
                       Node = X.
select(N,E,N1,Node) :- N1 = [X|_],
                       deletefirst(N1,N2),
                       get_all_out_nodes(E,X,N3),
                       append(N2,N3,N4),
                       select(N,E,N4,Node).

selectnode(N,E,Node) :- startnode(Sn),
                        N1 = [Sn],
                        select(N,E,N1,Node).

expand(N,E,Node,N1,E1)
  :- findall([Node|X],edge(Node,X,C),L),
     addtograph(L,N,E,N1,E1).

addtograph([],N,E,N,E).
addtograph([H|T],N,E,N1,E1)
  :- H = [_|H1],
     processnodes(H1,N,N2),
     append([[H,u]],E,E2),
     addtograph(T,N2,E2,N1,E1).

processnodes([],N,N).
processnodes([H|T],N,N2)
  :- not member([H,_],N),!,
     h(H,C,_),
     append([[H,C]],N,N3),
     checksolved(H),
     processnodes(T,N3,N2).
processnodes([H|T],N,N2) :- processnodes(T,N,N2).

checksolved(H) :- termnode(H),!,
                 h(H,C,Z),
                 retract(h(H,C,Z)),
                 assert(h(H,C,solved)).
checksolved(H).

revisecosts(N1,E1,Node,N2,E2)
  :- S = [Node],
     revise(S,N1,E1,N2,E2).

revise([],N1,E1,N1,E1).
revise(S,N1,E1,N2,E2)
  :- S2 = S,
     picknode(S2,S,E1,M),
     delete(M,S,S1),
     updatecostsandmarks(M,N1,E1,N3,E3,Minedge,Upd),
     checkandmarksolved(Minedge,Sol),
     updateS(M,S1,E3,Upd,Sol,NewS),
     revise(NewS,N3,E3,N2,E2).

picknode([X|Y],S,E,M)
  :- descendants(X,E,D),
     intersection(S,D,[]),!,
     M = X.
picknode([X|Y],S,E,M) :- picknode(Y,S,E,M).

descendants(X,E,D)
  :- T = [X],
     D1 = [],
     get_descendants(T,E,D1,D).

get_descendants([],E,D,D).
get_descendants([H|T],E,D1,D)
  :- D4 = [],
     successors(H,E,D4,D2),
     append(D2,D1,D3),
     append(D2,T,T1),
     get_descendants(T1,E,D3,D).

successors(H,[],D,D).
successors(H,[[[H|Y],_]|T],D2,D)
  :- append(Y,D2,D5),
     successors(H,T,D5,D).
successors(H,[F|T],D2,D) :- successors(H,T,D2,D).

updatecostsandmarks(M,N1,E1,N3,E3,Minedge,Upd)
  :- getallconnectors(M,E1,C),
     getmincostedge(C,N1,Minedge,Mincost),
     updatecostofnode(M,Mincost,N1,N3,Upd),
     updatemarkonedges(Minedge,E1,E3).

getallconnectors(M,E1,C)
  :- C1 = [],
     connectors(M,E1,C1,C).

connectors(M,[],C1,C1).
connectors(M,[[[M|Y],_]|T],C1,C)
  :- edge(M,Y,Cost),
     append([[[M|Y],Cost]],C1,C2),
     connectors(M,T,C2,C).
connectors(M,[H|T],C1,C) :- connectors(M,T,C1,C).

getmincostedge([[[X|Y],Cost]],N1,[X|Y],C1)
  :- getcostofnodesinedge(Y,N1,C2),
     C1 is Cost + C2.
getmincostedge([[[X|Y],Cost]|T],N1,Minedge,Mincost)
  :- getmincostedge(T,N1,M1,C1),
     getcostofnodesinedge(Y,N1,C3),
     C1 < Cost + C3,!,
     Minedge = M1,
     Mincost = C1.
getmincostedge([[[X|Y],Cost]|T],N1,Minedge,Mincost)
  :- Minedge = [X|Y],
     getcostofnodesinedge(Y,N1,C3),
     Mincost is Cost + C3.
getcostofnodesinedge([],N1,0).
getcostofnodesinedge([X|Y],N1,C2)
  :- costofnode(X,N1,C3),
     getcostofnodesinedge(Y,N1,C4),
     C2 is C3 + C4.
costofnode(X,[[X,C3]|Y],C3).
costofnode(X,[H|T],C3) :- costofnode(X,T,C3).

updatecostofnode(M,Mincost,N1,N3,Upd)
  :- N2 = [],
     updatecost(M,Mincost,N1,N2,N3,Upd).

updatecost(M,Mincost,[],N2,N2,Upd).
updatecost(M,Mincost,[[M,C]|T],N2,N3,Upd)
  :- Mincost > C,
     append([[M,Mincost]],N2,N4),
     Upd = yes,
     updatecost(M,Mincost,T,N4,N3,Upd).
updatecost(M,Mincost,[[M,C]|T],N2,N3,Upd)
  :- Mincost = C,
     append([[M,C]],N2,N4),
     Upd = no,
     updatecost(M,Mincost,T,N4,N3,Upd).

updatecost(M,Mincost,[H|T],N2,N3,Upd)
  :- append([H],N2,N4),
     updatecost(M,Mincost,T,N4,N3,Upd).

updatemarkonedges(Minedge,E1,E3)
  :- E2 = [],
     updatemarks(Minedge,E1,E2,E3).

updatemarks(Minedge,[],E2,E2).
updatemarks([M|R],[[[M|R],_]|T],E2,E3)
  :- append([[[M|R],m]],E2,E4),
     updatemarks([M|R],T,E4,E3).
updatemarks([M|X],[[[M|Y],m]|T],E2,E3)
  :- append([[[M|Y],u]],E2,E4),
     updatemarks([M|X],T,E4,E3).
updatemarks(Minedge,[H|T],E2,E3)
  :- append([H],E2,E4),
     updatemarks(Minedge,T,E4,E3).

checkandmarksolved([M|T],Sol)
  :- allsuccessorssolved(T),!,
     retract(h(M,Y,Z)),
     assert(h(M,Y,solved)),
     Sol = yes.
checkandmarksolved(X,Sol)
  :- Sol = no.

allsuccessorssolved([]).
allsuccessorssolved([X|Y])
  :- h(X,_,solved),
     allsuccessorssolved(Y).

updateS(M,S,E,Upd,Sol,NewS)
  :- (Upd = yes ; Sol = yes),!,
     P1 = [],
     markedparentsofM(M,E,P1,P),
     append(S,P,NewS).

updateS(M,S,E,Upd,Sol,S).

markedparentsofM(M,[],P,P).
markedparentsofM(M,[[[X|Y],m]|T],P1,P)
  :- member(M,Y),!,
     append([X],P1,P2),
     markedparentsofM(M,T,P2,P).
markedparentsofM(M,[H|T],P1,P) 
  :- markedparentsofM(M,T,P1,P).

solve(N1,E1,N1,E1)
  :- startnode(Sn),
     h(Sn,_,solved).
solve(N,E,N3,E3)
  :- selectnode(N,E,Node),
     expand(N,E,Node,N1,E1),
     revisecosts(N1,E1,Node,N2,E2),
     solve(N2,E2,N3,E3).

ao :-
  initgraph(N1,E1),
  solve(N1,E1,N,E),
  compute(N,E,SN,SE),
  tell(f),
  output(SN,SE),
  told.

compute(N,E,SN,SE)
  :- startnode(Nd),
     Nodes = [Nd],
     costofnode(Nd,N,C),
     N1 = [[Nd,C]],
     E1 = [],
     solgraph(N,E,Nodes,N1,E1,SN,SE).

solgraph(N,E,[],SN,SE,SN,SE).
solgraph(N,E,[H|T],N1,E1,SN,SE)
  :- getmarkededge(H,E,[X|Y]),!,
     append(Y,T,T1),
     append([[X|Y]],E1,E2),
     putnodes(N,Y,N1,N2),
     solgraph(N,E,T1,N2,E2,SN,SE).
solgraph(N,E,[H|T],N1,E1,SN,SE) :- solgraph(N,E,T,N1,E1,SN,SE).

getmarkededge(H,[[[H|Y],m]|T],[H|Y]).
getmarkededge(H,[X|Y],E) :- getmarkededge(H,Y,E).

putnodes(N,[],N2,N2).
putnodes(N,[H|T],N1,N2)
  :- costofnode(H,N,C),
     append([[H,C]],N1,N3),
     putnodes(N,T,N3,N2).

output(SN,SE)
  :- print('Nodes in the solution graph :'),nl,nl,
     remduplicates(SN,SN1),
     outnodes(SN1),
     nl,nl,
     print('Edges in the solution graph :'),nl,nl,
     outedges(SE).

outnodes([]).
outnodes([[N,C]|T])
  :- print(N),print('   cost='),print(C),nl,outnodes(T).

outedges([]).
outedges([H|T])
  :- print(H),nl,outedges(T).

remduplicates(SN,SN1)
  :- SN2 = [],
     remdup(SN,SN2,SN1).

remdup([],SN2,SN2).
remdup([H|T],SN2,SN1)
  :- not member(H,T),!,
     append([H],SN2,SN3),
     remdup(T,SN3,SN1).
remdup([H|T],SN2,SN1) :- remdup(T,SN2,SN1).