Dokumentace - test dvousouvislosi grafu

download

Specifikace:

Program má za úkol pro zadaný graf, otestovat, zda je graf dvousouvislý (tedy po odebraní libovolného vrcholu graf zůstane souvislý). Výstupem programu je pak graf rozdělený na maximální komponenty dvousouvislosti a případně artikulace (má-li smysl je uvažovat - tj. graf je alespoň souvislý).

Vstup:

Vsupem pro program je seznam vrcholů. Vrchol je struktura v(označení_vrcholu, [seznam_sousedů]). Graf je neorientovaný.

Algoritmus:

Základem algoritmu je DFS, tedy procházení grafu do hloubky. Počínaje libovolným prvkem procházíme postupně jeho syny, rekurzivně. Při návštěvě daného vrcholu, určíme čas jeho návštěvy D (ten roste s vzrůstajícím počtem vrcholů), a Low. Low spočteme, jako min(D,D[všech sousedů]). Při návratu do vrcholu (navštívili jsme jeho syna a chystáme se na dalšího) se Low upraví ještě jednou Low:=min(Low,Low[syna]). Všechny údaje jsou pak připraveny.

Mimo všechny početní operace algoritmus pracuje se zásobníkem hran. Vždy při průchodu hranou z vrcholu i do vrcholu j, přidáme hranu do zásobníku. Ve vrcholu j pak přidáme ještě všechny zpětné hrany.

Aritkulace se algoritmu prozradí tak, že její D (čas navštívení) je menší než Low některého ze synů. To zda-li je vrchol artikulací testujeme při návratu ze syna j. Pokud artikulací vrchol i je, pak maximální dvousouvislou komponentu, kterou ohraničuje získáme z hran na zásobníku - jsou to všechny až po hranu (i,j). Ty ze zásobníku algoritmus vyjme a pokračuje v prohledávání grafu.

Obvykle se výpis komponent a artikulací provádí průběžně při prohledávání grafu. Algoritmus programu obvykle pracuje se složitostí O(m+n) vůči počtu hran m a počtu vrcholů grafu n. Toho se mi nepodařilo dosáhnout.

Implementace a datové struktury

Datové struktury: program jako takový zpracovává graf a určuje jeho další vlastnosti. V programu jsem proto využil seznamu vrcholů s jednotlivými parametry. Pro určení DFS stromu tak nejprve vzniká v(označení,otec,[synové],[všechny_hrany]), návrh samozřejmě mohl být lepší (občas pracuji s rozdílovým seznamem Hrany-Potomci, což bylo možné zjednodušit implementací). Další datová struktura tento graf obohacuje o D a Low, hodnoty počítané algoritmem.
Mimo uvedené implementace grafu, jsem v programu využil další dílčí struktury - zásobník hran, seznam komponent grafu.

Procedury programu: Program obsahuje 27 klauzulí. Hlavní procedurou programu je art(+graf,-artikulace,-komponenty). Ta rozděluje úkol na inicializaci - inicializuj(+graf,-inicializovaný graf) a vyhodnocení artikuluj(+vrchol,+Graf,+zásobník_hran,-zásobník_hran,-seznam artikulací,-seznam komponent). Navíc zkontroluje, zda je zadaný graf souvislý a tedy zda má smysl uvádět artikulace (ta není pro nesouvislý graf definována), v případě nesouvislosti grafu vrací místo seznamu artikulací [nesouvisly_graf].

Inicializace je rozdělena na vygenerování průchodu grafu dfs(+graf,-uspořádání) a ohodnocení vygenerovaného grafu hodnotami Low a D - ini_first(+graf,-graf ohodnocený). ini_first dosává poslouponst vrcholů a podle této posloupnosti vypočítává Low a D pomocí inic_vrchol přesně podle algoritmu (jedinný rozdíl je, generování v závislosti na předloženém seznamu - ne přímo při tvorbě seznamu). Další zajímavosti v inicializaci nejsou (více viz zdrojový kód).

Vyhodnocení oproti inicializaci je už více zajímavé (možná proto, že se systém v průběhu vývoje několikrát změníl). Vyhodnocení se sestává ze dvou hlavních procedur artikuluj(...) (stará se o jeden vrchol a artikuluj_vrcholy(...) (jež rozvíjí jeho potomky), tyto procedury s sebou nesou zásobník hran a generují postupně podle spočtených hodnot artikulace a jednotlivé komponenty dvousouvislosti. V každém vrcholu navšíveném artikuluj se proto vygenerují hrany do zásobníku a postupně se prochází jednotliví synové vrcholu, při návratu z každého syna se vrchol otestuje a případně se vygeneruje potřebná artikulace/komponenta. Právě generování hran do zásobníku zásobník(...) pracuje s rozdílovým seznamem potomků a všech hran vrcholu (tj. hrany z vrcholu zpětné a hrana otec-vrchol). Více opět ve zdrojovém kódu.

Možnosti programu

Program má "zřejmě" kvadratickou složitost v počtu hrany+vrcholy. Testován byl pouze na grafech do velikosti 20 vrcholů a k*n hran. Bez problémů. Vstup/výstup z/do souboru netestován nepoužíván. Několik testových grafů je na začátku zdrojového kódu programu.
1: [v(a,[b,c,d]),v(b,[a,d]),v(c,[a,d]),v(d,[a,c,b]),v(e,[])] 2: [v(a,[]),v(b,[d]),v(c,[]),v(d,[]),v(e,[])] 3: [v(a,[b]),v(b,[a,c,e,f]),v(c,[b,d]),v(d,[c]),v(e,[b]),v(f,[b])] 4: [v(a,[b]),v(b,[d]),v(c,[f,g]),v(d,[b,e,h]),v(e,[d,f,l]),v(f,[c,e]),v(g,[c,h]),v(h,[d,g,i,j]),v(i,[h,l]),v(j,[h]),v(l,[e,i])] 5: [v(a,[b,c]),v(b,[a,c]),v(c,[a,b,d,e]),v(d,[c,e]),v(e,[c,d])] 6: [v(a,[b,c]),v(b,[a,c]),v(c,[a,b,d]),v(d,[c,e,f]),v(e,[d,f]),v(f,[d,e])] 7: [v(a,[b]),v(b,[a]),v(c,[d]),v(d,[c]),v(e,[f]),v(f,[e])] 8: [v(a,[b,d,f,h]),v(b,[a,c]),v(c,[b]),v(d,[a,e]),v(e,[d]),v(f,[a,g]),v(g,[f]),v(h,[a,i]),v(i,[h])]

Nedodělky

Optimalizace.