%Implementace Goldbergova algoritmu
%(c)2002 Petr Cermak <cermak01@seznam.cz>
%Format V/V grafu:
%seznam [CisloVrcholu-[CisloNaslednika-kapacita_hrany]]
%Format site:
%sit(CisloZdroje, CisloStoku)

%graf1
%     2--3 
%    /  / \
%   1   |  4
%    \ /  /
%     6--5      vsechny kapacity: 10 krome 6-3: 1
graf1([1-[2-10,6-10], 2-[3-10], 3-[4-10], 4-[], 5-[4-10], 6-[3-1, 5-10]], sit(1, 4)).
%Kratky
graf2([1-[2-5], 2-[3-1], 3-[]], sit(1, 3)).
%Slepe strevo
graf3([1-[2-5],2-[3-5],3-[6-5],4-[5-5],5-[6-5],6-[7-5],7-[8-1], 8-[9-5], 9-[]], sit(1, 9)).
%Dlouha cesta s jednou zmensenou kapacitou
graf4([1-[2-5],2-[3-5],3-[4-5],4-[5-5],5-[6-5],6-[7-5],7-[8-5], 8-[9-5], 9-[10-5], 10-[11-5], 11-[12-5], 
	12-[13-5], 13-[14-5], 14-[15-5], 15-[16-5], 16-[17-5], 17-[18-5], 18-[19-5], 19-[20-5], 
	20-[21-5], 21-[22-5], 22-[23-1], 23-[26-26], 24-[25-5], 25-[26-5], 26-[27-5], 27-[]], sit(1, 27)). 
%Kuceruv graf
graf5([1-[2-18, 3-81, 4-69], 2-[5-10, 6-5, 7-1, 8-8], 3-[5-64, 6-66, 7-67], 4-[8-85], 5-[9-2, 10-88],
	6-[9-20, 10-1], 7-[10-79], 8-[9-1, 10-83], 9-[11-67], 10-[11-88], 11-[]], sit(1, 11)).
%Michal - v jednom z techto dvou grafu je velikost toku nulova
graf6([1-[4-5,7-5],2-[],3-[1-5],4-[3-5],5-[1-5,6-5],6-[1-4],
	7-[8-4,9-4,10-4,11-4],8-[12-3],9-[7-4],10-[12-3], 
	11-[14-3],12-[9-3],13-[15-3],14-[13-3],15-[18-2],
	16-[15-2,18-2,17-2],17-[],18-[17-2,19-2],19-[22-2],
	20-[18-2,19-2,22-2,26-2],21-[19-1,23-2],22-[23-1,24-2],
	23-[25-3],24-[21-3],25-[26-1],26-[16-3,27-2], 27-[16-4]],
	sit(1, 27)).
graf7([1-[4-5,7-5],2-[],3-[1-5],4-[3-5],5-[1-5,6-5],6-[1-4],7-[8-4,9-8,10-4,11-4],
	8-[12-3],9-[7-4],10-[12-3],11-[14-3],12-[9-3],13-[3-3],14-[13-3],15-[18-2],
	16-[15-2,18-2,17-2],17-[],18-[17-2,19-2],19-[22-2],20-[18-2,19-2,22-2,26-2],
	21-[19-1,23-2],22-[23-1,24-2],23-[25-3],24-[21-3,23-4],25-[26-1],26-[16-3,27-2],
	27-[16-4]], sit(1, 27)).
%Paradox
graf8([1-[2-5], 2-[3-5, 5-3], 3-[4-5], 4-[2-5], 5-[]], sit(1, 5)).
%Smycka a<-->b
graf9([1-[2-5], 2-[3-6], 3-[2-4, 4-6], 4-[]], sit(1, 4)).
%Nasobna hrana
graf10([3-[4-10], 2-[3-5, 3-3], 4-[], 1-[2-10]], sit(1, 4)).
%Nesouv. komp, smycky, nas. hrany.
graf11([1-[1-5,2-1,2-1,9-3,9-4,9-5],2-[3-3,9-2],3-[6-3],4-[7-3],5-[4-3],6-[2-3],7-[8-3],8-[3-1,8-5,9-5],9-[1-2,9-3],10-[]], sit(1, 9)). 

prikl1:-graf1(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl2:-graf2(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl3:-graf3(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl4:-graf4(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl5:-graf5(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl6:-graf6(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl7:-graf7(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl8:-graf8(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl9:-graf9(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl10:-graf10(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.
prikl11:-graf11(G, S), run(G, S, O, Vel), write('Puvodni: '), write(G), nl, write(S), nl, write('Tok: '), write(O), nl, write('Velikost: '), write(Vel), nl.

%----------------
% Hlavni predikat
%----------------

%timto se spousti program
%param: graf ve V/V formatu+, sit(Zdroj, Stok) - cisla vrcholu+, vystup-
run(Graf, Sit, VystupG, VystupVel):-
	quicksort(Graf, Graf1),                 %seradi vrcholy podle velikosti
	seradNasl(Graf1, Graf2),                %seradi jejich nasledniky podle velikosti
	elimNasobne(Graf2, BezNas),             %slouci nasobne hrany
	pridejOpHrany(BezNas, Graf3),           %prida opacne hrany s nulovou kapacitou
	v2muj(Graf3, Graf4),                    %prevede na format [vrchol()-[hrana(vrchol(),rezerva),...],...]
	inicializace(Graf4, Sit, StartAlg),     %provede prvni krok algoritmu
	vypocet(StartAlg, Sit, KonecAlg),       %vlastni vypocet
	muj2v(KonecAlg, Graf5),                 %preved z formatu vrchol()... na [cislo-[cisloNasl-OhHrany]]
	elimNasobne(Graf5, Graf6),              %opet slouci nas. hrany vznikle z smycky a<-->b
	vycisti(BezNas, Graf6, Graf6, Graf7),   %porovna graf s puvodnim grafem a vypusti pridane hrany
	vratNasobne(Graf7, Graf2, VystupG),     %rozdeli sloucene hrany do puvodnich nasobnych
	spocVelikost(Graf7, Sit, VystupVel).         %spocita velikost toku

%--------------
% Velikost toku
%--------------

%Spocita velikost toku (to co vtece do stoku, ze stoku nic nevyteka)
%param: Graf ve V/V formatu+, sit+, velikost toku-

spocVelikost([], _, 0).
spocVelikost([_-Nasl|Zb], sit(_, CisloS), Out):-
	sectiDoStoku(Nasl, CisloS, Souc),
	spocVelikost(Zb, sit(_, CisloS), SoucZb),
	Out is Souc+SoucZb.

sectiDoStoku([], _, 0).
sectiDoStoku([CisloS-Tok|Zb], CisloS, SoucOut):-
	sectiDoStoku(Zb, CisloS, Souc),
	SoucOut is Souc+Tok.
sectiDoStoku([Cislo-_|Zb], CisloS, SoucOut):-
	Cislo\=CisloS,
	sectiDoStoku(Zb, CisloS, SoucOut).

%-------------------------------------------------------
% Vyroba grafu se kterym pracuje algoritmus (sit rezerv)
%-------------------------------------------------------

%Slouci nasobne hrany do jedne
%param: graf ve V/V formatu+, vystup-
elimNasobne([], []).
elimNasobne([Cislo-Nasl|Zb], [Cislo-NaslOut|ZbOut]):-
	elimNasl(Nasl, NaslOut),
	elimNasobne(Zb, ZbOut).

elimNasl([], []).
elimNasl([Cislo-Rez|Zb], [Cislo-RezOut|ZbOut]):-
	sectiNasl(Cislo, [Cislo-Rez|Zb], ZbNext, RezOut),
	elimNasl(ZbNext, ZbOut).

sectiNasl(CisloNasl, [CisloNasl-Data|Zb], ZbOut, SoucOut):-
	sectiNasl(CisloNasl, Zb, ZbOut, SoucNasl),
	SoucOut is SoucNasl + Data.
sectiNasl(CisloNasl, [CisloN-_|Zb], ZbOut, SoucOut):-
	CisloNasl@>CisloN,
	sectiNasl(CisloNasl, Zb, SoucOut).
sectiNasl(CisloNasl, [CisloN-Rez|Zb], [CisloN-Rez|Zb], 0):-
	CisloNasl@<CisloN.
sectiNasl(_, [], [], 0).

%--

%Ke kazde hrane prida hranu opacne orientovanou s nulovou kapacitou
%param: Graf ve V/V formatu+, vystup-
pridejOpHrany(Graf, Out):-
	obratGraf(Graf, GObr),
	vynulujRezervy(GObr, GObr1),
	slucGrafy(Graf, GObr1, Out).

%Vynuluje vsechny rezervy daneho grafu
%param: Graf ve V/V formatu+, vystup-
vynulujRezervy([], []).
vynulujRezervy([Cislo-Nasl|Zb], [Cislo-NaslOut|ZbOut]):-
	vynulujHrany(Nasl, NaslOut),
	vynulujRezervy(Zb, ZbOut).

vynulujHrany([], []).
vynulujHrany([Cislo-_|Zb], [Cislo-0|ZbOut]):-
	vynulujHrany(Zb, ZbOut).

%--

%Slouci hrany grafu Graf1 a Graf2, vrcholy si musi odpovidat. 
%param: Graf1 ve V/V formatu+, Graf2 ve V/V formatu+, vystup-
slucGrafy(Graf1, Graf2, Out):-
	sluc(Graf1, Graf2, Out1),
	seradNasl(Out1, Out).

sluc([], [], []).
sluc([Cislo1-Nasl1|Zb1], [Cislo2-Nasl2|Zb2], [Cislo1-NaslOut|ZbOut]):-
	Cislo1==Cislo2,
	append(Nasl1, Nasl2, NaslOut),
	sluc(Zb1, Zb2, ZbOut).

%--------------------------------------------------
% Predikaty pro prevod site rezerv na vystupni graf
%--------------------------------------------------

%Odstrani z grafu pridane opacne hrany, nesmeji v nem byt hrany nasobne
%param: puvodni graf ve V/V formatu+, graf k procisteni ve V/V formatu+, jeste jednou k procisteni+, vystup
vycisti([], [], _, []).
vycisti([Cislo-SeznamP|ZbP], [Cislo-SeznamN|ZbN], Cele, [Cislo-SeznamOut|ZbOut]):-
	vycistiHrany(Cislo, SeznamP, SeznamN, Cele, SeznamOut),
	vycisti(ZbP, ZbN, Cele, ZbOut).

%Pro prebyvajici hrany v puvodnim grafu predikat neuspeje.
vycistiHrany(_, [],_,_,[]).
vycistiHrany(CisloV, [CisloP-DataP|ZbP], [CisloN-DataN|ZbN], Cele, Out):-
	CisloP@>CisloN,
	vycistiHrany(CisloV, [CisloP-DataP|ZbP], ZbN, Cele, Out).
vycistiHrany(CisloV, [CisloP-_|ZbP], [CisloN-TokN|ZbN], Cele, [CisloN-TokOut|ZbOut]):-
	CisloP==CisloN,
	najdiTok(CisloN, CisloV, Cele, TokOpacny),
	(TokOpacny@>=TokN -> TokOut=0;
	TokOut is TokN-TokOpacny),
	vycistiHrany(CisloV, ZbP, ZbN, Cele, ZbOut).

%Najde velikost toku na hrane Cislo-CisloN
%param: Poc. vrhol+, koncovy vrchol hrany+, cely graf+, Tok-
najdiTok(Cislo, CisloN, [Cislo-Nasl|_], Tok):-
	najdiTokNasl(CisloN, Nasl, Tok).
najdiTok(Cislo, CisloN, [CisloV-_|Zb], Tok):-
	Cislo\=CisloV,
	najdiTok(Cislo, CisloN, Zb, Tok).

najdiTokNasl(CisloN, [CisloN-Tok|Zb], Tok).
najdiTokNasl(CisloN, [CisloV-_|Zb], Tok):-
	CisloN\=CisloV,
	najdiTokNasl(CisloN, Zb, Tok).

%--

%Z puvodniho grafu s kapacitami a z vysledneho grafu s toky (bez nasobnych hran) vyrobi finalni graf s nas. hranami
%param: Posledni graf+, puvodni graf+, vystup-
vratNasobne([], [], []).
vratNasobne([CisloN-NaslN|ZbN], [CisloN-NaslP|ZbP], [CisloN-NaslOut|ZbOut]):-
	vratNasobneNasl(NaslN, NaslP, NaslOut),
	vratNasobne(ZbN, ZbP, ZbOut).

vratNasobneNasl([CisloN-Tok|ZbN], [CisloN-Rezerva|ZbP], [CisloN-TokOut|ZbOut]):-
	(Rezerva@>=Tok ->
		TokOut=Tok,
		TokNext=0;
	TokOut=Rezerva,
	TokNext is Tok-Rezerva),
	vratNasobneNasl([CisloN-TokNext|ZbN], ZbP, ZbOut).	
vratNasobneNasl([CisloN-Tok|ZbN], [CisloP-Rezerva|ZbP], ZbOut):-
	CisloN\=CisloP,
	vratNasobneNasl(ZbN, [CisloP-Rezerva|ZbP], ZbOut).
vratNasobneNasl(_, [], []).

%-------------------------------------------------------------
% Konverze V/V format <-> Format, se kterym pracuje algoritmus
%-------------------------------------------------------------

%Prevede graf z vstupniho/vystupniho formatu na format se kterym pracuje vlastni program
%param: graf ve vstupnim formatu (V/V)+, graf ve formatu pro algoritmus-
v2muj([], []).
v2muj([Cislo-Nasl|Zb], [vrchol(Cislo, 0, 0)-Hrany|ZbOut]):-
	v2mujNasl(Nasl, Hrany),
	v2muj(Zb, ZbOut).

v2mujNasl([], []).
v2mujNasl([Cislo-Rezerva|Zb], [hrana(vrchol(Cislo, 0, 0), Rezerva, 0)|ZbOut]):-
	v2mujNasl(Zb, ZbOut).

%--

%Prevede graf zpet do puvodniho formatu (zahodi informace o prebytcich a vyskach vrcholu)
%param: graf ve formatu pro algoritmus+, graf ve vystupnim formatu (V/V)-
muj2v([], []).
muj2v([vrchol(Cislo,_,_)-Hrany|Zb], [Cislo-Nasl|ZbOut]):-
	muj2vHrany(Hrany, Nasl),
	muj2v(Zb, ZbOut).

muj2vHrany([], []).
muj2vHrany([hrana(vrchol(Cislo,_,_), _, Tok)|Zb], [Cislo-TokOut|ZbOut]):-
	(Tok@<0 ->TokOut=0;
	TokOut=Tok),
	muj2vHrany(Zb, ZbOut).

%---------------
% Obraceni grafu
%---------------

% Obrati vsechny hrany v grafu. 
%param: graf V/V format+, vystup-
obratGraf(Graf, Out):-
	udelejPrazdny(Graf, Prazdny),
	obrat(Graf, Prazdny, Out1),
	seradNasl(Out1, Out).

obrat([], Seznam, Seznam).
obrat([Cislo-Nasl|Zb], Seznam, Out):-
	obratHrany(Nasl, Cislo, Seznam, Out1),
	obrat(Zb, Out1, Out).

obratHrany([], _, Seznam, Seznam).
obratHrany([Cislo-Rezerva|Zb], CisloV, Seznam, Out):-
	pridejDoSeznamu(Cislo, CisloV-Rezerva, Seznam, Out1),
	obratHrany(Zb, CisloV, Out1, Out).

udelejPrazdny([], []).
udelejPrazdny([Cislo-Nasl|Zb], [Cislo-[]|ZbOut]):-
	udelejPrazdny(Zb, ZbOut). 

%-----------------------------
% Prace se seznamem nasledniku
%-----------------------------

%Prida do seznamu typu [Prihradka-[seznam polozek typu Cislo-Data]] danou polozku,
%neexistuje-li takova prihradka, neuspeje
%param: prihradka+, dvojice klic-polozka+, cely seznam+, vystup-
pridejDoSeznamu(Prihradka, Cislo-Polozka, [PrihC-Data|Zb], [PrihC-DataOut|ZbOut]):-
	Prihradka==PrihC,
	append([Cislo-Polozka], Data, DataOut),
	ZbOut=Zb.
pridejDoSeznamu(Prihradka, Cislo-Polozka, [PrihC-Data|Zb], [PrihC-DataOut|ZbOut]):-
	Prihradka\=PrihC,
	DataOut=Data, 
	pridejDoSeznamu(Prihradka, Cislo-Polozka, Zb, ZbOut).

%--

%V celem grafu seradi seznamy nasledniku. Vstup - V/V format.
%param: graf ve V/V formatu+, vystup-
seradNasl([], []).
seradNasl([Cislo-Nasl|Zb], [Cislo-NaslOut|ZbOut]):-
	quicksort(Nasl, NaslOut),
	seradNasl(Zb, ZbOut).

%-----
% Sort
%-----

%Prevzato (a upraveno) z knizky 
%NEPROCEDURALNI PROGRAMOVANI A UVOD  DO PROGRAMOVACIHO JAZYKA PROLOG, 
%Rudolf Kryl, KSVI MFF UK Praha
%Seznam vzdy tvaru Klic-Data

split(_,[],[],[]).
split(Pivot-Prm,[Y-A|Zbytek],[Y-A|Male],Velke) :-
	Pivot>Y,
	split(Pivot-Prm,Zbytek,Male,Velke).
split(Pivot-Prm,[Y-A|Zbytek],Male,[Y-A|Velke]) :-
	Pivot=<Y,
	split(Pivot-Prm,Zbytek,Male,Velke).
quick([Pivot|Zbytek],S,Konec):-
	split(Pivot,Zbytek,Mala,Velka),
	quick(Mala,S,[Pivot|Y]),
	quick(Velka,Y,Konec).
quick([],Konec,Konec).
quicksort(Vstup,Setrideno) :-
	quick(Vstup,Setrideno,[]).
		
%--------------------------------------------------------------
% Zbyvajici predikaty pracuji jiz jen s vnitrnim formatem grafu
%--------------------------------------------------------------
%---------------------
% Prvni krok algoritmu
%---------------------

%Nastavi zdroj do vysky N, vlozi do nej pocatecni prebytek
%odpovidajici souctu kapacit hran z nej vychazejicich.
%param: graf v alg. formatu+, sit+, vystup-
inicializace(Graf, sit(CisloZ, CisloS), Out):-
	pocVrcholu(Graf, 0, Poc),
	zmenVysku(CisloZ, Poc, Graf, Out1),
	soucRezerv(Graf, CisloZ, Preb),
	upravPrebytek1(CisloZ, Preb, Out1, Out2),
	poustej(Out2, Out2, sit(nocheck, CisloS), Out3),
	upravPrebytek1(CisloZ, 0, Out3, Out).


%Spocita pocet vrcholu grafu. Volani: pocVrcholu(Graf+, 0+, Pocet-)
pocVrcholu([], Poc, Poc).
pocVrcholu([_-_|Zb], Poc, Out):-
	PocN is Poc+1,
	pocVrcholu(Zb, PocN, Out).

%Secte rezervy vsech nasledniku daneho vrcholu. Predpoklada, ze vrchol CisloZ se naleza v grafu.
soucRezerv([vrchol(Cislo,_,_)-Nasl|Zb], CisloZ, Out):-
	(Cislo==CisloZ -> sectiRezervy(Nasl, 0, Out);
	soucRezerv(Zb, CisloZ, Out)).

sectiRezervy([], Souc, Souc).
sectiRezervy([hrana(_,Rez,_)|Zb], Souc, Out):-
	Souc1 is Souc + Rez,
	sectiRezervy(Zb, Souc1, Out).

%------------------------
% Hlavni cyklus algoritmu
%------------------------

%hlavni smycka algoritmu
%param: graf ve vnitrnim formatu pro alg.+, sit+, vystup-
vypocet(Graf, Sit, Vystup):-
	poustej(Graf, Graf, Sit, Out1),
	zvedej(Out1, Out1, Out2), 
	(Out2==konec -> Vystup=Out1;
	vypocet(Out2, Sit, Vystup)).

%---------
% Pousteni
%---------

%Pousti prebytky dokud to jde
%param: graf v alg. formatu+, jeste jednou+, sit+, vystup-

%jiz neni co poustet -> zvedej, nebo konec
poustej([], Cele, Sit, Cele).

%Preskoc vrcholy bez prebytku (+zdroj, stok)
poustej([vrchol(_,_,0)-_|Zb], Cele, Sit, Out):-
	poustej(Zb, Cele, Sit, Out).

%Nalezen vrchol vhodny pro pousteni
poustej([vrchol(Cislo, Vyska, Prebytek)-Sousede|Zb], Cele, Sit, Out):-
	Prebytek\=0,
	pust(vrchol(Cislo, Vyska, Prebytek), Sousede, false, Pusteno, Sit, Cele, CeleNext),	
	(Pusteno==false -> poustej(Zb, Cele, Sit, Out);
	poustej(CeleNext, CeleNext, Sit, Out)).   %Bylo pusteno, prohledej graf znovu od zacatku.

%--

%Soused ma vyssi vysku -> nejde poustet, dalsi
pust(vrchol(Cislo, Vyska, Prebytek), [hrana(vrchol(CisloS, VyskaS, PrebytekS), _, _)| ZbS], 
     Pusteno, PustenoOut, Sit, Cele, CeleOut):-
	Prebytek\=0,
	VyskaS@>=Vyska,
	pust(vrchol(Cislo, Vyska, Prebytek), ZbS, Pusteno, PustenoOut, Sit, Cele, CeleOut).

%Soused ma mensi vysku, ale neni to soused :-)  (rezerva hrany je nulova)
pust(vrchol(Cislo, Vyska, Prebytek), [hrana(vrchol(CisloS, VyskaS, PrebytekS), 0, _)| ZbS], 
     Pusteno, PustenoOut, Sit, Cele, CeleOut):-
	Prebytek\=0,
	VyskaS@<Vyska,
	pust(vrchol(Cislo, Vyska, Prebytek), ZbS, Pusteno, PustenoOut, Sit, Cele, CeleOut).

%Dosli jsme na konec - provadelo se pouze nasycene pousteni, zkopirujeme akumulatory na vystup
pust(vrchol(Cislo, Vyska, Prebytek), [], Pusteno, Pusteno, Sit, Cele, CeleOut):-
	Prebytek\=0,
	upravPrebytek(Cislo, Prebytek, Sit, Cele, CeleOut).

%Zde se skonci pri vycerpani prebytku. (Bud nenasycene pousteni, nebo nasycene, kde Rezerva=Prebytek)
pust(vrchol(Cislo, Vyska, 0), _, Pusteno, Pusteno, Sit, Cele, CeleOut):-
	upravPrebytek(Cislo, 0, Sit, Cele, CeleOut).

%Nasycene pousteni, hrana vypadne ze site rezerv (rez=0), pridame opacne orientovanou
pust(vrchol(Cislo, Vyska, Prebytek), [hrana(vrchol(CisloS, VyskaS, PrebytekS), Rezerva, _)| ZbS], 
     Pusteno, PustenoOut, Sit, Cele, CeleOut):-
	Prebytek\=0,
	VyskaS@<Vyska,
	Rezerva\=0,
	Prebytek@>=Rezerva,
	upravRezervu(Cislo, CisloS, 0, Cele, Cele1, prepis),
	upravRezervu(CisloS, Cislo, Rezerva, Cele1, Cele2, pricti),
	NovyPreb is PrebytekS+Rezerva,
	upravPrebytek(CisloS, NovyPreb, Sit, Cele2, Cele3),
	prictiTok(Cislo, CisloS, Rezerva, Cele3, Cele4),
	Zbylo is Prebytek-Rezerva,
	pust(vrchol(Cislo, Vyska, Zbylo), ZbS, true, PustenoOut, Sit, Cele4, CeleOut).

%Nenasycene pousteni zmeni se rezervy hran v obou smerech, v dalsim kroku rekurze skonci
pust(vrchol(Cislo, Vyska, Prebytek), [hrana(vrchol(CisloS, VyskaS, PrebytekS), Rezerva, _)| ZbS], 
     Pusteno, PustenoOut, Sit, Cele, CeleOut):-
	Prebytek\=0,
	VyskaS@<Vyska,
	Rezerva\=0,
	Prebytek@<Rezerva,
	ZbylaR is Rezerva-Prebytek,
	upravRezervu(Cislo, CisloS, ZbylaR, Cele, Cele1, prepis),
	upravRezervu(CisloS, Cislo, Prebytek, Cele1, Cele2, pricti),
	NovyPreb is PrebytekS+Prebytek,
	upravPrebytek(CisloS, NovyPreb, Sit, Cele2, Cele3),
	prictiTok(Cislo, CisloS, Prebytek, Cele3, Cele4),
	pust(vrchol(Cislo, Vyska, 0), ZbS, true, PustenoOut, Sit, Cele4, CeleOut).

%--

%Prepise nebo pricte k rezerve hrany zacinajici ve vrcholu CisloVrch, koncici v CisloS danou rezervu
upravRezervu(_,_,_,[],[], _).
upravRezervu(CisloVrch, CisloS, RezervaN,
             [vrchol(CisloV, VyskaV, PrebytekV)-Hrany|Zb], 
             [vrchol(CisloV, VyskaV, PrebytekV)-HranyOut|ZbOut], Pricist):-
	(CisloVrch==CisloV -> zpracujHrany(CisloS, RezervaN, Hrany, HranyOut, Pricist);
	HranyOut=Hrany),
	upravRezervu(CisloVrch, CisloS, RezervaN, Zb, ZbOut, Pricist).

%Pomocny predikat pro upravRezervu.. prochazi hrany vychazejici z daneho vrcholu a upravi rezervu
zpracujHrany(_,_,[],[],_).
zpracujHrany(Cislo, RezervaN, [hrana(vrchol(CisloS, VyskaS, PrebytekS), RezervaS, Tok)|Zb],
             [hrana(vrchol(CisloS, VyskaS, PrebytekS), RezervaOut, Tok)| ZbOut], Pricist):-
	(Cislo==CisloS -> 
		(Pricist==prepis -> RezervaOut=RezervaN;
		RezervaOut is RezervaS + RezervaN),
		ZbOut=Zb;
	RezervaOut=RezervaS,
	zpracujHrany(Cislo, RezervaN, Zb, ZbOut, Pricist)).


prictiTok(_,_,_,[],[]).
prictiTok(CisloVrch, CisloS, RezervaN,
             [vrchol(CisloV, VyskaV, PrebytekV)-Hrany|Zb], 
             [vrchol(CisloV, VyskaV, PrebytekV)-HranyOut|ZbOut]):-
	(CisloVrch==CisloV -> zpracujTokHrany(CisloS, RezervaN, Hrany, HranyOut);
	HranyOut=Hrany),
	prictiTok(CisloVrch, CisloS, RezervaN, Zb, ZbOut).


zpracujTokHrany(_,_,[],[]).
zpracujTokHrany(Cislo, Tok, [hrana(vrchol(CisloS, VyskaS, PrebytekS), Rezerva, TokS)|Zb],
             [hrana(vrchol(CisloS, VyskaS, PrebytekS), Rezerva, TokOut)| ZbOut]):-
	(Cislo==CisloS -> 
		TokOut is TokS + Tok,
		ZbOut=Zb;
	TokOut=TokS,
	zpracujTokHrany(Cislo, Tok, Zb, ZbOut)).

%--

%Upravi prebytek daneho vrcholu, pro Zdroj nebo Stok zachova 0.
upravPrebytek(Cislo, Preb, sit(CisloZ, CisloS), 
              Graf, 
              GrafOut):-
	(Cislo==CisloZ -> GrafOut=Graf;
	(Cislo==CisloS -> GrafOut=Graf;
	upravPrebytek1(Cislo, Preb, Graf, GrafOut))).	

%Upravi prebytek daneho vrcholu,
upravPrebytek1(_,_,[],[]).
upravPrebytek1(Cislo, Preb, [vrchol(CisloV, VyskaV, PrebytekV)-Nasl| Zb], 
               [vrchol(CisloV, VyskaV, PrebytekOut)-NaslOut|ZbOut]):-
	(Cislo==CisloV -> PrebytekOut=Preb;
	PrebytekOut=PrebytekV),
	upravNaslPrebytek(Cislo, Preb, Nasl, NaslOut),
	upravPrebytek1(Cislo, Preb, Zb, ZbOut).

upravNaslPrebytek(_,_,[],[]).
upravNaslPrebytek(Cislo, PrebN, [hrana(vrchol(CisloS, VyskaS, PrebytekS), RezervaS, Tok)|Zb],
                  [hrana(vrchol(CisloS, VyskaS, PrebytekOut), RezervaS, Tok)| ZbOut]):-
	(Cislo==CisloS -> PrebytekOut=PrebN;
	PrebytekOut=PrebytekS),
	upravNaslPrebytek(Cislo, PrebN, Zb, ZbOut).

%------------
% Zvedani
%------------

%Najde vrchol s kladnym prebytkem a ten zvedne o min{vi| vi je vyska souseda i} + 1

%Zajimaji nas jen vrcholy s prebytkem  (zdroj i stok ho maji nulovy...  (resp. +oo a -oo))
zvedej([vrchol(_,_,0)-_|Zb], Cele, Out):-
	zvedej(Zb, Cele, Out).

%Nalezli jsme vrchol pro zvednuti
zvedej([vrchol(Cislo, _, Prebytek)-Nasl|Zb], Cele, Out):-
	Prebytek\=0,
	zvedni(Cislo, infty, Nasl, Cele, Out).

%Zadny takovy vrchol neni
zvedej([], _, konec).

%--

%najdeme souseda s minimalni vyskou
%kazdy zvedany vrchol ma vzdy aspon jednoho souseda -> na konci nebude nikdy infty
zvedni(Vrchol, VTmp, [hrana(vrchol(_, VN, _), Rezerva,_)|Zb], Cele, Out):-     
	Rezerva\=0,
	(VTmp==infty -> VNext=VN;
	(VTmp@>VN    -> VNext=VN;
	VNext=VTmp)),
	zvedni(Vrchol, VNext, Zb, Cele, Out).

zvedni(Vrchol, VTmp, [hrana(vrchol(_, VN, _), 0,_)|Zb], Cele, Out):-     
	zvedni(Vrchol, VTmp, Zb, Cele, Out).

%nasemu vrcholu zmenime vysku na vysku souseda s nejmensi vyskou + 1
zvedni(Vrchol, VTmp, [], Cele, Out):-
	VNew is VTmp+1,
	zmenVysku(Vrchol, VNew, Cele, Out).

%--

zmenVysku(_,_,[],[]).
zmenVysku(Cislo, NovaVyska, [vrchol(CisloV, VyskaV, PrebytekV)-Nasl| Zb], 
          [vrchol(CisloV, VyskaOut, PrebytekV)-NaslOut|ZbOut]):-
	(Cislo==CisloV -> VyskaOut=NovaVyska;
	VyskaOut=VyskaV),
	zmenNaslVysku(Cislo, NovaVyska, Nasl, NaslOut),
	zmenVysku(Cislo, NovaVyska, Zb, ZbOut).

zmenNaslVysku(_,_,[],[]).
zmenNaslVysku(Cislo, VyskaN, [hrana(vrchol(CisloS, VyskaS, PrebytekS), RezervaS, Tok)|Zb],
                  [hrana(vrchol(CisloS, VyskaOut, PrebytekS), RezervaS, Tok)| ZbOut]):-
	(Cislo==CisloS -> VyskaOut=VyskaN;
	VyskaOut=VyskaS),
	zmenNaslVysku(Cislo, VyskaN, Zb, ZbOut).