"Max_flow je v Prologu napsaný program, který řeší úlohu nalezení maximálního toku v síti. Vstupem programu je síť, zadaná jako seznam hran a jejich kapacit v prologovské databázi; krom toho je potřeba definovat zdroj a spotřebič toku v síti. Po spočítání maximálního toku pro každou hranu jej program vypíše na standardní výstup.
V programu jsem použil Goldbergův algoritmus pro hledání max. toku, který má příznivou asymtotickou složitost a navíc není složitý na implementaci. Pro každý vrchol si v paměti navíc uchovává přebytek toku a "výšku", která je v počátečním kroku nastavena na 0 u všech vrcholů, kromě zdroje, kde je rovna počtu vrcholů v síti. Při inicializaci je navíc ze zdroje převeden do s ním hranami přímo spojených vrcholů přebytek rovný kapacitě těchto hran (takže je vždy ≥ max. toku ).
Hlavní struktura algoritmu vypadá přibližně takto:Dokud existuje vnitřní vrchol sítě s kladným přebytkem (v): pokud existuje hrana (e) vedoucí z vrcholu v do w (nebo z w do v), přes kterou lze převést přebytek, a zároveň výška(v) > výška(w): převeď (max. možný) přebytek z v do w po hraně e. (tj. změní (zvětší/zmenší, podle skutečného směru hrany) tok hranou e). jinak zvedni vrchol v o 1.
V době zastavení algoritmu dostáváme skutečně tok, protože žádný vnitřní vrchol nemá kladný přebytek. Pro každou hranu e=(v,w) nebo (w,v) platí, že je-li možné po ní převést přebytek z v do w, musí být výška(v) ≤ 1 + výška(w). ( platí po inicializaci, algoritmus toto neporušuje - je-li v výš než w a hranou lze převést přebytek, vrchol v nezvedá; přebytek nikdy nepřevádí do vrcholu s větší výškou). Proto je získaný tok skutečně maximální (v okamžiku skončení algoritmu je zdroj ve výšce N (počet vrcholů v síti) a spotřebič ve výšce 0 ( algoritmus mění výšku jen vnitřním vrcholům). Každá cesta ze zdroje do spotřebiče může mít max. délku n-1 vrcholů, proto musí min. na jedné hraně překonávat výšk. rozdíl ≥ 2 - tato hrana tedy nesmí mít žádnou rezervu toku - tok touto hranou už nelze zlepšit.
Při konst. době přístupu k jednotl. vrcholům i hranám má Goldbergův algoritmus asymptotickou časovou složitost O( N2 * M ), kde N je počet vrcholů a M počet hran. V mém zápočtovém programu je v průběhu výpočtu ale graf reprezentován v paměti v seznamech, takže vyhledání hrany může zabrat čas až O(M), výsledná časová složitost je tedy vyšší. Pro zjednodušení práce při převádění přebytků (odpadá nutnost znovu pro převádění vyhledávat zdrojový i cílový vrchol v seznamu) místo výšky vrcholů program v paměti uchovává pro každou hranu rozdíl výšky.
Hlavní predikát - max_flow - provádí celý výpočet. Při něm nejprve získá seznam vrcholů (který v databázi - reprezentaci sítě na vstupu není) - pomocí predikátu vrcholy; potom provede inicializaci - přidání přebytku vrcholů a rozdílu výšky a provedení úvodního kroku - zvednutí zdroje o N a převedení přebytků do vrcholů s ním sousedících. Potom vyvolá hlavní část Goldbergova algoritmu - predikát goldberg, který rekurzivně volá sám sebe, dokud je možné najít vnitřní vrchol s kladným přebytkem a provádí převedení přebytku, resp. zvednutí vrcholů; pokud to už není možné, skončí (uspěje). Nakonec program vypíše výsledný tok každou hranou - write_flow.
Po dobu výpočtu je aktuální stav grafu uchováván v seznamech vrcholů s přebytkem a hran s aktuálním tokem. Predikát goldberg pro svou práci používá několik pomocných predikátů - najdi_vdelta, který vrací vrchol s kladným přebytkem, pokud takový existuje, jinak neuspěje a najdi_hranu, zjišťující, pro tento vrchol existuje hrana, po které je možné přebytek převést. Na základě úspěchu nebo neúspěchu najdi_hranu se volá buď preved_delta, který vrátí seznam vrcholů s převedeným přebytkem a akt. tok použitou hranou, nebo predikát zvedni_vrchol, který zvětší výšku zadaného vrcholu s přebytkem - vrátí seznam hran s upravenými rozdíly výšky ovlivněných hran. Většina těchto hlavních predikátů navíc používá některé pomocné, jejichž použití je vysvětleno v komentářích kódu programu.
Vstupní data musí být reprezentována prologovskou databází - pro každou hranu v síti musí být v databázi predikát "hrana( Z, Do, Kapacita).", kde Z označuje číslo/identifikátor zdrojového vrcholu, Do označuje cílový vrchol hrany a Kapacita (konkrétně, číselně) kapacitu. Navíc musí být ve vstupní databázi (jednoznačně) definovány predikáty "zdroj( Z )." a "stok( S ).", kde Z je identifikátor zdroje a S identifikátor spotřebiče.
Uživatel tak po spuštění interpretu Prologu přidá celou síť do vnitřní databáze ( např. "příkazem consult( sit ).", jsou-li údaje o síti umístěny v souboru "sit.pl" v aktuálním adresáři). Navíc je potřeba do vnitřní databáze přidat samotný program ( "consult( max_flow )." ). Potom po zavolání hlavního predikátu - "max_flow." program spočítá maximální tok pro každou hranu a vypíše ho na standardní výstup (typicky obrazovka) ve formátu "Z->Do : Tok" (pro každou hranu, Z je identifikátor zdrojového vrcholu, Do cílového a Tok označuje vypočtenou velikost toku hranou).