Sortowanie topologiczne polega na rozszerzeniu skończonego częściowego porządku do porządku liniowego.
Mówiąc prościej, mając dany DAG (czyli graf skierowany bez cykli) należy przypisać wierzchołkom takie różne liczby naturalne (nadające kolejność tym wierzchołkom), żeby dla każdej krawędzi grafu jej źródło miało niższy numer niż jej cel.
Mówiąc jeszcze prościej, mając daną częściową informację o zależności, powiedzmy, czynności od siebie (np. buty wkładamy po skarpetkach, krawat po koszuli itp. ale kolejność wkładania skarpetek i koszuli może być dowolna) mamy wygenerować ścisłą kolejność wykonywania czynności (np. koszula, skarpetki, buty, krawat).
Konkretnie, należy zaprogramować implementację topol.ml załączonej specyfikacji topol.mli.
W implementacji można korzystać z modułu pMap (bardzo podobnego do pSet z poprzedniego zadania), którego specyfikacja i implementacja również są załączone. Wszystkie potrzebne pliki można także pobrać w postaci archiwum zip.
Termin oddania zadania ustala prowadzący — 2 tygodnie od ogłoszenia.
| Załącznik | Wielkość |
|---|---|
| wpf-4-topol.mli | 436 bajtów |
| wpf-4-pMap.mli | 3.39 KB |
| wpf-4-pMap.ml | 4.58 KB |
| wpf-4-topol.zip | 3.47 KB |