%:-use_module(library(clpfd)).
%:-use_module(library(lists)).

%%% Usiamo grafi con archi diretti

testa(5,[[1,2],[2,3],[3,4],[4,5],[5,2]]). %%% NO 
testb(5,[[1,2],[2,3],[3,4],[4,5],[5,2],[5,1]]). %%% YES

hc( N, Edges ) :-
   statistics(runtime,_),
   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   length(Path, N ),
   domain( Path, 1, N),
   all_edges( 1, Path, Edges ), %%%
   %%%all_edges_fdset( 1, Path, Edges ),
   circuit( Path ),  
   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   statistics(runtime,[_,T1]),
   write('Constraint Time: '),write(T1),nl,
   labeling([ff], Path),
   !,
   statistics(runtime,[_,T2]),
   write('Labeling Time: '),write(T2),nl,
   write_path(Path,N),nl.
   
hc( _, _ ) :-
   statistics(runtime,[_,T]),
   write('No Hamiltonian circuits: time '),write(T),nl.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% All path edges must use graph edges !
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% VERSION USING FDSETS

%all_edges_fdset( _ , [], _) :- !.
%all_edges_fdset( M , [ X | R ], Edges) :-
%   findall(Y, member([M,Y],Edges),Values),
%   list_to_fdset(Values,Set),
%   X in_set Set, %%% <==== dominio  
%   M1 is M + 1,
%   all_edges_fdset( M1, R, Edges).
%%% NB. Gli archi sono diretti. Se li vogliamo
%%% non diretti basta mettere
%%%  findall(Y, ( member([M,Y],Edges);
%%%               member([Y,M],Edges) ),Values),

%%% OLD VERSION WITH A BOOLEAN FORMULA
%%% All path edges must use graph edges !

all_edges( _ , [], _) .
all_edges( M , [ X | R ], Edges) :-
   member_edge( M, X, Edges ),
   M1 is M + 1,
   all_edges( M1, R, Edges).

%%% Look for edge [M,X] where X = circuit[M]

member_edge(M,X,Edges) :-
   member_edge(M,X,Edges,1). %%% 1 = true
    
member_edge( _, _ ,[], 0). %%% 0 = false

%%% A e D sono ground. B e' var FD

member_edge( A, B ,[[A,D] | R ], Constraint) :-
   !,
   member_edge( A, B ,R,Con2),
   Constraint #<=> Con2 #\/ (B #= D).
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Se non vogliamo gli archi diretti basta decommentare
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%member_edge( A, B ,[[D,A] | R ], Constraint) :-
%   !,
%   member_edge( A, B ,R,Con2),
%   Constraint #<=> Con2 #\/ ( B #= D).

member_edge( A, B ,[[_,_] | R ], Constraint) :-
   member_edge( A, B ,R,Constraint).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definizione alternativa MOLTO piu' inefficiente (provare) 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%member_edge( A, B ,[[C,D] | R ], Constraint) :-
%   member_edge( A, B ,R,Con2),
%   Constraint #<=> Con2 #\/
%           ( (A #= C #/\ B #= D) #\/
%             (A #= D #/\ B #= C) ).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

write_path(Path,N) :-
   write('Path: '),
   write_path(1,N,Path).
   
write_path(_,0,_) :- !.
write_path(M, N,Path) :-
   element(M,Path,El),
   write(El), write(' , '),
   N1 is N - 1,
   write_path(El,N1,Path).   
   

