Mosty w grafie - Haskell

Zbliża się powrót do szkoły więc trzeba powrócić do implementowania algorytmów. Jako projekt do wykonania dostałem napisanie algorytmu znajdującego mosty w grafie i działającego w czasie O(n+m), gzie n to liczba wierzchołków, a m to liczba krawędzi. Moje upodobania na szczęście się przez święta nie zmieniły więc napisałem to w Haskellu.

Algorytm znajdowania mostów wykorzystuje algorytm DFS. Zmiany są niewielkie, a mianowicie:

• przeglądając dany wierzchołek nadajemy mu od razu kolejny numer,
• nadajemy mu także początkową wartość low taką samą jak numer wierzchołka,
• dalej postępujemy jak w algorytmie DFS, czyli przeglądamy wszystkie sąsiadujące wierzchołki i jeżeli są nieodwiedzone to wrzucamy je na stos po czym wywołujemy procedurę rekurencyjnie z nowym stosem,
• wracając z rekurencji sprawdzamy wszystkie sąsiadujące wierzchołki, różne od tego, z którego przyszliśmy (czyli różne od ojca) i jeżeli sąsiad był odwiedzony i ma wartość low mniejszą od wierzchołka, w którym jesteśmy to zmieniamy naszą wartość low na wartość tego sąsiada.

Po wykonaniu tej procedury, wierzchołki, które mają numer równy low tworzą mosty.

Algorytm stanie się bardziej jasny jak przeanalizujemy kod:


Linie od 7 do 10 definiują nam typy danych, tak aby się nam lepiej programowało. Wierzchołek (Vertex) ma jak widać jakiś numer, jakąś listę krawędzi oraz jakąś wartość low. Krawędź to po prostu liczba, a most z kolei to para liczb oznaczająca parę wierzchołków tworzących jeden most.

Funkcja findBridges przyjmuje tablicę wierzchołków i zwraca listę mostów. Dalej treść funkcji czytamy od końca. Zatem wywołujemy funkcję dfsBridges dla pierwszego wierzchołka i naszej tablicy, która uzupełni nam podanym wyżej algorytmem wartości low oraz numery wierzchołków i zwróci te dane jako nową tablicę wierzchołków. Funkcja assocs zamieni nam tablicę na listę par typu (indeks, Vertex). Przeglądamy tą listę (foldr) i dla każdej pary sprawdzamy czy wartość low jest równa numerowi wierzchołka (czyli wyszukujemy wierzchołki tworzące mosty). Jeżeli nie to pomijamy ten wierzchołek. Natomiast jeżeli tak to bierzemy z listy sąsiadów tylko te wierzchołki, które mają wartość low różną od wartości low danego wierzchołka (filter). Dalej z tej listy tworzymy pary (mosty) w ten sposób: bierzemy numer naszego wierzchołka jako pierwszą liczbę w parze oraz dany element uzyskanej przed chwilą listy jako drugą liczbę (zip). Na koniec zostaje nam dołączenie tej listy do listy już uzyskanej.

Funkcja dfsBridges przyjmuje "stos" (w naszym przypadku po prostu listę) indeksów wierzchołków, ich tablicę oraz aktualny numer do przydzielenia. Zwraca natomiast uzupełnioną tablicę wierzchołków o numer i wartość low. Tą funkcję zaczynamy czytać od where. Na początku inicjalizujemy wartości naszego wierzchołka czyli przydzielamy mu numer oraz low równy aktualnemu numerowi - wartość d. Odbywa się to w ten sposób, że tworzymy nową tablicę wierzchołków (initArr), która zawiera te same dane za wyjątkiem naszego wierzchołka (//). Dalej obliczamy nowy "stos" przeglądając sąsiadów aktualnego wierzchołka i jeżeli któryś z nich nie był jeszcze odwiedzony (czyli ma numer większy niż -1) to wrzucamy go na koniec listy.

Kolejnym krokiem jest wywołanie naszej funkcji rekurencyjnie z nowym "stosem" i nową tablicą oraz kolejnym numerem. Jak przypadkiem skończy się nam "stos" (czyli lista będzie pusta, czyli wszystkie wierzchołki zostały odwiedzone) to zwracamy uzyskaną tablicę wierzchołków. Wracając z rekurencji przeglądamy sąsiadów naszego wierzchołka ale z nowo uzyskanej tablicy. Dalej jest już jak w algorytmie czyli jak któryś z sąsiadów był odwiedzony i nie jest to wierzchołek, z którego przyszliśmy oraz ma mniejszą wartość low to bierzemy jego wartość low. Na koniec zmieniamy tablicę tak aby nasz wierzchołek uzyskał tą nową wartość low i ją zwracamy.

Jeżeli ktoś jeszcze nie za bardzo rozumie co to jest ta wartość low to w skrócie można powiedzieć, że jeżeli napotkamy cykl w grafie to wszystkim wierzchołkom w tym cyklu nadajemy jednakową wartość low (obrazowo można powiedzieć, że kolorujemy cykle w grafie).

To właściwie wszystko. Czekam na komentarze.