% Video Presentation Design by Graph Searching
% Copyright, David Poole, 1997.

% Here are soem example queries
% ask hsearch(depth,[node(vp([welcome,robots],[]),[],0,0)],P).
% ask hsearch(breadth,[node(vp([welcome,skiing,robots],[]),[],0,0)],P).

% segment(SegId, Duration, Covers)

segment(seg0,10,[welcome]).
segment(seg1,30,[skiing,views]).
segment(seg2,50,[welcome,computational_intelligence,robots]).
segment(seg3,40,[graphics,dragons]).
segment(seg4,50,[skiing,robots]).

% all_segments(L) is true if list L is the list of all of the segments
all_segments([seg0,seg1,seg2,seg3,seg4]).

% A node is of the form
%   vp(ToCover,Segs) where ToCover is a list of topics to cover and
% Segs is a list of segments.

is_goal(vp([],_)).

% neighbours(Node,Neighs) is true if Neighs is the list of neighbours
% of node Node.

% example query:
% ask neighbours(vp([welcome,robots],[]),Neighs).

neighbours(vp([],_),[]).

neighbours(Node,Neighs) <-
   all_segments(AllSegs) &
   neighbour_segments(AllSegs,Node,Neighs).

% neighbour_segments(AllSegs,Node,Neighs). Is true if Neighs is the
% list of all neighbours of Node that use segments in AllSegs.

neighbour_segments([],_,[]).
neighbour_segments([Seg|RSegs],vp([Topic|OtherTopics],Segs),
                        [vp(TopicsToCover,[Seg|Segs])|Neighs]) <-
   segment(Seg,_,SegTopics) &
   member(Topic,SegTopics) &
   listdiff(OtherTopics,SegTopics,TopicsToCover) &
   neighbour_segments(RSegs,vp([Topic|OtherTopics],Segs),Neighs).

neighbour_segments([Seg|RSegs],vp([Topic|OtherTopics],Segs),Neighs) <-
   segment(Seg,_,SegTopics) &
   notin(Topic,SegTopics) &
   neighbour_segments(RSegs,vp([Topic|OtherTopics],Segs),Neighs).

% cost(N1,N2,C) is true if C is the cost of the arc <N1,N2>

cost(vp(_,Segs),vp(_,[Seg|Segs]),SegTime) <-
   segment(Seg,SegTime,_).

% listdiff(L1,L2,L3) is true if L3 contains the elements of L1 that
% are not also in L2
listdiff([],_,[]).
listdiff([H|T],S,RT) <-
   member(H,S) &
   listdiff(T,S,RT).
listdiff([H|T],S,[H|RT]) <-
   notin(H,S) &
   listdiff(T,S,RT).

% member(A,L) is trie if A is in list L
member(A,[A|_]).
member(A,[_|L]) <-
   member(A,L).

% notin(A,L) is true if A isn't in list L
notin(_,[]).
notin(A,[B|L]) <-
   A \= B &
   notin(A,L).