TOK V SÍTI - GOLDBERGŮV ALGORITMUS
==================================
(c) 2002 Petr Čermák <cermak01@seznam.cz>

	Síť je orientovaný vážený graf s dvěma označenými vrcholy - zdrojem a stokem. G=(V, E), z, s \in V, z != s, c: E -> R^{+}_{0}. Hodnotu c(e \in E) nazývame kapacitou hrany e. Tok v síti je zobrazení f: E->R^{+}_{0} splňující následující podmínky:
   (i)  \forall e \in E: 0 <= f(e) <= c(e)
  (ii)  \forall u \in V, u != z, s: sum_{x, xu \in E} f(xu) = sum_{x, ux \in E} f(ux)
Velikost toku je pak číslo w(f) = sum_{x, zx \in E} f(zx) - sum_{x, xz \in E} f(xz) (= sum_{x, xs \in E} f(xs) - sum_{x, sx \in E} f(sx) ). Nejčastější úlohou je pak hledání maximálního toku (s maximální w). Dalším potřebným pojmem je řez Ř \subset E: v G(V, U\Ř) neexistuje žádná orientovaná cesta ze z do s. Kapacitou (velikostí) řezu pak rozumíme c(Ř)=sum_{e \in Ř} c(e). V každé takovéto síti existuje maximální tok fM. Pro fM navíc platí, že w(fM)=c(Řm), kde Řm je řez s minimální velikostí. Program se zabývá pouze speciální množinou sítí s celočíselnými kapacitami. Platí, že pokud jsou všechny kapacity celočíselné, pak existuje celočíselný maximální tok. Na jeho nalezení existuje několik různých algoritmů většinou hledající vylepšující cestu (Ford-Fulkerson, Dinic, 3-Indové). Program však implementuje Goldbergův algoritmus který nehledá vylepšující cestu, ale pracuje na jiném, velmi jednoduchém principu.
	Goldbergův algoritmus pracuje s modifikovanou definicí toku a to tzv. vlnou, která připouští v každém vrcholu přebytek: sum_{x, xu \in E} f(xu) >= sum_{x, ux \in E} f(ux). Pokud však již nemáme v žádném vrcholu přebytek (kromě zdroje, který má +oo a stok -oo), je tento tok shodný s původní definicí. Pro každý vrchol budeme ještě udržovat informaci o výšce. Pracuje se se sítí rezerv, kde každá hrana e je ohodnocena číslem c(e) - f(e). Přidáme i hrany opačně orientované s nulovou kapacitou. Definujeme f(e)=-f(e opačná). Označíme r(e)=c(e)-f(e). Algoritmus pracuje v následujících krocích:
   (i)  Vstup - všechny vrcholy výšky nula, všude nulový přebytek.
  (ii)  Zvedni zdroj do výšky n, kde ne je počet vrcholů. A pusť hranami vycházejícími ze zdroje tok odpovídající jejich kapacitě.
 (iii)  Pokud existuje vrchol s kladným přebytkem a pokud existuje jeho nějaký soused s menší výškou a hrana mezi nimi je nenasycená (f(e)<c(e)), tak do něj pusť tok velikosti min(c(e)-f(e)=r(e), přebytek).
  (iv)  Krok (iii) opakuj dokud můžeš.
   (v)  Existuje-li vrchol v s kladným přebytkem, zvedni ho na výšku min{výška(u)| u je soused v}+1 a jdi na krok (iii).
  (vi)  Vydej výsledný tok.
	Program pracuje podle tohoto schematu. Jako reprezentaci grafu používá seznam následníků, neboť nejčastěji potřebuje získávat informace o sousedech daného vrcholu. Přístup k libovolnému sousedovi daného vrcholu je možný v čase O(N). Například procházení sousedů je rychlejší než u matice incidence (reprezentované v prologu seznamem seznamů).
	Na začátku sloučí program násobné hrany původního grafu. (Lépe se tak pracuje, neboť není třeba vědět, která hrana je ke které opačná).  Dále jsou ke všem hranám přidány opačně orientované s nulovou rezervou (lepší, než za běhu algoritmu přidávat a ubírat hrany podle aktuálních změn). Nyní již přistoupí program k vlastnímu algoritmu. Po jeho dokončení porovná graf s původním (po eliminaci násobných hran) a odstraní přidané hrany. V předposledním kroku porovná opět získaný graf s původním zadaným a rozdělí tok získaný ve sloučených násobných hranách do originálních násobných. Nakonec spočítá velikost toku.
	Vstup se zadává ve formě seznamu následníků (ve zdrojovém kódu označováno jako V/V formát) a dvojice čísel určující zdroj a stok. Seznam následníků má formát seznamu prvků typu číslo_vrcholu-seznam_hran, kde seznam_hran je seznam prvků typu číslo_souseda-kapacita hrany. Zdroj a stok se zadávají dvojicí sit(číslo_zdroje, číslo_stoku). Pro spuštění výpočtu se používá predikát run(Graf+, Síť+, Graf_s_tokem-, Velikost_toku). Výsledný graf s tokem má opět formát seznamu následníků jako vstup, jsou v něm však kapacity hran nahrazeny tokem na nich. Program neprovádí žádnou kontrolu zadaného grafu a tak předpokládá, že daný seznam bude reprezentovat orientovaný graf s nezáporným ohodnocením hran a dvojice čísel zdroj, stok budou dvě navzájem různá čísla vrcholů tohoto grafu. Seznam nemusí být nijak uspořádaný, třídění proběhne krátce po spuštění.
Příklad užití:
graf:
%     2--3 
%    /  / \
%   1   |  4
%    \ /  /
%     6--5      všechny kapacity: 10 krome 6-3: 1, hrany orientované zleva doprava.
run([1-[2-10,6-10], 2-[3-10], 3-[4-10], 4-[], 5-[4-10], 6-[3-1, 5-10]], sit(1, 4), Graf, Velikost).
	Tato implementace Goldbergova algoritmu má horší složitost, než algoritmus sám, neboť nemohu k libovolnému vrcholu přistoupit v konstantním čase (například udržováním seznamu vrcholů s kladným přebytkem jako ukazatelů na dané vrcholy v datové struktuře grafu). Jistá vylepšení je možno například udělat ve fázi pouštění - vhodně (topologicky) uspořádat graf sestávající pouze z vrcholů s přebytkem a přípustných hran (hrana v topol. usp. zleva klesající a s rezervou) a pouštění provádět zleva. Další možné vylepšení by mohl být jistý preprocessor grafu, který by odstranil nepotřebné komponenty souvislosti, hrany vycházející ze stoku a jiné.
	

TECHNICKÁ PŘÍLOHA
=================

* Popis některých predikátů, které by mohli najít uplatnění i v jiných úlohách.

elimNasobne(Graf+, Graf-)
Sloučí násobné hrany v jednu, která má kapacitu odpovídající součtu kapacit hran původních.

pridejOpHrany(Graf+, Graf-)
Přidá ke každé hraně hranu opačně orientovanou s kapacitou 0.

vynulujRezervy(Graf+, Graf-)
Vynuluje rezervy všech hran grafu.

slucGrafy(Graf1+, Graf2+, Graf-)
Sloučí grafy Graf1 a Graf2, vrcholy si musí odpovídat. 

obratGraf(Graf+, Graf-)
Změní orientace všech hran v grafu.

pridejDoSeznamu(Prihradka+, Cislo-Polozka+, Seznam+, Seznam-):-
Přidá do seznamu typu [Prihradka-[seznam polozek typu Cislo-Data]] danou položku.
Neexistuje-li takova prihradka, neuspeje.

seradNasl(Graf+, Graf-)
Setřídí seznamy následníků grafu.

quicksort(Seznam+,Seznam-)
Setřídí seznam typu klíč-položka.

Další popisy predikátů se nalézají přímo ve zdrojovém kódu.

* Reprezentace grafu, se kterou pracuje vlastní algoritmus.

Pro vlastní algoritmus je potřeba v grafu uchovat více informací, než v původním seznamu následníků. Jedná se hlavně o informace o výšce a přebytku vrcholů, které jsou navíc duplikovány i v seznamech následníků. Pro přehlednost byl zvolen následující formát využívající dva typy termů k pojmenování položek:
[vrchol-[hrana, hrana, hrana, ...], ...]
kde vrchol je term typu vrchol(Číslo_vrcholu, Výška, Přebytek) a hrana typu hrana(vrchol, Rezerva, Tok).
BYla tak zvýšena přehlednost zdrojového kódu (Je jasné, zda se prochází celý seznam (vrcholů), nebo seznam následníků daného vrcholu).

V/V formát byl ponechán ve standardním tvaru, neboť je úspornější a i vhodnější z hlediska kompatibility při použití tohoto programu jinými programy.

Predikáty pro převody mezi V/V formátem a vnitřním formátem:

v2muj(GrafVV+, GrafAlg-)
V/V formát ---> vnitřní reprezentace grafu

muj2v(GrafAlg+, GrafVV-)
naopak