% 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

%['gracefulgraph-gnu']. codeine(grace,xml). codeine_maxint(210).fd_set_vector_max(210).

:-include(n6q9).

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),
  fd_labeling(LV).

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),
    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).