/*
Examen PPC 2022-2023
Corrigé de l'exercice 3
*/


/*
inclus(Arg1,Arg2): Arg1 inclus dans Arg2 (au sens large)
*/
inclus(_,[0]).
inclus([A,B],[C,D]):-A>=C,
	B=<D.
/*
transposee/ : transposee(Arg1) = Arg2
*/
transposee([0],[0]).
transposee([A,B],[C,D]):-C is (-B),
	D is (-A).
/*
inters/3 : Arg1 inters Arg2 = Arg3
*/
inters([0],A,A).
inters(A,[0],A).
inters([A,B],[C,D],[E,F]):-max(A,C,E),
	min(B,D,F).
/*
max/3 : maximum(Arg1,Arg2) = Arg3
*/
max(A,B,Max):-A>=B,
	!,
	Max is A.
max(_,A,Max):-Max is A.
/*
min/3 : minimum(Arg1,Arg2) = Arg3
*/
min(A,B,Min):-A=<B,
	!,
	Min is A.
min(_,A,Min):-Min is A.
/*
comp/3 : Arg1 ° Arg2 = Arg3
*/
comp([0],_,[0]).
comp(_,[0],[0]).
comp([A,B],[C,D],[E,F]):-E is A+C,
	F is B+D.
bdAC([L0|M]):-verifier(L0,M,1).
verifier(_,[],_):-write('bd-consistance d arc verifiee'),
	!.
verifier(L0,[LJ|M],J):-length(Gauche,J),
	append(Gauche,[ZeroJ|_],L0),
	verifier2(ZeroJ,L0,LJ,J,0),
	Jplus1 is J+1,
	verifier(L0,M,Jplus1).
verifier2(_,[],[],_,_):-!.
verifier2(ZeroJ,[ZeroI|L0],[JI|LJ],J,I):-comp(ZeroJ,JI,Comp),
	inclus(ZeroI,Comp),
	!,
	Iplus1 is I+1,
	verifier2(ZeroJ,L0,LJ,J,Iplus1).
verifier2(ZeroJ,[ZeroI|_],[JI|_],J,I):-writeln('bd-consistance d arc non verifiee: ZeroI non inclus dans ZeroJ ° JI'),
	write('I = '),write(I),write(' ZeroI = '),writeln(ZeroI),
	write('J = '),write(J),write(' ZeroJ = '),writeln(ZeroJ),
	write(' JI = '),writeln(JI),
	fail.
/*
REMARQUE :
Les lignes et les colonnes de Mp sont indicees de 0 à Nv-1,
	Nv étant le nombre de variables.

EXEMPLE :
Testé avec la représentation matricielle Mp du STP P = (X,C), avec :
- X = {X0,X1,X2}
- C = {c1: (X1-X0) in [0,1],c2:(X2-X0) in [5,6],
       c3: (X2-X1) in [2,3]}

[[[0,0],[0,1],[5,6]],
 [[-1,0],[0,0],[2,3]],
 [[-6,-5],[-3,-2],[0,0]]]

bdAC([[[0,0],[0,1],[5,6]],[[-1,0],[0,0],[2,3]],[[-6,-5],[-3,-2],[0,0]]]).

Un autre exemple :
bdAC([[[0,0],[0,1],[2,4]],[[-1,0],[0,0],[2,3]],[[-4,-2],[-3,-2],[0,0]]]).
*/