Motto:
"Představte si, že byste celý život znali jenom jedno pohlaví, to kdybyste pak zjistili, že existuje i to druhé, mohl by to být docela šok... i když později by to pro vás možná bylo docela zabávné."
RNDr. Rudolf Kryl
Abych algoritmus lépe pochopil, napsal jsem napřed implementaci v čistém céčku. Kód není příliš názorný, je postaven na operacích se spojovými seznamy a pointery (občas dvojitými), ale relativně snadno jsem dosáhl časové složitosti O(MN). Pak jsem se hned pustil do implementace v Prologu. Docela mě zajímá srovnání: Bude to v Prologu kratší a přehlednější? Po přednášce by se zdálo že určitě, ale jaká je realita? Vzhůru do práce a uvidíme. Aby bylo srovnání spravedlivé, rozhodl jsem se, že implementace v Prologu musí běžet se stejnou asymptotickou složitostí (tedy O(MN). Bylo to závažné rozhodnutí, ale nepředbíhejme.
aneb "čínský film s japonskými titulky"
Nečekal jsem, že první srážka s Prologem proběhne tak brzy. Procházení grafu musí běžet v čase O(M), a je potřeba při něm nějak označovat vrcholy. Ale na to potřebuju 1) indexovat pole (najít vrchol) a 2) měnit hodnotu proměnných (označit a pak odznačit vrchol). Nic takového mi Prolog neumožňuje (označovat můžu jen svázáním volné proměnné, což je "na jedno použití"). Možná kdybych měl vrcholy v utříděném seznamu, pak by to běželo v O(MlogN)... Ne, tak brzo se nevzdám. A co třeba mít vrcholy přímo v databázi, a uvažovat že hledání v databázi je konstantní... Ne, to je podvod. Je jediné řešení: mít graf jako cyklickou strukturu. A hrany z vrcholu budou seznam sousedů - v němž budou přímo ti sousedé. Příklad (dva vrcholy spojené hranou):
graph([V1,V2]) :- edges(V1,[V2]), edges(V2,[V1]).
Použití takovéto struktury přináší několik pastí. Struktura se musí načítat pomocí consult. Prolog ji naštěstí dokáže vypsat (i když vyznat se v tom nedá, napsal jsem si vlastní funkci print_graph), a verze 5.4 ji dokáže i zkopírovat pomocí copy_term (verze 5.1 skončila se Segmentation Fault). Ale mě klasické kopírování nestačí. Potřebuji při něm odznačit označené vrcholy (tj. udělat z označení znovu volné proměnné). A to vše v O(M). Jak na to? Kopírování bude mít dvě fáze: napřed se k vrcholům vytvoří jejich "klony" (proměnná pro "klona" je součástí struktury vrcholu). A pak se vytvoří nový graf jako seznam klonů, kde se ke každému vrcholu přiřadí seznam sousedů vytvořený z klonů sousedů. Starý graf pak zanikne, pokud tedy Prolog používá normální garbage collector (a ne jen nějaké counted pointers).
aneb "Backtracking? děkuji, nechci."
Hledání volné střídavé cesty (predikát augmenting_path) je vlastně jen jednoduché prohledávání do hloubky. Abych se nazacyklil, označuji navštívené vrcholy (tím, že volnou proměnnou s něčím svážu a testuji jí pomocí var). Jen se musí jít po vrstvách: v sudé vrstvě (tj. sudé vzdálenosti od počátku) jdu nepárovou hranou, v liché párovou hranou. Pokud není vrchol v liché vrstvě spárovaný, vyhrál jsem a mám volnou střídavou cestu. Při návratu tedy přehodím párování hran na cestě (přičemž vrcholy se párují ve svých klonech - stávající spárování nemůžu měnit - a graf se pak okopíruje). Pokud hledání nedojde do volného vrcholu, selže a zkusí se další vrchol. To lze v Prologu napsat snadno, to za mě vlastně udělá sám. Nebo ne?
Je tu jistý háček. Tenhle postup by vždycky našel volnou střídavou cestu, pokud existuje! Prolog totiž bude backtrackovat, a přitom rušit i označení vrcholů. Sice se (možná) nezacyklí, ale dostane se na exponenciální složitost.
Řešení je logické: zakázat backtracking pomocí řezů (nakonec stačil jen jeden řez). A předávat jestli se našla VSC přes návratové hodnoty (přidaný parametr predikátu). A vždy napřed zavolat procházení a pak tuto hodnotu testovat (dvě možnosti pomocí ';'). A výsledek je pak totéž jako řešení v jazyce C.
aneb "Krok stranou"
Pokusil jsem se implementovat kontrakci grafu "poctivě" podobně jako v C, ale to jsem nakonec musel vzdát (kontrakci jsem vymyslel, ale dekontrakce v O(M) se už ukázala nad mé síly). Zkusil jsem tedy jiný přístup: k vrcholu se bude zaznamenávat, do kterého vrcholu byl zkontrahován (přičemž se zde dosadí přímo samotný vrchol). Snadné a rychlé řešení, dekontrakce je jen projití a nahrazení odkazů na vrchol opět volnými proměnnými (v klonech vrcholů, samozřejmě, hodnoty nelze měnit). Nebo je tu zase háček?
Bohužel. Co když se vrchol A zkontrahuje do B, pak B do C atd.? Pak vznikne řetězec délky něco jako O(N), a sbohem čase O(MN). Naštěstí to lze snadno zapatchovat: vypočítají se "zkratky", vrcholy, kam je daný vrcholu skutečně zkontrahován. Pokud je A zkontrahováno do B a B už nikam, bude tato "zkratka" vrchol B. Jinak bude "zkratka" vrcholu A totéž co zkratka B. Ta sice ještě nemusí být vypočtena, ale to v Prologu nevadí, prostě se sváží dvě proměnné. To je po dlouhé době kladný bod pro Prolog. Vlastně možná první kladný bod.
Pořád zbývá jedna komplikace: takovouto kontrakcí mohou vzniknout vícenásobné hrany. To naštěstí nevadí: počet hran se nezvýší, takže složitost neutrpí, a při procházení se označují vrcholy, takže z vícenásobných hran se vždy projde nejvýše jedna.
Ještě je nutno dodat, že při dekontrakci se musí přesměrovat spárování vrcholů: Je-li pár (A,Z) kde Z je vrchol vzniklý kontrakcí, bude spárován A s vrcholem na kružnici, do něhož vede z A hrana (libovolným, je-li takových více). Hrany na kružnici se pak spárují střídavě.
Málem bych zapomněl: ještě je nutno zmínit nalezení liché kružnice (tzv. květu), která se má zkontrahovat (predikát odd_circle). Procházení je obdobné hledání VSC, pouze je nutné vrcholy značit různě podle vrstvy (abychom poznali skutečně lichou kružnici). A také se mění cílová podmínka (nalezení označeného vrcholu na sudé vrstvě).
Zajímavá je též otázka, jakou bude mít tento postup paměťovou složitost. To lze u Prologu odhadovat docela těžko, ale pokusím se. Nejlepší odhad, který jsem vymyslel je O(N2). Původní graf zůstáva stejný (jen se možná přiřadí k některému vrcholu kam je zkontrahován), ale do grafu přibývá nový vrchol, který může mít teoreticky až N-1 hran. A kontrakcí se může provést až O(N). To odpovídá paměťové složitosti řešení v C.
aneb "Tudy ne, přátelé!"
Celé dílo je u konce. Hledání maximálního párování (maximum_matching) je již jen opakováné hledání VSC. Pokud jsme ji nenašli (což ovšem neznamená, že neexistuje), zkusíme najít lichou kružnici, zkontrahovat, rekurzivně se zavolat a pak kružnici dekontrahovat. Při každé úpravě grafu se graf musí kopírovat, protože nelze měnit již unifikované proměnné.
Výsledný program je o 50% delší než implementace v Céčku. A je i podle mého názoru méně přehledný a přímočarý. To mě trochu zklamalo, a bohužel potvrdilo můj názor, že Prolog je jazyk, v němž lze jednoduše pomocí backtrackingu vyřešit jistou třídu problémů (typu symbolická integrace). Cokoli jiného je docela souboj - jako v tomto případě.
Edmondsův algoritmus tak jak byl na přednášce
0) Inicializace: M (množina hran v párování) je prázdná 1) Vytvořím Edmondsův lesík F: 1a) Do F přidám všechny volné vrcholy, ty tvoří hladinu H0, k := 0 1b) Přidám hladinu H[2k+1]: všechny vrcholy spojené nepárovací hranou s vrcholy H[2k] (včetně těchto hran) 1c) Přidám hladinu H[2k+2]: všechny vrcholy spojené párovací hranou s vrcholy H[2k+1] (včetně těchto hran) 1d) k := k + 2, pokud byly přidány nějaké hrany, pokračuji 1b) 2) Pokud existuje hrana mezi sudými hladinami dvou různých stromů Edmondsova lesíku, existuje v grafu VSC. Zaměním tedy párovací a nepárovací hrany na cestě a pokračuji 1) 3) Pokud existuje hrana mezi sudými hladinami v jednom stromě, je v grafu lichá kružnice. Tuto kružnici zkontrahuji do vrcholu, z M odstraním hrany kružnice a pokračuji 1) na zkontrahovaný graf. 4) M je maximální párování