U2: Robinson Crusoe ztroskotal

Když Robinson Crusoe ztroskotal, nevěděl, zda se nachází na ostrově nebo na pevnině. Jenom postupně poznával své nejprve bližší a pak vzdálenější okolí a konstruoval mapu. Robinsonova mapa je dána jako neorientovaný graf. Sestává z jednotlivých vrcholů, které reprezentují konkrétní místa na ostrově. Každý vrchol nese identifikační údaje – název, pozici, barvu a také seznam sousedících vrcholů.

Robinson sestavil mapu, zaznačil na ní svoji pozici a algoritmem prohledávání do hloubky zjistil, že se nachází na ostrově. Aby optimalizoval pohyb po ostrově, využil algoritmus prohledávání do šířky a našel nejkratší cesty mezi význačnými body ostrova. Když poznal ostrov, na němž se nacházel, rozhodl se prozkoumat okolí. Pomocí člunu a náročných výprav zmapoval okolí ostrova a také zde vyznačil jednotlivé ostrovy a našel vhodné cesty. Výsledek jeho práce lze vidět na obrázku.

Na obrázku je vidět několik ostrovů – červený, zelený, oranžový, růžový, bleděmodrý… Na oranžovém ostrově je světle zeleně vyznačena cesta mezi vrcholy 26 a 46. Ostrovy 1, 4, 6, 34 apod. obsahují pouze jeden vrchol a jsou označeny černou barvou (nejsou obarveny).

Kromě ostrovů a cest na ostrovech Robinsona zajímají také oblasti, které jsou z jeho dočasného domova dostupné za jeden den chůze. Tyto oblasti představují jakousi ohraničenou oblast se všemi vrcholy, které jsou od jeho domova vzdálené méně než daná vzdálenost.

Na obrázku jsou světle zelenou barvou znázorněny body na oranžovém ostrově vzdáleny od vrcholu 75 maximálně 3 (délka cesty je menší nebo rovna 3).

• Definici třídy v jazyce C++
• Definici konstruktorů třídy
• Přístup k privátním proměnným třídy
• Použití objektů třídy
• Definici vnořené třídy
• Definici grafu jako množiny vrcholů s jistými vlastnostmi
• Algoritmus prohledávání do hloubky k nalezení komponent grafu
• Algoritmus prohledávání do šířky k nalezení cesty v grafu

Definice tříd a seznam metod, které musíte implementovat najdete v hlavičce crusoe.hpp. Co jednotlivé metody mají dělat pak najdete v téže hlavičce, ve formátu Doxygen komentářů.

Archiv s testy, hlavičkou crusoe.hpp a CMakeLists.txt najdete zde.

Jeden nebo více .cpp souborů (obvykle crusoe.cpp), které implementují funkce deklarované v souboru crusoe.hpp tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor crusoe.hpp neměňte. Zejména doporučujeme neměnit operátory pro zápis do proudu. Ty umožˇují znázornit testovanou situaci - viz obrázek image.svg, který je vytvářen s každým testem.

Řešení je koncipováno do několika tříd. Třída vertex reprezentuje jeden vrchol grafu. Ten je určen názvem, souřadnicemi [x, y] na mapě a barvou. Kromě toho nese vrchol – ne zcela typicky – informace o svých sousedech. Každý soused tvoří s daným vrcholem hranu, proto je ke každému sousedovi přeřazena barva odpovídající hrany.

Třída graph nese informace o jednotlivých vrcholech grafu. Ty jsou uloženy ve struktuře std::vector. Index daného vrcholu ve vektoru reprezentuje číslo vrcholu a ve využíváno při definici sousedů vrcholu. Toto je možné proto, že vrcholy z vektoru nemažeme a jejich index se proto nemění.

Nejprve je potřeba implementovat základní funkcionality obou tříd (stage1).

Nejobtížnější částí úkolu je z algoritmického hlediska implementace algoritmů prohledávání do hloubky a prohledávání do šířky (stage2). Pokud potřebujete, můžete využít rekurzi, velikost grafů je uzpůsobena rekurentnímu řešení úkoly. Algoritmus do šířky předpokládá využití fronty. Tu si můžete implementovat samostatně nebo můžete využít implementaci, která je součástí standardní knihovny std::queue.

Pro rekonstrukci cesty (funkce vrací seznam vrcholů na cestě) je nutné si pamatovat pro každý z vrcholů jeho případného předchůdce na cestě. Cestu pak dokážeme zrekonstruovat zpětným přechodem cesty od konce do začátku.

Poslední část úkolu (stage3) je zaměřena na vyhledání všech komponent grafu a získání dalších informací o souostroví, uprostřed kterého Robinson ztroskotal.

Jako při řešení předešlého úkolu doporučujeme postupně implementovat jednotlivé funkce definované v souboru crusoe.hpp. Požadovaná funkčnost je popsána v komentářích. Vedle zadání opět najdete testy. Testy lze spouštět i samostatně podle toho, kterou část úlohy zrovna řešíte. Část testů můžete zakomentovat nebo je spouštět pomocí definovaných tagů.

Většina testů na ukládá výsledek do souboru. Ten najdete ve složce, do níž projekt překládáte a kde ho spouštíte. Vykreslené obrázky vám mohou být nápomocné při řešení úlohy.

Doporučujeme úlohu řešit postupně, jak jsou jednotlivé funkce v zadání uvedeny. Každá další funkce předpokládá správnou funkčnost předchozích funkcí.