% A graph with n labelled nodes and q labelled edges is said "garceful" iff
% each node has different label in [0 .. q]
% each edge between nodes i j of labels xi xj has label |xi-xj|
% all edge labels are differents
% Example with some symetries which depend on the graph
% sym de valeur: xi -> q-xi
% sym de var: cliques, path reversibility
% Nota: graphs with trivial solution: q+1 nodes and q edges
% Difficult case: 2 cliques of 5 nodes.
% Problem originating from telecommunications
%[sbds_allpl].['gracefulgraph-gnu-sbds']. codeine(grace,xml). codeine_maxint(210).fd_set_vector_max(210).
%[sbds_allpl],['gracefulgraph-gnu-sbds'], codeine(grace,xml), codeine_maxint(210),fd_set_vector_max(9).
%:-include('exemples/n8q7.pl').
%:-include('exemples/n10q25.pl').
:-include('n6q9.pl').
%:-include('exemples/n8q16.pl').

q(NV,LV,NE,LE) :-
  nbnodes(NV), length(LV,NV),
  nbedges(NE), length(LE,NE), fd_domain(LE,1,NE),  fd_domain(LV,0,NE),
  findall((I,J) ,edge(I,J), Arcs),
  buildgraph(Arcs,LV,LDe),
  extract(LDe,LE), 
  fd_all_different(LE),
  fd_all_different(LV),
  postcontr(LDe),

%% n10q25
%  ieme(1,LV,First),
%  First#<13,

  write('start label'),nl,
  fd_labeling(LV).

qsym(NV,LV,NE,LE) :-
  nbnodes(NV), length(LV,NV),
  nbedges(NE), length(LE,NE), fd_domain(LE,1,NE),  fd_domain(LV,0,NE),
  findall((I,J) ,edge(I,J), Arcs),
  buildgraph(Arcs,LV,LDe),
  extract(LDe,LE), 
  fd_all_different(LE),
  fd_all_different(LV),  
  postcontr(LDe),

  % value symmetries
%% n8q7
  %ieme(1,LV,First),
  %First#<4,
%% n10q25
  %ieme(1,LV,First),
  %First#<13,
  
%% n8q16
  %ieme(1,LV,First),
  %First#<8,
  
  % variable symmetries 
%% n8q7
  %LSym=[sym(varval,[8,7,6,5,4,3,2,1],[0,1,2,3,4,5,6,7]),sym(varval,[1,2,3,4,5,6,7,8],[7,6,5,4,3,2,1,0])],
%% n10q25
%  liste_num(L25,0,25),
%  liste_num(L10,1,10),
%  LSym=[ sym(varval,[2,3,4,5,1,7,8,9,10,6],L25) , sym(varval,[2,1,3,4,5,7,6,8,9,10],L25),sym(varval,[6,7,8,9,10,1,2,3,4,5],L25),sym(varval,L10,[25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]) ],

  %n8q16
  %liste_num(L16,0,16),
  %liste_num(L8,1,8),
  %LSym=[sym(varval,[2,3,4,1,6,7,8,5],L16) , sym(varval,[2,1,3,4,6,5,7,8],L16),sym(varval,[5,6,7,8,1,2,3,4],L16),sym(varval,L8,[16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0])],

 %n6q9
  liste_num(L9,0,9),
  liste_num(L6,1,6),
  LSym=[sym(varval,[2,3,1,5,6,4],L9), sym(varval,[2,1,3,5,4,6],L9),sym(varval,[4,5,6,1,2,3],L9),sym(varval,L6,[9,8,7,6,5,4,3,2,1,0])],

  % labeling
  write('start label'),nl,
%  fd_labeling_sbds(LV,[group(LSym)]).
  fd_labeling_sbds(LV,LSym).
  
buildgraph([],_,[]).
buildgraph([(I,J)|Arcs],LV,[(I,XI,J,XJ,_)|LD]) :- 
  ieme(I,LV,XI),ieme(J,LV,XJ),buildgraph(Arcs,LV,LD).
  
postcontr([]).
postcontr([(_,XI,_,XJ,DIJ)|LDe]) :-   
%   XI**2+XJ**2-2*XI*XJ#=#DIJ**2,
%    (XI+DIJ#=#XJ;XJ+DIJ#=#XI),
   dist(XI,XJ)#=#DIJ,
    postcontr(LDe).

extract([],[]).
extract([(_,_,_,_,D)|LDe],[D|L]) :- extract(LDe,L).

ieme(1,[X|_],X) :-!.
ieme(I,[_|L],Y) :- I>1, I1 is I-1, ieme(I1,L,Y).

equal([],[]).
equal([E|L],[E2|L2]) :- E#=E2, equal(L,L2).