open PMap

(** wyjatek rzucany przez [topol] gdy zaleznosci sa cykliczne *)
exception Cykliczne

(* funkcja pomocnicza do folda przy tworzeniu grafu
w - wierzchołek *)
let tworz_graf graf (w, sasiedzi) =
  if not (mem w graf) then add w sasiedzi graf else
  (* dodajemy nowych sąsiadów do już istniejących *)
  let dotychczasowi_sasiedzi = find w graf in
  add w (dotychczasowi_sasiedzi @ sasiedzi) graf

(** Dla danej listy [(a_1,[a_11;...;a_1n]); ...; (a_m,[a_m1;...;a_mk])]
    zwraca liste, na ktorej kazdy z elementow a_i oraz a_ij wystepuje
    dokladnie raz i ktora jest uporzadktowana w taki sposob, ze kazdy
    element a_i jest przed kazdym z elementow a_i1 ... a_il *)
let topol lista_sasiedztwa =
  if lista_sasiedztwa = [] then [] else
  (* mapa, która przechowuje listę sąsiadów każdego wierzchołka *)
  let graf = List.fold_left tworz_graf empty lista_sasiedztwa in
  (* lista zawierająca pierwsze elementy z par z listy lista_sasiedztwa *)
  let wierzcholki_poczatkowe =
    List.fold_left (fun l (w, sasiedzi) -> w :: l) [] lista_sasiedztwa in
  (* funkcja pomocnicza służąca do przetworzenia wierzchołków i zwrócenia
    odpowiedniego wyniku
    stan odwiedzenia:
    - gdy nie istnieje dowiązanie do jakiegoś wierzchołka to nie zaczął on być
      przetwarzany
    - 1 - wierzchołek jest w trakcie przetwarzania
    - 2 - wierzchołek jest przetworzony *)
  let rec dfs (wynik, stan_odwiedzenia) wierzcholek =
    (* sprawdzenie czy wierzchołek zaczął być przetwarzany *)
    if not (mem wierzcholek stan_odwiedzenia)
    then
      (* aktualizacja stanu wierzchołka *)
      let stan_odw1 = add wierzcholek 1 stan_odwiedzenia in
      (* gdy wierzchołek ma jakichkolwiek sąsiadów to wywoływana jest dla nich
      funkcja dfs i zwracana jest para postaci (stan_odwiedzenia, wynik),
      gdy nie ma tych sąsiadów zwracana jest para *)
      if mem wierzcholek graf
      then
        (* (stan_odw2, wyn2) - pomocnicza para przechowująca wynik zwracany
        przez folda *)
        let (wyn2, stan_odw2) = List.fold_left dfs (wynik, stan_odw1)
          (find wierzcholek graf) in
        (wierzcholek :: wyn2, add wierzcholek 2 stan_odw2)
      else (wierzcholek :: wynik, add wierzcholek 2 stan_odw1)
    (* gdy w funkcja dfs zostaje wywołana dla już przetwarzanego wierzchołka
    (takiego, że jego stan odwiedzenia jest równy 1) to znaczy, że w grafie jest
    cykl, więc zostaje podniesiony wyjątek *)
    else if (find wierzcholek stan_odwiedzenia) = 1 then raise Cykliczne else
    (* dany wierzchołek został już przetworzony, więc zostaje zwrócony wynik*)
      (wynik, stan_odwiedzenia)
  in
  (* wywołanie funkcji dfs dla wszystkich wierzchołków, które mają sąsiadów
  i zwrócenie wyniku *)
  fst(List.fold_left dfs ([], empty) wierzcholki_poczatkowe)