[Soubor je v kodovani UTF-8] ZÁKLADNÍ INFORMACE O PRÉMIOVÉ ÚLOZE -------------------------------------------------------------------------------------------- V prémiové úloze si budete hrát s jednoduchými orientovanými grafy. Úloha je rozdělena na dvě části a dohromady za ni lze získat až 8 bodů. Řešení odevzdávejte do IS a následně mi pošlete e-mail se žádostí o opravení úlohy. Deadline na odevzdání úlohy je v neděli 20. ledna 2008. Úlohy odevzdané později odmítám opravovat. Úloha je rozdělena na následující dvě části: 1) Reprezentace orientovaného grafu s ohodnocenými hranami (4 body) * vytvoření třídy (a případných pomocných tříd) pro reprezentaci orientovaného grafu * načtení grafu ze vstupního proudu a vytvoření konkrétní reprezentace tohoto grafu * uložení zadaného grafu do libovolného výstupního proudu * demonstrace výše uvedeného v metodě main() 2) Jednoduché grafové algoritmy (4 body) * vytvoření třídy s implementací jednoduchých grafových algoritmů * implementace algoritmu pro prohledávání grafu do hloubky ze zadaného vrcholu * implementace algoritmu pro prohledávání grafu do šířky ze zadaného vrcholu * implementace algoritmu pro vyhledání nejkratší cesty mezi dvěma vrcholy grafu * demonstrace výše uvedeného v metodě main() Řešit můžete buď jen první část, nebo první i druhou část. Budete-li řešit obě části, je nutné je odevzdat zároveň. Postupné odevzdávání jednotlivých částí nepřipadá v úvahu. Následují podrobnější informace včetně krátkého úvodu do regulárních výrazů, které se vám při řešení úlohy budou určitě hodit. Nezapomeňte, že třída String nabízí spoustu užitečných metod, stejně jako třídy Integer, Collections a další. Přeji hodně úspěchů! POŽADAVKY NA IMPLEMENTACI -------------------------------------------------------------------------------------------- Třída Graph bude představovat orientovaný graf s hranami ohodnocenými kladnými celými čísly. Implementace této třídy je pouze na vás. Doporučuji vytvořit i pomocné třídy Vertex a Edge pro reprezentaci vrcholů a hran grafu. Třída by měla být napsána tak, aby ji mohl jednoduše použít někdo jiný než vy. Třída by měla obsahovat metody pro získání názvu grafu, uspořádané množiny všech vrcholů a množiny všech hran. Dále by mělo být možné získat vrchol se zadaným jménem, případně uspořádanou množinu všech sousedních vrcholů zadaného vrcholu a ohodnocení hrany mezi nimi. Názvy vrcholů jsou malá písmena abecedy uspořádána abecedně. Dále si musíte rozmyslet, jakým způsobem budete graf budovat při načítání ze souboru a případně vytvořit i odpovídající metody (nebo lépe jen konstruktor). Třída GraphStorage umožní načítání/ukládání grafu ze/do zadaného vstupního/výstupního proudu pomocí statických metod load() a save(). Popis formátu pro uložení orientovaného grafu najdete níže. Metody by měly vyhazovat výjimku GraphStorageException pokud při ukládání nebo načítání dojde k nějaké chybě. Výjimka by měla být vyhozena především při načítání grafů, pokud dostanete na vstup data ve špatném formátu. Třída GraphAlgorithms poskytne statické metody pro prohledávání grafu do hloubky, do šírky a pro nalezení nejkratší cesty mezi dvěma vrcholy. Metody pojmenujte depthFirstSearch(), breadthFirstSearch() a shortestPath(). Všechny metody budou mít jako první parametr graf, nad kterým má být algoritmus proveden, a jako druhý parametr počáteční vrchol. Metoda pro hledání nejkratší cesty bude mít navíc jako parametr i cílový vrchol. Všechny metody budou jako výsledek vracet seznam vrcholů. Při prohledávání grafu do hloubky i do šířky bude vrácený seznam obsahovat všechny dosažitelné vrcholy z počátečního vrcholu v takovém pořadí, v jakém byly navštíveny. Nezapomeňte, že nad vrcholy grafu je zavedeno uspořádání. Při hledání nejkratší cesty bude výsledkem posloupnost vrcholů tvořících cestu z počátečního do koncového vrcholu, případně null pokud cesta neexistuje. Součástí řešení bude i třída GraphDemo sloužící k demonstraci toho, co jste naprogramovali. Je velmi důležité, abyste byli schopni správně načítat grafy ze vstupního proudu. Když odevzdáte svoje řešení, budu ho testovat na několika špatně naformátovaných souborech a dvou správně naformátovaných. Prvním bude nějaký strom, druhým obecný graf. Nezapomeňte tedy svoje řešení otestovat na co nejvíce různých (především špatných) vstupech! Při opravování nebudu hledět na efektivitu kódu. Můžete směle používat rekurzi, pokud se vám bude na řešení některých problémů hodit. Hodnotit budu především objektovou dekompozici, dodržování konvencí, správné používání metod equals() a hashCode(), kontrolu parametrů ve všech metodách a konstruktorech, a hlavně kvalitní Javadoc komentáře. POŽADAVKY NA DEMONSTRACI -------------------------------------------------------------------------------------------- Svoji implementaci budete demonstrovat v metodě main() třídy GraphDemo. Tuto třídu musí být možné pustit z příkazové řádky s jedním parametrem, kterým bude název souboru, ze kterého se má načíst graf. Pro první část úkolu v metodě main() provedete následující: * zkontrolujete, zda byl zadán požadovaný parametr z příkazové řádky * pokud ne, vypíšete chybovou hlášku na chybový výstup a skončíte pomocí System.exit() * pokusíte se načíst graf ze souboru uvedeného jako parametr z příkazové řádky * pokud dojde k libovolné chybě, vypíšete chybovou hlášku a opět skončíte zpracování * na standardní výstup vypíšete pomocí metody println() řetězec "GRAPH" * načtený graf uložíte s pomocí třídy GraphStorage na standardní výstup * pokud dojde k libovolné chybě, vypíšete chybovou hlášku a opět skončíte zpracování * na standardní výstup vypíšete prázdný řádek pomocí metody println() Pro druhou část úkolu v metodě main() provedete následující: * na standardní výstup vypíšete pomocí metody println() řetězec "DEPTH FIRST SEARCH" * na standardní výstup vypíšete výsledky prohledávání načteného grafu do hloubky z každého vrcholu grafu, každý výsledek na jeden řádek (pro n vrcholů bude tedy n řádků) * jednotlivé výsledku budou ve tvaru ': ...', kde je název počátečního vrcholu a jsou vrcholy v takovém pořadí, v jakém byly navštíveny * na standardní výstup vypíšete prázdný řádek pomocí metody println() * na standardní výstup vypíšete pomocí metody println() řetězec "BREADTH FIRST SEARCH" * na standardní výstup vypíšete výsledky prohledávání načteného grafu do šířky z každého vrcholu grafu, každý výsledek na jeden řádek (pro n vrcholů bude tedy n řádků) * jednotlivé výsledku budou ve tvaru ': ...', kde je název počátečního vrcholu a jsou vrcholy v takovém pořadí, v jakém byly navštíveny * na standardní výstup vypíšete prázdný řádek pomocí metody println() * na standardní výstup vypíšete pomocí metody println() řetězec "SHORTEST PATH" * na standardní výstup vypíšete nejkratší cestu z vrcholu u do vrcholu v a z vrcholu v do u, kde u/v je nejmenší/největší vrchol v rámci uspořádání na množině vrcholů * obě cesty budou ve tvaru ' -> : ... ', kde je název počátečního vrcholu, je název koncového vrcholu a jsou vrcholy na cestě z do * pokud cesta neexistuje, vypíšete na výstup ' -> : path not found' * každá výsledná cesta bude vypsána na samostatném řádku * na standardní výstup vypíšete prázdný řádek pomocí metody println() Poznámka: Uvozovky nejsou součástí požadovaného výstupu! POPIS FORMÁTU TEXTOVÉHO SOUBORU PRO ULOŽENÍ ORIENTOVANÉHO GRAFU -------------------------------------------------------------------------------------------- Orientovaný graf je uložen v jednom textovém souboru v kódování UTF-8. Textový soubor s orientovaným grafem bude mít příponu '.graph'. Formát textového souboru pro uložení orientovaného grafu je následující: [nazev-grafu] {a, b, c, ..., z} {(a, b, 1); (b, c, 2); (c, b, 3); ...; (x, y, 100)} 1. řádek obsahuje název grafu. * řádek musí začínat levou hranatou závorkou a končit pravou hranatou závorkou * název grafu smí obsahovat pouze písmena 'a' až 'z' bez diakritiky a znak '-' * znak '-' se v názvu grafu nesmí vyskytovat na začátku/konci, ani vícekrát za sebou * kolem názvu grafu může být libovolný počet bílých znaků (nejsou součástí názvu) 2. řádek obsahuje množinu vrcholů grafu. * řádek musí začínat levou složenou závorkou a končit pravou složenou závorkou * je-li množina vrcholů prázdná, bude řádek obsahovat levou a pravou složenou závorku * vrcholy grafu jsou značeny písmeny 'a' až 'z' bez diakritiky a oddělovány čárkou * kolem názvu vrcholu může být libovolný počet bílých znaků (nejsou součástí názvu) * názvy vrcholů se nesmí na řádku opakovat, jedná se o zápis množiny * názvy vrcholů mohou být v množině uvedeny v libovolném pořadí 3. řádek obsahuje množinu ohodnocených orientovaných hran mezi dvojicemi vrcholů grafu. * řádek musí začínat levou složenou závorkou a končit pravou složenou závorkou * je-li množina hran prázdná, bude řádek obsahovat levou a pravou složenou závorku * hrany jsou uvedeny ve tvaru (u, v, w), kde u je počáteční vrchol z množiny vrcholů, v je koncový vrchol z množiny vrcholů a w je ohodnocení hrany kladným celým číslem * počáteční a koncový vrchol hrany musí být navzájem různé, nejsou povoleny smyčky * jednotlivé složky hran jsou odděleny čárkou, jednotlivé hrany středníkem * kolem názvu vrcholu i ohodnocení hrany může být libovolný počet bílých znaků 4. řádek je prázdný. Soubor ve správném formátu tedy obsahuje právě 4 řádky dle výše uvedených pravidel. Všechny textové soubory s jiným formátem byste měli vyhodnotit jako nevalidní. VELMI KRÁTKÝ ÚVOD DO REGULÁRNÍCH VÝRAZŮ -------------------------------------------------------------------------------------------- Regulární výraz je v Javě reprezentován jako textový řetězec. Pro konstrukci regulárních výrazů v Javě lze použít následujících konstrukcí: * "[a-z]+" ... vyhovuje neprázdnému řetězci složenému z malých písmen abecedy * "\\s*,\\s*" ... vyhovuje řetězci s čárkou a libovolným počtem bílých znaků vlevo/vpravo * "\\d+" ... vyhovuje neprázdnému řetězci složenému z číslic * "(\\d+)( \\d+)*" ... vyhovuje posloupnosti kladných celých čísel oddělených mezerou Více informací lze nalézt v dokumentaci, ale tohle by vám mohlo stačit...