Topologiczny sort w OCaml

Question

Próbuję napisać sortowanie topologiczne w ocaml, ale jestem początkującym (w OCaml & algorytmów wykresów) i nie mogę zrobić tego sam.

Łatwiej mi myśleć o sortowaniu topologicznym na przykład w C++ (i jest dużo przykładów sortowania topologicznego w C++ w Internecie), ale chcę się czegoś nowego nauczyć. Co więcej, znalazłem kilka przykładów sortowania topologicznego zapisanych w OCaml, ale nie rozumiem ich, szczerze mówiąc.

Powiedzmy mam listę (int * int list) list, na przykład:

myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;

a to oznacza, że ​​trzeba "zrobić" zadanie 1 przed zadaniem 2 zadaniem 4 przed zadaniami 3 i 1 etc.

myślę, że wyjście na tej liście powinny być:

[8; 5; 6; 7; 4; 3; 1; 2]

(choć nie jestem pewien, bo po prostu się tym przykładem, więc jeśli się mylę, proszę mnie poprawić)

Również czytałem, że topologiczna sortowania nie działa cykli na wykresach, więc musi istnieć jakiś warunek dla cykli - gdy dany wykres ma cykl (y), wychodzimy na wyjątek (myślę, że to dobry pomysł).

AFAIK, potrzebuję użyć DFS w algorytmie do sortowania topologicznego, którego (DFS) Nie wiem jak zaimplementować w OCaml (Rozumiem główny pomysł, ale nie odczuwam czuję się, jak to działa OCaml/programowanie funkcjonalne).

Naprawdę doceniam Twoją pomoc w zrozumieniu tego pojęcia (mam na myśli sortowanie topologiczne, DFS w OCaml/programowaniu funkcjonalnym). Jeśli możesz, byłoby wspaniale, gdybyś pokazał mi przykładowe kody, ponieważ czytanie kodu jest (dla mnie) najlepszą metodą zrozumienia koncepcji algorytmu.

Wiem, że dla większości z Was to proste pytanie, ale mam nadzieję, że to nie powstrzyma Cię przed udzieleniem mi pomocy.

PS: Uczę się samodzielnie OCaml (jestem w liceum), więc nie mam solidnego zaplecza teoretycznego (ani w OCaml ani algorytmach). Zacząłem uczyć się OCaml, ponieważ chciałem zrozumieć koncepcję rekursji, a teraz ten język wydaje się interesujący, ponieważ tak naprawdę różni się od C++, więc wciąż próbuję nauczyć się czegoś nowego w OCaml.

Answer 1

[W przypadku, gdy nie wiem, termin, w którym piszę DAG poniżej Znaczy „skierowany graf acykliczny” lub kolekcji z/do krawędzi łączących wierzchołki takie, że nie ma cykli.]

Jednym ze sposobów na to jest rozszerzenie częściowego porządku (struktura DAG) w całkowitą kolejność (tak dla każdej pary różnych wierzchołków u i v, u jest następcą v lub odwrotnie). Następnie możesz sortować wierzchołki w kolejności: u występuje przed v, jeśli v jest następcą u.

Możesz zbudować swoje całkowite zamówienie, zaczynając od pustego wykresu i dodając jedną krawędź naraz z oryginalnego DAG. Oznacza to, że element (u, [v1; v2; ...; vn]) w oryginalnym DAG odpowiada krawędziom (u, v1), (u, v2), ..., (u, vn). Dla każdej takiej krawędzi (u, v) znajdź poprzedników P i następców S v z twojego całkowitego porządku. Następnie dodaj (p, s) do całkowitej kolejności dla wszystkich p w P U {u} i s w S U {v}.

TERAZ! Szybszym sposobem na to jest znalezienie korzenia w oryginalnym DAG (tj. Wierzchołku bez poprzedników) i wykonanie pierwszego wyszukiwania z tego korzenia, upewniając się, że nigdy nie odwiedzasz tego samego wierzchołka dwa razy. Za każdym razem, gdy cofasz się w swojej traversal, "wyprowadzasz" wierzchołek, z którego odchodzisz. W ten sposób skonstruujesz topologiczny rodzaj swojej DAG. Jeśli pozostały jakieś wierzchołki, spłucz je i powtarzaj, aż wszystkie się skończą.

Answer 2

Nie wiem OCaml, ale istnieje prosty algorytm z Wikipedia akredytowanym dla Kahna, z którego z powodzeniem korzystałem (transkrypcja do Pythona). Jest to dość proste, więc może mógłbyś przetłumaczyć je na OCaml. Oto ona:

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    insert n into L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    output error message (graph has at least one cycle) 
else 
    output message (proposed topologically sorted order: L) 

Answer 3

Powinieneś najpierw wypróbować DFS, jest to łatwiejsze i bardziej satysfakcjonujące.

Answer 4

Po pierwsze, należy pamiętać, że Objective Caml obsługuje styl programowania, który pomimo różnic składniowych jest dość podobny do C++, za pomocą mutowalnych struktur danych (odniesienia, tablice, tabele mieszania) i imperatywnych konstrukcji (pętli for i while , przypisanie zmiennych). Zakładam, że poniżej próbujesz napisać swój topologiczny rodzaj w idiomatycznym, czysto funkcjonalnym stylu.

Czyste funkcjonalne programowanie jest w większości deklaratywne: ta funkcja zastosowana do tej wartości to ta inna wartość. Właśnie dlatego prawa strona z let x = jest wyrażeniem (ocenia wartość) zamiast sekwencji działań, która używa return. Oczywiście pojawia się problem przy dostosowywaniu algorytmu, który jest zwykle opisywany jako seria kroków.

Na szczęście istnieje wzorzec (w rzeczywistości rodzina wzorów), który pozwala przedstawić reprezentatywne algorytmy w stylu funkcjonalnym, zmieniając "wartość X" na "zwracaj nowy obiekt, który jest identyczny ze starym , z wyjątkiem wartości X ".

Tradycyjny algorytm DFS polega na przejściu przez wykres, pamiętając, które elementy już zostały odwiedzone - ogólnie (aby nie odwiedzać ich więcej niż jeden raz) i aby uzyskać aktualną pozycję (aby można było wykryć cykle). Tak więc imperatywny stan algorytmu DFS składa się z bieżącego węzła, zestawu odwiedzanych węzłów i zestawu węzłów w bieżącej ścieżce. Wszystkie te dane będą musiały zostać dostarczone do wywołań rekurencyjnych, a wszelkie trwałe zmiany będą musiały być zwracane przez te same wywołania rekursywne.

Korzystanie strukturę wykres z powyżej, w połączeniu z reprezentacją listy dla dwóch zestawów (to prawie optymalny - Set byłoby lepszym wyborem tutaj), algorytm będzie wyglądać mniej więcej tak:

let dfs graph start_node = 
    let rec explore path visited node = 
    if List.mem node path then raise (CycleFound path) else 
    if List.mem node visited then visited else  
     let new_path = node :: path in 
     let edges = List.assoc node graph in 
     let visited = List.fold_left (explore new_path) visited edges in 
     node :: visited 
    in explore [] [] start_node 

Trzy ważne szczegóły powyżej: po pierwsze, DFS mówi, że skończyłeś eksplorować wszystkie dzieci danego węzła, powinieneś usunąć ten węzeł z listy "aktualnej ścieżki" i umieścić go na liście "odwiedzonych". Ponieważ używamy niezmiennych struktur danych, pierwszy krok jest niepotrzebny: jego jedynym celem było cofnięcie wstawienia węzła po rozpoczęciu eksploracji, a w naszej wersji lista new_path nie została zmodyfikowana przez wywołanie rekursywne do explore. Jest to przykład przypadku, w którym struktury danych funkcjonalnych są wygodniejsze w użyciu niż struktury wymagające. Kolejnym ważnym szczegółem jest użycie List.fold_left. Kiedy rozpoczęliśmy tworzenie stanu jawnego, zastąpiliśmy domyślne funkcje imperatywne typu -> unit jawnymi funkcjami typu -> state -> .. -> state (akceptujemy stan jako parametr, zwracamy nowy stan).Tak, imperatyw lista poszukiwania, który wyglądał tak:

f edge_1 ; f edge_2 ; f edge_3 

Teraz wygląda tak:

let state = f (f (f state edge_1) edge_2) edge_3) 

który jest dokładnie to, co List.fold_left f state [edge_1 ; edge_2 ; edge_3] robi. Tooting mój własny róg, ale mam a nice article about this here.

Trzeci punkt jest taki, że operacja "dodaj element do zestawu", gdy używasz list do reprezentowania zbiorów, jest napisana po prostu jako element :: set, ponieważ jest to operacja, która zwraca nowy zestaw (listę), który zawiera wszystkie elementy oryginalny zestaw wraz z nowym elementem. Pozostawia to oryginalny zestaw nietknięty (co jest dobre z powodów opisanych w kroku 1) przy użyciu stałej ilości pamięci (tworzy komórkę cons - prosta para głowa-ogon zawierająca odniesienie do elementu i odniesienie do zestawu): nie tylko masz możliwości cofania, ale robisz to bez dodatkowych kosztów.

Powyższy algorytm "wstawia" węzły do ​​visited rozpoczynając od liści eksploracji DFS, które w twoim przypadku reprezentują te węzły, które powinny być wykonane jako ostatnie. W skrócie, zwrócona lista jest sortowana topologicznie - ale może nie zawierać wszystkich elementów, ponieważ punkt początkowy może nie być jedynym elementem głównym (lub nawet być w ogóle elementem głównym). Jest tu więc dodatkowy etap przetwarzania, polegający na tym, że kolejny węzeł z wykresu zostanie odnaleziony, dopóki cały wykres nie zostanie zbadany.

Albo, innymi słowy, rozpoczynając poszukiwania nowego DFS z każdego węzła na wykresie, ale ignorując wszelkie węzły uprzednio zbadane - co jest równoważne prowadzenie listy odwiedzanych elementów z jednego DFS poszukiwań do następnego .

Korzystanie mały uszczypnąć do naszego poprzedniego algorytmu, to zajmuje tylko dwie linie:

let dfs graph visited start_node = 
    let rec explore path visited node = 
    if List.mem node path then raise (CycleFound path) else 
    if List.mem node visited then visited else  
     let new_path = node :: path in 
     let edges = List.assoc node graph in 
     let visited = List.fold_left (explore new_path) visited edges in 
     node :: visited 
    in explore [] visited start_node 

let toposort graph = 
    List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph 

Tweak polega na swobodnym rozmówcę o dfs określić listę odwiedzonych węzłów. Przenoszenie listy odwiedzonych węzłów podczas uruchamiania systemu plików DFS z każdego węzła odbywa się za pomocą List.fold_left dokładnie tak, jak poprzednio.

EDYCJA: oprócz typu wyjątku, nie ma tu nic, co ogranicza typ elementów na wykresie. Jednak wyjątek nie może być polimorficzny, więc masz dwa możliwe rozwiązania. Pierwszym z nich jest zrezygnować rzeczywiście powrocie żadnych danych wraz z wyjątkiem:

exception CycleFound 

... raise CycleFound ... 

ten powróci typ toposort powrotem do bardziej rodzajowe ('a * ('a list)) list -> 'a list.

Innym rozwiązaniem jest raczej zaawansowany OCaml: trzeba dokonać modułktóry zawiera wyjątek i sortowanie topologiczne polimorficzny w tym szczególnego rodzaju, jak następuje:

module type NODE = sig 
    type t 
end 

module type Topo = functor (Node:NODE) -> struct 
    exception CycleFound of Node.t list  
    let dfs ... 
    let sort ... 
end 

byłoby to uczynić typ Topo(Node).sort być (Node.t * (Node.t list)) list -> Node.t list, co oznacza, że ​​można rozwiązać każdy rodzaj chcesz definiując moduł węzła z tego typu:

type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve 

module Node = struct 
    type t = recipe 
end 

let graph = [ Wheat, [Eggs,Milk,Mix] ; 
       Milk, [Mix] ; 
       Eggs, [Mix] ; 
       Mix, [Cook] ; 
       Cook, [Serve] ; 
       Serve, [] ] 

module RecipeTopo = Topo(Node) 

let sorted = RecipeTopo.sort graph