Grafové algoritmy ve výuce ekonomicko matematických metod

Mendelova univerzita v Brně Provozně ekonomická fakulta

Grafové algoritmy ve výuce ekonomicko matematických metod Bakalářská práce

Vedoucí práce: Mgr. Tomáš Foltýnek, Ph.D.

Petr Zach

Brno 2010

2

Zde se nachází zadání práce

Děkuji svému vedoucímu bakalářské práce Mgr. Tomáši Foltýnkovi, Ph.D. a pracovníkům ÚSOV za cenné a konstruktivní rady, čas a trpělivost, které mi v průběhu tvorby záverečné práce věnovali.

Prohlašuji, že jsem závěrečnou práci vypracoval samostatně s použitím literatury, kterou uvádím v seznamu.

Brno, 17. května 2010

....................................................

5

Abstract Zach, P. Graph algorithms in courses of Economic-mathematical Methods. Bachelor thesis. Brno, 2010. The thesis deals with the problem of graphs and graph algorithms through operational research. After the theoretical basis follows the analysis, concept and implementation of process application, which can be used as a teaching tool, particularly in the EMM courses. This allows students to create graphs models, apply for them selected graph algorithms, together with export of whole solution. Application is made with regard of further extension possibility to create another graph algorithms. Keywords graph theory, graph algorithms, Delphi, shortest path problem, minimal spanning tree

Abstrakt Zach, P. Grafové algoritmy ve výuce ekonomicko matematických metod. Bakalářská práce. Brno, 2010. Závěrečná práce přibližuje problematiku grafů a grafových algoritmů s využitím v oblasti operačního výzkumu. Po teoretickém základu následuje analýza, návrh a postup implementace aplikace, která najde uplatnění jako učební pomůcka zejména do předmětu EMM. Umožní studentům tvořit grafové modely a na ně aplikovat vybrané grafové algoritmy a celé řešení exportovat. Aplikace je tvořena tak, aby byla pohodlně rozšiřitelná o další grafové algoritmy. Klíčová slova teorie grafů, grafové algoritmy, Delphi, nejkratší cesta, kostra grafu

6

OBSAH

Obsah 1 Úvod a cíl práce 1.1 Úvod do problematiky . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Cíl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 8

2 Současný stav

10

3 Východiska práce 3.1 Operační výzkum a Ekonomicko matematické metody 3.2 Základní poznatky z teorie grafů . . . . . . . . . . . . 3.3 Algoritmy a jejich aplikace . . . . . . . . . . . . . . . 3.4 Reprezentace grafu . . . . . . . . . . . . . . . . . . . 3.5 Vývojové prostředí Delphi . . . . . . . . . . . . . . . 3.6 Dynamické datové typy . . . . . . . . . . . . . . . . . 3.7 Dynamic Link Library . . . . . . . . . . . . . . . . . 3.8 Multiple Document Interface . . . . . . . . . . . . . . 3.9 Algoritmus de Casteljau . . . . . . . . . . . . . . . . 3.10 LATEX a balík pstricks . . . . . . . . . . . . . . . . .

11 11 11 16 18 19 19 21 21 22 23

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

4 Metodika řešení

24

5 Vlastní práce 5.1 Analýza požadavků . . . . . . . . . . . . . . 5.2 Návrh aplikace . . . . . . . . . . . . . . . . 5.3 Organizace kódu . . . . . . . . . . . . . . . 5.4 Implementace rozhraní . . . . . . . . . . . . 5.5 Implementace struktur . . . . . . . . . . . . 5.6 Princip překreslování a práce nad plátnem . 5.7 Implementace vykreslování prvků . . . . . . 5.8 Indetifikace prvků na plátně . . . . . . . . . 5.9 Vstup a výstup . . . . . . . . . . . . . . . . 5.10 Komunikace s knihovnou a krokování řešení 5.11 Export grafu . . . . . . . . . . . . . . . . . .

25 25 26 28 28 31 31 33 36 37 38 40

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

6 Diskuse

43

7 Závěr

44

8 Literatura

45

Přílohy

46

A GUI při startu aplikace

47

OBSAH

7

B Pracovní formulář

48

C Implementace dynamických struktur

49

D Pseudokód metody PlatnoMouseDown

50

E Pseudokód metody PlatnoMouseMove

51

F Pseudokód metody PlatnoMouseUp

52

G Graf v souboru

53

H API komunikace s knihovnou

54

1 ÚVOD A CÍL PRÁCE

1 1.1

8

Úvod a cíl práce Úvod do problematiky

Prudký rozvoj informačních technologií posledních desetiletí významnou měrou ovlivnil život lidí. IT nachází uplatnění v různorodých činnostech a v mnoha směrech se staly doslova nepostradatelnými. S výpočetní technikou se setkáváme na místech, kde si to většina ani uvědomuje. Informační a komunikační technologie jsou symbolem dnešní doby a udávají směr vývoje celé společnosti. S využíváním výpočetní techniky je již neodmyslitelně spjata pestrá množina vědních disciplín, která se dohromady nazývá Operační výzkum (viz níže). Této problematice se na Provozně ekonomické fakultě Mendelovy univerzity v Brně věnují zejména předměty Ekonomicko matematické metody a Operační výzkum. Oba tyto předměty jsou při výuce zásobeny literaturou a jinými běžnými studijními materiály, které však ne zcela splňují formu, jakou udává dnešní trend výuky. Velmi oblíbený, nejen na vysokých školách, se stává eLearning. ELearning lze popsat jako nástroj pro podporu výuky, který využívá moderních výpočetních a komunikačních prostředků. Jeho snahou je začlenit se do studia tak, aby je učinil efektivnějším. Ve spojení s Internetem tak otevírá nové možnosti hlavně pro kombinovanou formu studia. K materiálům lze přistoupit internetovým připojením kdykoli a odkudkoli. V rámci prezenčního studia může univerzita pro výuku vhodné části náplně předmětu použít pouze eLearningové opory a v konečném důsledku tak efektivnějším využitím vyučujících vyhovět stále většímu zájmu o studium na vysokých školách. Nikterak ovšem nemusí trpět kvalita studia, protože interaktivní a propracovaný eLearning, který využívá schopností informačních technologií, mnohdy předčí mluvené slovo nebo omezené možnosti tabule. Vytváří se tedy elektronická podpora studia i do výše zmíněných předmětů. Zde je žádaná dvojnásob, protože kromě všeobecných výhod e-opor lze v problematice operačního výzkumu s velkou výhodou využít možností výpočetní techniky. Na celém modulu zpravidla pracuje kvůli jeho rozsahu více lidí, což nabízí příležitosti k realizaci dílčích projektů. Jedním z nich se zabývá i tato bakalářská práce.

1.2

Cíl práce

Výsledek musí primárně vyhovovat požadavkům Ústavu statistiky a operačního výzkumu PEF MENDELU v Brně (ÚSOV), který výstup práce začlení jako součást elektronických opor vybraných předmětů. Cílem tedy je se nejprve seznámit s problematikou teorie grafů a grafovými algoritmy se zaměřením na náplň síťové analýzy EMM. Dále je nutné navrhnout a poté vytvořit desktopovou aplikaci pro platformu MS Windows bez speciálních nároků na operační systém a programové vybavení, která vhodným způsobem osvětlí studentům problematiku teorie grafů. Tato oblast je ze souvislého textu s nedostatkem grafických ukázek pro studenty obtížně srozumitelná

1.2 Cíl práce

9

a ne vždy správně pochopí smysl a postup jednotlivých metod. Proto je zde nutná pomůcka, která po nezbytném teoretickém základu vyučujícího názorně problém předvede, může být podle potřeby uživatelem ovládána a vytvoří dále použitelný výstup. V aplikaci bude možno pomocí intuitivního GUI1 vytvářet různé modely grafů a na ně pak aplikovat algoritmy, které se používají v teorii grafů a zejména síťové analýze operačního výzkumu. Program umožní vytvořený model grafu pro pozdější zpracování uložit. Také musí být vyřešen způsob, jak explicitně vytvořit model grafu přímo tvorbou/úpravou uloženého souboru. Celý výstup z aplikace algoritmu na model musí studentu dopřát dostatek času na porozumění změn v každé části výpočtu. Grafický výstup bude doplňován textovým komentářem. Řešení musí být exportovatelné tak, aby vyučující mohl snadno vytvořit zadání zápočtové písemky a zároveň si v aplikaci ověřit správné řešení. Nakonec je nutné aplikaci rozšířit o schopnost zpracování nových algoritmů tak, že nebude nutná další kompilace. Do správného adresáře se pouze nakopíruje nová knihovna (DLL2). V rámci této práce tedy bude pro ukázku vytvořena knihovna s vybraným algoritmem. V neposlední řadě musí brát aplikace zřetel na koncového uživatele. Prostředí musí uživatelsky přívětivé, ovládání intuitivní a využítí efektivní.

1 2

Grafické uživatelské prostředí (angl. Graphical User Interface). Dynamic-link library - dynamicky připojovaná knihovna, viz dále.

2 SOUČASNÝ STAV

2

10

Současný stav

Na Mendelově univerzitě v Brně funguje Univerzitní informační systém (UIS), který kromě mnoha jiných součástí integruje eLearningový modul, který vyučujícím umožňuje pro každý předmět vytvořit elektronickou podporu studia. Ta je automaticky zpřístupněna všem studentům, kteří právě studují daný předmět. Předměty Ekonomicko matematické metody a Operační výzkum (dále jen EMM a OV) v současné době mají opory, které slouží zejména jako prostor pro sdílení elektronických dokumentů s typovými modely a příklady na procvičení látky. Opora EMM obsahuje flashové animace, které krokováním po snímcích znázorňují chování jednotlivých metod aplikovaných na vzorovém modelu. Bohužel pro každou metodu je vytvořena jen jedna animace. Je tedy nutné vytvořit prostředek, který uživateli (studentům i vyučujícím) umožní tvořit různorodé modely a na nich demonstrovat jednotlivé algoritmy. V bezplatné internetové sféře již existujě několik online přístupných projektů, které do určité míry splňují požadavky na budoucí aplikaci. Za zmínku stojí velmi vydařené aplikace Romana Kužele3 , projekt Mathematical Programing4 , autor je K. Ikeda nebo JGraphEd, autor Jonatan Haras5 . Žádný z nich ale potřeby Ústavu statistiky a operačního výzkumu neuspokojuje zcela. Projekty mají například omezené spektrum řešených úloh, nebo neumožňují práci se I/O soubory. Hlavně se ale teorií grafů zabývají z pohledu diskrétní matematiky, ale aplikace pro EMM a OV by měla studentům příblížit teorii grafů jako nástroj pro analýzu problému ekonomického charakteru. Investici do komerčního software ústav neuvažuje.

3

Zdroj: http://cam.zcu.cz/~rkuzel/aplety. Zdroj: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/. 5 Zdroj: http://www.jharris.ca/JGraphEd/.

4

11

3 VÝCHODISKA PRÁCE

3

Východiska práce

3.1

Operační výzkum a Ekonomicko matematické metody

Samotný Operační výzkum Holoubek (2009, s. 5) definuje jako množinu exaktních metod a nástrojů, používaných při rozhodování o tom, jak co nejlepším způsobem řešit složité operace uskutečňované ve velkých a složitých systémech. Oblast Ekonomicko matematických metod dále popisuje jako výběr ze souboru poměrně samostatných vědních disciplín označovaných souhrnným názvem Operační výzkum. EMM je tedy podmnožinou OV. Operační výzkum je vědní disciplína velmi ovlivněná praxí. Základy OV byly položeny průmyslovou revolucí v první polovině 19. století. Paradoxně největší rozmach zaznamenal OV díky druhé světové válce. Bylo třeba hledat nejvhodnější řešení v oblasti logistiky, plánování, harmonogramu operací, rozdělování surovin, atd. s ohledem na ekonomickou stránku věci. Po válce se výzkum těchto otázek nezastavil, protože dané poznatky nacházely své uplatnění zejména v ekonomice, kde se setkáváme prakticky se stejnými situacemi – konec konců, ekonomika je také trochu válka (Fajmon, Koláček, 2005, s. 150). Operační výzkum do dnešní podoby posunuli svým velkým přínosem hlavně L. V. Kantorovič a G. B. Dantzig, kteří jsou spjati zejména s lineárním programováním. Významnou roli ve vývoji OV hrálo i hojné využívání výpočetní techniky. Holoubek (2009) dělí OV na tyto disciplíny: 1. Matematické programování 2. Síťová analýza 3. Strukturní analýza 4. Teorie zásob 5. Teorie obnovy 6. Teorie hromadné obsluhy 7. Teorie her Problematika zpracovávaná v této závěrečné práci se týká oblasti síťové analýzy. Je tedy nezbytné seznámit se s teoretickým minimem teorie grafů a jejím využitím.

3.2

Základní poznatky z teorie grafů

Jak už název napovídá, předmětem zájmu je zde graf6, který se skládá z množin dvou elementárních prvků – uzlů a hran. Holoubek (2009, s. 119) definuje graf jako neprázdnou množinu uzlů U a neprázdnou množinu hran H, které jsou uspořádány ve dvoj či trojrozměrném prostoru (trojrozměrné nebudou dále uvažovány). Prostý graf G je možno definovat zápisem: G = (U, H) pro U = {ui}, i = 1, 2, 3, . . . , n, H = {hi,j } = {ui, uj }, i, j = 1, 2, 3, . . . , n. 6

V žádném případě se nejedná o graf funkce.

3.2 Základní poznatky z teorie grafů

12

Nejčastěji se uzel znázorňuje pomocí kroužku nebo bodu, hrany se znázorňují pomocí úseček nebo křivek spojující dva uzly. Většinou nese každý prvek své označení, kterým ho lze snadno identifikovat. Hrany mohou být identifikovány pomocí dvou hodnot reprezentující uzly, se kterými je hrana spojena. Příklad grafů lze vidět na obrázku 1. Každá hrana vždy začíná a končí v určitém uzlu. Uzel ui je označován jako počáteční uzel a uj jako koncový uzel hrany hi,j . Pokud se ui rovná uj , tedy že hrana začíná i končí ve stejném uzlu, jedná se o smyčku. Výše zmíněná definice vychází z předpokladu prostého grafu. Prostý graf neuvažuje násobné (paralelní) hrany mezi dvěma uzly. Pokud graf obsahuje násobné hrany, je nazýván multigraf. Jestliže je naopak prostý a současně neobsahuje žádnou smyčku, jedná se o jednoduchý graf. Následuje definice obecného grafu, kde vzniká prostor i pro násobné hrany. Šeda (2003, s. 5) popisuje obecný graf G jako trojici (U, H, e), kde V je množina vrcholů grafu G a e je zobrazení incidence, e : H → U × U 7 . V rámci síťové analýzy OV bude dále užíváno pouze jednoduchého grafu. Jinými slovy by graf měl být hlavně chápán jako model, který zjednodušuje pohled na složitou strukturu určitého systému. Holoubek (2009, s. 7 a 8) definuje model jako abstrakci reality, která z jistého hlediska (účelově) zjednodušeně znázorňuje podstatné znaky a vlastnosti zkoumaného objektu a na něm definovaného systému. Uvádí také, že systém je: • Účelově zjednodušená představa o objektu sloužící k poznání podstatných vlastností objektu a k jeho následnému ovlivňování. • Uspořádaný soubor vzájemně propojených částí – prvků – tvořících celek se společnou funkcí a chováním. • Relativně uzavřená část nějakého prostředí – okolí. Okolí obklopuje systém, tvoří jeho vnější prostředí. Mezí okolím a systémem existují oboustranné vzájemné vztahy. Užití grafů a stručná historie Grafy se využívají v mnoha oborech lidského bádání. Pro představu si lze představit mapu měst a silnic České republiky, kde města reprezentují uzly a silnice jsou hrany. Znázornění organizačních struktur v podniku je také nejčastěji tvořeno pomocí grafu. Nepřeberné množství diagramů užívaných v informatice a podnikovém řízení, rodokmeny, tzv. „pavoukÿ (ve skutečnosti strom), který znázorňuje pořadí sportovních utkání, to vše jsou svým způsobem grafy. Podle Jírovského (2008) pochází první zmínka o grafech už z první poloviny 18. století, kdy tento pojem zavedl Leonard Euler (1707-1783), který roku 1736 řešil známý Problém sedmi mostů města Königsbergu. Jednalo se o to, že měl zjistit, zda je možné projít všemi sedmi mosty pouze jednou a vrátit se zpět na místo, odkud vyrazil. Při řešení použil první graf, protože jednotlivé břehy označil jako uzly a mosty chápal jako hrany. To mu pomohlo ke zjištění, že problém je neřešitelný. Dále stojí 7

Každé hraně h ∈ H přiřazuje uspořádanou dvojici vrcholů (ui , uj ) ∈ U .

13

3.2 Základní poznatky z teorie grafů

5 1

2

2

6

2

1

3

3

4

1 a)

b)

1

4 3

9 6

5

Obr. 1: Ukázka dvou modelů grafů (Exportováno z aplikace, která je předmětem BP)

za zmínku Gustav Kirchhoff, který až o sto let pouzději využil kostry grafu (viz dále) pro výpočet proudů v elektrických síťích. Přibližně ve stejné době (polovina 19. stol) vymyslel William Hamilton hru, jejímž smyslem bylo propojit jedním tahem všechny vrcholy pravidelného dvanáctistěnu. Odtud pochází ustálený výraz pro kružnici, která spojuje všechny vrcholy (uzly), a to hamiltonská kružnice. Významným milníkem 19. století je Problém čtyř barev. Zabývá se tím, zda je možné obarvit na mapě evropských zemí všechny státy tak, aby sousední státy měly vždy jinou barvu8 . Největší rozmach zažila teorie grafů spolu s OV v minulém století. Spousta algoritmů řešící úlohy na grafových modelech nese jména podle svých objevitelů, za zmínku stojí například E. Dijkstra (nejkratší cesta), J. B. Kruskal, R. C. Prim, Češi V. Jarník a O. Borůvka (všichni min. kostra grafu). EMM se dnes zabývají kromě kostry grafu a nejkratší cesty také například maximálním tokem v síti nebo metodami z oblasti řízení projektů – deteministická metoda CPM (Critical Path Method) a nedeterministická PERT (Program Evaluation and Review Technique). Orientace grafu Graf může nabývat dvou zásadních podob, může být orientovaný (obrázek 1, a) nebo neorientovaný (obrázek 1, b). Koucký a Zelinka (2003, s. 58) o neorientovaném grafu tvrdí, že je to uspořádaná dvojice G = (U, H), kde U je konečná množina uzlů a H je podmnožina množiny všech dvouprvkových podmnožin U (vychází z předpokladu, že hranu lze identifikovat dvojicí uzlů, kde hrana začíná a končí). Prvky množiny H jsou neorientované hrany. Naopak o orientovaném grafu se zmiňují jako o uspořádané dvojici G = (U, H), kde U je množina uzlů a H je podmnožina množiny všech uspořádaných dvojic prvků množiny U (tedy podmnožina kartézského součinu U × U). Prvky množiny H jsou orientované hrany. Orientace hrany se znázorňuje pomocí šipky na koncovém bodě hrany směřující ke koncovému uzlu. Princip orientace lze jednoduše vysvětlit na příkladu, kde uzly 8

Vyřešeno až v sedmdesátých letech minulého století.

3.2 Základní poznatky z teorie grafů

14

hran představují města a hrany komunikace silničního provozu. Pokud je hrana neorientovaná, lze přejíždět mezi městy v obou směrech, pokud je hrana orientovaná, značí jednosměrnou komunikaci ve směru od počátečního do koncového uzlu. Ohodnocení grafu Jak je zmíněno výše, jednotlivé prvky bývají z různých důvodů označeny číslem nebo jinak. Označení uzlů má většinou pouze orientační charakter, ale číslem označená hrana je ohodnocená hrana, jejíž číslo může označovat například vzdálenost mezi počátečním a koncovým uzlem (počátečním a cílovým městem). Černý (2008, s. 36) popisuje ohodnocený graf (obrázek 1, b) jako graf G = (V, H), ke kterému přidáme funkci o : H → H, která každé hraně h přiřadí hodnotu o(h). Neohodnocený graf (obrázek 1, a) lze chápat tak, že všechny hrany mají stejné ohodnocení, a to hodnotu 1. Izomorfismus a rovinný graf Izomorfismus grafů se zabývá otázkou, jak grafy porovnávat. Nezáleží zde na poloze ani tvaru znázorněných uzlů a hran. Zda jsou grafy vzájemně izomorfní se hodnotí zejména podle počtu uzlů a hran a stupňů uzlů9 . Foltýnek a kol. (2006) používají pro izomorfní grafy tuto definici: „Nechť G1 = (U1 , H1 , e1 ) a G2 = (U2 , H2 , e2 ) jsou dva grafy, pro které platí, že U1 = U2 , H1 = H2 a e1 = e2 . Potom jsou grafy G1 a G2 stejné. G1 a G2 se nazývají izomorfní, píšeme G1 ≈ G2 , když existuje dvojice vzájemně jednoznačných zobrazení α : U1 → U2 a β : H1 → H2 takových, že zachovávají vztahy incidence e1 a e2 .ÿ Ačkoliv vizuálně různé grafy mohou být ve skutečnosti izomorfní a mohlo by se zdát, že není třeba zajímat se dále o způsobu znázorňování grafů, je ale vhodné seznámit se s pojmem rovinný graf. Lze ho nakreslit tak, aby se vzájemně žádné hrany nekřížily. Výhoda těchto grafů je zřejmá. Zpřehledňuje celý model a zabraňuje případným omylům, kdy je možno několik hran vzájemným překrytím vnímat jako jednu, kdy je vlivem křížení nečitelné ohodnocení některé z hran, atd. Souvislost grafu O grafu lze říci, že je souvislý (obrázek 1, b), pokud jsou všechny uzly pomocí hran spojeny do souvislého celku (komponenty), tedy bez ohledu na orientaci existuje mezi všemi dvojicemi uzlů cesta. I uzel, který neinciduje s žádnou hranou je samostatná komponenta označovaná jako izolovaný uzel. Graf se může skládat i z více než jedné komponenty. V takovém případě se jedná o nesouvislý graf (obrázek 1, a). Pokud s každou dvojicí uzlů inciduje nějaká hrana, vzniká úplný graf. Stupeň uzlu ui u neorientovaných grafů se rovná počtu hran, které jsou spojeny s uzlem ui (hrany incidující s uzlem ui ). U orientovaných grafů se analogicky určují polostupně vstupů (výstupů). 9

3.2 Základní poznatky z teorie grafů

15

Podgraf, faktor a kostra grafu Jestliže existuje graf G = (U, H) a graf G1 = (U1 , H1 ), je graf G1 podgrafem G právě tehdy, jestliže se U ⊆ U1 ∧ H ⊆ H1 . Jinými slovy to znamená, že podgraf grafu G nazvaný G1 vznikne, pokud odstraníme některé uzly nebo hrany z původního grafu G. Zvláštním případem podgrafu je faktor. Vzniká podobně jako podgraf, ale z původního grafu nesmí být odstraněn žádný uzel, pouze hrany. Znamená to tedy, že U = U1 ∧ H ⊆ H1 . A speciálním případem faktoru je kostra. Faktor se nazývá kostra, jestliže je současně stromem. Stromy jsou významným typem grafu, které nacházejí své uplatnění v mnoha oborech. Strom je souvislý, neorientovaný graf, který neobsahuje kružnici (viz níže) a počet jeho hran je minimální. Pokud n značí počet uzlů grafu, musí strom obsahovat právě n − 1 hran. Tato práce se však hlouběji touto obsáhlou problematikou nezabývá. Dále je nutné zmínit, že minimální kostra značí kostru, kde má suma ohodnocení všech hran kostry minimální hodnotu. Sled, tah, cesta, kružnice, cyklus Existuje několik zajímavých podgrafů, které dostaly své vlastní pojmenování. Prvním z nich je sled. Sled (z vrcholu u do vrcholu v) v grafu G je libovolná posloupnost (u = u0 , u1 , . . . , uk = v), kde ui jsou uzly (vrcholy) grafu G2 a pro každé i = 1, . . . , k je hi,j = (ui−1 , ui ) hranou grafu G (Čada a kol., 2004, s. 73). Součet ohodnocení všech hran sledu je označován jako délka sledu. V definici sledu nezáleží na orientaci. Neopakuje-li se v neorientovaném sledu žádná hrana, vzniká řetěz, v orientovaném grafu tah. Pokud se ve sledu neopakují žádné uzly (tím pádem ani hrany), jedná se o cestu. Cesta v neorientovaném grafu, která začíná i končí ve stejném uzlu, se nazývá kružnice. V případě orientovaného grafu je to cyklus. Síťový graf Na závěr teoretického úvodu do oblasti teorie grafů se již lze seznámit s klíčovým druhem grafu, síťovým grafem. Síťový graf (obrázek 1, b), někdy zkráceně označován jako síť, je v oblasti OV velmi významným typem grafu. EMM, resp. OV se zabývá grafovými modely nesoucí právě prvky charakteristické pro síťový graf. Holoubek (2009) popisuje síťový graf jako souvislý, konečný, orientovaný, acyklický, nezáporně ohodnocený s jedním vstupním a jedním výstupním uzlem. Konečný je každý graf se spočitatelnou množinou svých prvků. Acyklický graf nesmí obsahovat žádný cyklus. Vstupní uzel, někdy označován jako startovní10 , je uzel, ze kterého hrany pouze vystupují, analogicky výstupní je uzel, kam hrany pouze vstupují a žádná nevychází. Metody, které jsou v OV aplikovatelné na orientovaný graf, začínají pracovat s modelem grafu právě od tohoto uzlu. 10

3.3 Algoritmy a jejich aplikace

3.3

16

Algoritmy a jejich aplikace

Grafy se používají proto, aby modelovaly určitý systém. Metody nasazované na tyto modely pak umožnují snáze vyrešit problém, který je spojený s tímto systémem. Na modelech se rešení, které je ekonomicky nejvýhodnejší a nejlepší pro dané podmínky, označuje se jako optimální, extrémní. Optimalizační úlohy jsou tedy vždy spojeny s hledáním maxima nebo minima. Zároveň ale existuje množina omezení (omezujících podmínek) různého charakteru (např. ohodnocení a orientace hran), které více či méně ovlivnují budoucí optimální hodnotu účelové funkce. Demel (2002, s. 32) tvrdí, že účelová funkce je zobrazení, které každému přípustnému rešení přirazuje určité číslo. Pricemž množina přípustných rešení jsou všechna rešení pro daný problém splnující omezující podmínky. Algorimů aplikovatelných na model grafu je celá řada. Často se liší pouze drobnostmi nebo vlastnostmi grafu, které musí graf splňovat, aby byl algoritmus aplikovatelný. V zásadě se jedná o úlohy hledání dostupnosti uzlu (prohledávání do hloubky nebo do šířky), úlohy o hledání nejkratších cest, úlohy o tocích v síti nebo úlohy z oblasti řízení projektu. Budoucí aplikace bude schopna rešit i algoritmy na grafech, které nemusí být nutně síťové. Vše záleží na knihovně, kterou si potenciální uživatel muže kdykoliv naprogramovat. Primárně ale bude aplikace pracovat právě se síťovým grafem, a tak je třeba, aby aplikace zvládla implicitně určit, zda je graf souvislý a acyklický. Z modelu uvedených výše jsou obě tyto vlastnosti zřejmé, ale mohou nastat složitejší případy, kdy se nedá na pouhý úsudek spolehnout. Ověření souvislosti Ověřit souvislost lze v grafu několika způsoby. V této práci bude použit algoritmus pro zjištění souvislosti grafu snadno předveditelný pomocí tabulky. Samotný algoritmus podle Holoubka (2009, s. 123) probíhá tak, že do tabulky znázorníme do prvního sloupce všechny hrany zápisem ui − uj seřazené nejlépe podle počátečních uzlů a do dalšího sloupce postupně všechny uzly. Ve třetím sloupci se očíslují uzly čísly komponent Ki tak, aby každý uzel tvořil samostatnou komponentu (izolovaný uzel). Další kroky se zanáší vždy do dalšího sloupce. V každém kroku se prochází všechny hrany. Pokud je Ki uzlu ui < Kj uzlu uj hrany hij , pak Kj := Ki . Jestliže Ki > Kj , pak Ki := Kj . Končí se v okamžiku, kdy se mezi sloupci nemění čísla komponent. Pak lze z posledních dvou sloupců zjistit, kolik komponent graf obsahuje.

17

3.3 Algoritmy a jejich aplikace

Tab. 1: Test souvislosti grafu z Obr. 1, b.

Výčet hran 1–2 1–3 2–4 3–2 3–5 4–3

Výčet uzlů 1 2 3 4 5

Tabulka komponent 0. krok 1. krok 2. krok 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1

Ověření acykličnosti Pro zjištění acykličnosti bude použit Fordův algoritmus pro číslování uzlů grafu. Pracuje se zde s řády uzlů označované λku (dolní index označuje uzel, horní je číslo kroku), přičemž platí tato pravidla: • Mezi uzly stejného řádu neexistuje hrana. • Hrany s koncovým uzlem řádu r mají počáteční uzel řádu r − 1. • Hrany s počátečním uzlem řádu r mají koncový uzel řádu r + 1. • Vstupní uzel je vždy nultého řádu, výstupní uzel je nejvyššího řádu. Na počátku výpočtu je vhodné si všechny uzly a hrany seřadit. V počátečním kroku je všem uzlům včetně vstupního přiřazena hodnota λ0u = 0. V každém dalším kroku se hodnoty λ jednotlivých uzlů mohou zvyšovat. Přepočítávají se totiž všechny hodnoty λ, musí ale platit vztah λuk−1 ≤ λku Jinými slovy to znamená, že λ v aktuálním kroku stejného uzlu musí být větší nebo rovna λ předchozího kroku daného uzlu. Přepočet hodnot λ v každém kroku se řídí předpisem λkn = max(λtp + 1) Tímto zápisem se rozumí, že hledáme maximální hodnotu λn z hodnot λ uzlů, ze kterých vedou hrany přímo do právě zpracovávaného uzlu. Největší hodnota se následně zvětší o jedničku. Může nastat situace, že některý předcházející uzel ještě v daném kroku nemá svoji hodnotu λp . V takovém případě se zpracuje hodnota λp z předcházejícího kroku (Holoubek, 2009). Výpočet končí, pokud se hodnoty λ všech uzlů v novém kroku již nezmění (graf je acyklický) nebo je některá hodnota λ větší než je počet všech uzlů grafu (graf je cyklický). Praktická ukázka zjištění acykličnosti grafu je v tabulce níže. V tomto případě graf z obrázku 1, b obsahuje cyklus, protože ve 4. kroku se objevují hodnoty větší než počet uzlů grafu.

18

3.4 Reprezentace grafu

Tab. 2: Test acykličnosti grafu z Obr. 1, b.

Výčet hran 1–2 1–3 2–4 3–2 3–5 4–3

Výčet uzlů 1 2 3 4 5

λ v dílčích krocích λ0u λ1u λ2u λ3u λ4u 0 0 0 0 0 0 1 2 4 5 0 1 3 4 6 0 2 3 5 6 0 2 4 5 7

Hledání nejkratší cesty Z množiny metod, které se v EMM aplikují na grafy, zde bude přiblížena jedna ze základních úloh celé teorie grafů – hledání nejkratší cesty v grafu. V EMM se pro hledání nekratší cesty v grafu využívá Dijkstrův algoritmus. Ve srovnání s BellmanFordovým algoritmem je rychlejší, zejména proto, že nalézá nejkratší cesty pouze v nezáporně ohodnoceném grafu. Z titulu síťového grafu, užívaného v EMM, je to algoritmus nejvhodnější. Algoritmus umí najít nejkratší cesty z vstupního uzlu do všech ostatních. Pracuje na principu značkování uzlů. Značky se dělí na trvalé a dočasné. Trvalé značky, někdy označované jako definitivní, se již v průběhu výpočtu nemohou změnit, definitivní značky dostávají uzly, u kterých už je jisté, že byla nalezena do nich vedoucí nejkratší cesta. Dočasnou značkou jsou označovány uzly, kam už byla zjištěna cesta, ale ještě nemusí být nejkratší. Značku lze popsat jako uspořádanou dvojici (vj , uj ), kde vj uchovává kumulativní vzdálenost od vstupního uzlu, přičemž uj je poslední uzel, který předchází aktuálnímu uzlu v cestě od vstupního uzlu. Postup lze přiblížit v tímto pseudokódem: 1. Označ vstupní uzel trvalou značkou s nulovou kum. vzdáleností (0, V ); 2. Z posledního trvale označeného uzlu najdi následníky; Následníky bez značky označ dočasnou značkou a vypočítej vj = vi + o(ui, uj ); Pro následníky s dočasnou značkou vypočítej vj = min(vj , vi + o(ui, uj )); 3. Ze všech uj označených dočasnou značkou vyber uzel s nejmenší vj a označ ho trvalou značkou; 4. Vrať se k druhému bodu dokud nebude množina dočasných uzlů prázdná; Hledání nejkratší cesty v grafu a kostry grafu lze vyzkoušet v aplikaci, která je součástí přiloženého CD.

3.4

Reprezentace grafu

Kromě grafického modelu grafu, kterým se zabývá text výše lze reprezentovat graf i jinými způsoby. Používá se: • Grafický model • Slovní model

3.5 Vývojové prostředí Delphi

19

• Matice • Datové struktury (počítače) Graf v paměti počítače V paměti počítače lze graf zaznamenat celou řadou způsobů. Nedá se ale přesně zvolit jeden, který by byl univerzální. Jakou strukturu zvolit, kromě úsudku programátora, záleží i na účelu, pro který má být struktura grafu v paměti použita nebo na vlastnostech zpracovávaných modelů. To porvrzuje i Demel (2002, s. 27), který navíc uvádí hned několik možností, jak držet graf v paměti počítače. Kromě maticového uložení grafu zmiňuje i variantu, kdy je graf uchováván ve dvou statických polích, což je velmi svazující. Prvků v polích je tolik, kolik je hran, přičemž jedno pole obsahuje označení počátečních, druhé označení koncových uzlů. Případné ohodnocení hran by se muselo ukládat do třetího pole. Druhý způsob, který Demel uvažuje, je opět vytovřit dvě statická pole A a B. Hodnoty A(i) jsou indexem prvku, kterým v poli B začíná seznam následníků vrcholu A(i). Konec seznamu následníků vrcholu udává počátek seznamu následníků uzlu i + 1. Ani jedna z možností nedovoluje neomezený počet prvků grafu. To řeší použití dynamických struktur ve třetí možnosti zmiňované Demelem (2002), a to je, že množinu uzlů tvoří statické pole s ukazateli na spojové seznamy hran, které vycházejí z toho uzlu. Budoucí počet hran v grafu tedy limituje jen kapacita operační paměti. V aplikaci, kterou popisuje tato bakalářská práce, byl použit ještě jiný datový model, který je však výše zmíněným textem inspirován a bude detailněji popsán v praktické části práce.

3.5

Vývojové prostředí Delphi

Delphi je nástroj určený k vytváření aplikací pro platformu MS Windows. Je to vývojové prostředí (IDE11 ), které integruje různé součásti pro pohodlnější programování (editor kódu, kompilátor, debuuger, UML editor, atd.). Navíc obsahuje RAD systém (Rapid Application Development), který umožňuje vytvořit vizuální rámec budoucí aplikace bez nutnosti tvorby programového kódu, čímž urychlí celý vývoj. Delphi používá jako programovací jazyk Object Pascal. Jak už název napovídá, jedná se o objektové rozšíření jazyku Turbo Pascal. OP pracuje s knihovnou VCL (Visual Component Library), která poskytuje hierarchickou strukturu komponent používaných pro aplikace vytvářené v Delphi.

3.6

Dynamické datové typy

Běžné (statické) datové typy kompilovaných programovacích jazyků po vytvoření alokují v paměti počítače vždy tak velký prostor, jaký přísluší danému datovému 11

Integrated Development Environment.

3.6 Dynamické datové typy

20

typu. Pro programátora je to pohodlný způsob deklarace proměnných, protože se nemusí starat o jejich uvolnění z paměti při ukončení aplikace. V rozsáhlých projektech je práce s těmito typy neefektivní, protože se většinou při činnosti aplikace nevyužije celý paměťový prostor, vyčleněný pro statické proměnné. Může nastat ale i druhá, ještě problematičtější, situace. Paměťový prostor proměnné totiž nemusí z různých důvodů vždy dostačovat. Pokud si například programátor vytvoří pole o tisíci prvcích pro evidenci filmů jeho videotéky, může v budoucnu vlastnit filmů padesát nebo i tisícjedna. Tento problém je v kompilovaných programovacích jazycích řešen dynamickými datovými strukturami. Ukazatel Základním stavebním kamenem dynamických struktur je datový typ ukazatel. Od ostatních datových typů se liší tím, že nejčastěji uchovává referenci na proměnnou statického datového typu, jak potvrzuje Pošta (2001) někdy nazývaný jako doménový typ ukazatele. Ve skutečnosti uchovává pouze adresu na určité místo v paměti a podle doménového typu aplikace k této paměťové oblasti přistupuje. Jeho velikost je vždy pouze 4 B. Na rozdíl od statických proměnných lze proměnné ukazatelového typu vytvářet a rušit kdykoliv během běhu programu a více ukazatelů může ukazovat na stejné místo. To skýtá pro vývojáře velké možnosti. Při neopatrném zacházení s ukazateli však může dojít k neočekávanému pádu aplikace. Rodina programovacích jazyků založených na Pascalu rozlišuje dva druhy ukazatelů - typové a netypové (univerzální). Typové mají doménový typ, netypové jsou pouze reference na místo paměti, po vhodném přetypování s nimi lze pracovat jako s typovými. Spojové struktury Hlavní výhoda dynamických proměnných spočívá v možnosti jejich sdružování do rozsáhlých spojových struktur (Polách, 1999). Lze tak tvořit struktury, jejichž rozsah je omezen pouze velikostí operační paměti počítače. Struktura je tvořená prvky (ukazateli), jejichž doménový typ tvoří strukturovaný datový typ záznam, který obsahuje kromě části nesoucí hlavní data také minimálně jednu nebo více položek12 stejného ukazatelového typu jako je sám prvek, který referuje další prvek ve struktuře. Pokud neodkazuje na žádné další místo v paměti, nabývá zvláštní hodnoty nil, která neukazuje nikam. Lze tak snadno zjistit počátek nebo konec spojové struktury. Tento systém umožňuje tvorbu celé řady struktur. Prvky lze uspořádat například do stromů nebo lineárních seznamů, které se dočkali mnoha modifikací. Velmi často používané jsou fronta (metoda FIFO) a zásobník (LIFO), do spojových seznamů lze libovolně vkládat nové prvky, řadit je (prioritní fronta), atd. Daň za tuto variabilitu je ale náročnější implementace. 12

Záleží, zda se jedná o jednosměrný nebo dvojsměrný seznam.

21

3.7 Dynamic Link Library

Ukazatel na začátek

Data

Data

Data

Data

Ukazatel

Ukazatel

Ukazatel

Ukazatel

nil

Obr. 2: Nástin jednosměrného spojového seznamu

3.7

Dynamic Link Library

Teixeira a Pacheco (2002, s. 129) popisují Dynamic Link Library (DLL) jako programový modul, který obsahuje kód, data a prostředky, který je možné sdílet mezi různými aplikacemi systému Windows. DLL a soubory s příponou exe jsou jediné dva spustitelné soubory výše zmíněného operačního systému. Dynamicky připojovaná knihovna na rozdíl od exe souboru nespouští instanci aplikace. Je to soubor procedur a funkcí, které s výhodou využívají jiné programy. To je právě jeden z důvodů, proč se DLL používá. Výhod, které přináší DLL je několik. Poskytují sdílený programový kód. Spustitelný soubor tak může zabírat méně paměti a jedna knihovna může být sdílena více než jedním programem. Hlavně ale můžeme pohodlně aktualizovat aplikaci přepsáním dynamické knihovny, aniž by bylo nutné překompilovat spustitelný soubor. Další nespornou výhodou těchto knihoven je nezávislost na prostředí, ve kterém byly vyvíjeny. Při znalosti API knihovny napsané například v C++ ji lze při dodržení jistých pravidel použít v aplikaci psané v jazyce Obejct Pascal. Rozdíl mezi statickým a dynamickým spojováním V problematice spojování se jedná o spojení podprogramů nacházejících se v jiných knihovnách či modulech s programovým kódem hlavní aplikace. Podle Cantua (2002, s. 433) se po překladu statického podprogramu vezme spojovací program přeložený kód podprogramu z přeložené jednotky (modulu či knihovny) a přidá jej do spustitelného souboru. Výsledný soubor .exe obsahuje mimo jiné i veškerý kód metod přijatých z jiných jednotek. Naopak k dynamickému spojování dochází, pokud jsou procedury nebo funkce volány aplikací až při samotném spouštění. Do té doby jsou v programu deklarovány pouze hlavičky funkcí. Pokud však při zavádění nelze nalézt požadovanou dynamickou knihovnu, vygeneruje se chybová hláška a program se vůbec nespustí.

3.8

Multiple Document Interface

Windows Developer Center (2010) popisuje Multiple Document Interface (MDI) jako aplikační rozhraní, které uživateli umožňuje práci s více dokumenty v rámci jedné aplikace ve stejném čase. Ve skutečnosti toto rozhraní nenabízí pouze paralelní zob-

22

3.9 Algoritmus de Casteljau

Zdrojový kód

Knihovna (DCU)

2

Překladač

Přeložený kód (DCU)

Statické spojování

Spoj. program

Spustitelný soubor (exe) 1

2

Externí deklarace

Dynamické spojování

Spoj. program

Spustitelný soubor (exe)

1

+ Dynamická knihovna (dll) 2 (DLL) = Přeložený kód

Obr. 3: Znázornení statického a dynamického spojování Zdroj: Cantu, 2002, upraveno autorem

razování více dokumentů, ale formulářových oken s jakýmkoli obsahem. Typickým reprezentantem MDI aplikací jsou nástroje pro úpravu grafiky (Adobe Photoshop), ale i tabulkový procesor MS Excel je MDI aplikace. Opakem tohoto modelu rozhraní je Document-oriented Model (např. jednoduchý textový editor). Všechna otevřená pracovní okna jsou uzavřena do rodičovského13 formuláře tzv. rámce, na jehož vlastnostech jsou podřízená okna závislá, jinak je ale práce s dceřinými formuláři neměnná. Přínos zde vytvářené aplikaci je tedy zřejmý - umožní uživateli pracovat s několika otevřenými modely grafu a sledovat případné odlišnosti aplikovaných algoritmů nebo různé chování jednoho algoritmu na dva a více jiných modelů grafu. Odpadá tak nutnost případných spouštění dalších instancí programu.

3.9

Algoritmus de Casteljau

Rekurzivní algoritmus de Casteljau je jedna z možností, jak vykreslit beziérovu křivku. Bod křivky o souřadnicích Q(t) se vypočítá podle rekurentního vztahu Pi,j (t) = (1 − t)Pj−1,i−1 + tP j, i − 1 kde i = 1, 2, . . . , n a j = i, i + 1, . . . , n. Vstupem tohoto algoritmu jsou body řídícího polygonu. Dosadí se za P0,i = Pi a rekurentní vztah výše postupně vypočítává body Pi,j tak, jak ukazuje obrázek 5. V posledním kroku výpočtu je koeficient Pn,n (t) roven hodnotě křivky v bodě Q(t). Obrázek 4 ukazuje výpočet bodu Q(1/2) (Žára a kol., 1998, s. 70). 13

Nejedná se o dědičnost tříd v OOP.

23

3.10 LATEX a balík pstricks P2,1

P1

P2

P2,2

P3,2 Q(1/2)

P1,1

P3,1

P0

P3

Obr. 4: Algoritmus de Casteljau Zdroj: Žára a spol. (upraveno autorem) P0,0

P0,1 P1,1

P0,2 P2,1

P2,2

P0,3 P3,1

P3,2 P3,3

Obr. 5: Postup při výpočtu koeficientů v algoritmu de Casteljau Zdroj: Žára a spol. (upraveno autorem)

3.10

LATEX a balík pstricks

Systém LATEX14 je nadstavbou volně šiřitelného nástroje pro typografickou sazbu TEX (Rybička, 2003, s. 9). Systém TEX vytvořil Donald E. Knuth pro publikace svých matematických prací. Předností tohoto systému jsou jeho schopnosti produkovat dokumenty na typograficky velmi vysoké úrovni, čímž značně převyšuje velkou vetšinu svých komerčních konkurentů. V současné verzi tohoto značkovacího jazyka lze kromě matematických publikací vytvářet dokumenty nejrůznějšího charakteru. Systém LATEX produkuje dokumenty s rozšířením .ps (PostScript) nebo z něj odvozený .pdf (Portable Document Format). Vstupem je naopak textový soubor .tex, který obsahuje kromě samotného textu práce také příkazy pro formátování dokumentu. Kompilátor tento soubor přeloží do souboru nezávislého na zobrazovacím zařízení .dvi (Device Independent). Ten se musí dále převést do souboru jednoho z výše zmíněných formátů. O průběhu překladu je uživatel informován na standardním výstupu nebo v logovém souboru. Systém TEX umožnuje připojovat různé balíky maker, které definují s výhodou použítelné předdefinované příkazy. Jedním z nich je i standardní balík pstricks využívající schopnosti PostScriptu pro práci s grafikou, který vytvořil Timothy Van Zandt.

14

Autor Leslie Lamport

4 METODIKA ŘEŠENÍ

4

24

Metodika řešení

V teoretické části byl čtenář seznámem s hlavními teoretickými podklady, které je nutné znát pro samotný vývoj aplikace. Dále byly po teoretické stránce přiblíženy některé metody, které budoucí aplikace bude aplikovat na modely. Při tvorbě aplikace je vhodné postupovat podle modelu systémového inženýrství životního cyklu vývoje aplikace, který má zároveň vliv na celkový tvar a sled metodiky řešení. Životní cyklus aplikace se podle klasického modelu dělí na části: požadavky – analýza požadavků – návrh – implementace – testování – provoz. Požadavky na aplikaci byly slovně definovány pracovníky Ústavu statistiky a operačního výzkumu PEF MENDELU v Brně a odpovídají cíli bakalářské práce. Analýza požadavků je klíčovým prvkem celého životního cyklu vývoje. Jejině správně analyzované požadavky zadavatele mohou vést k cíli podle jeho představ a lze se tak vyhnout pozdějším nepříjemnostem, kdy se reálný výsledek a původní představa z pohledu zadavatele vzájemně rozcházejí. Je nutné analyzovat veškeré potřeby budoucích uživatelů aplikace v závislosti na současném stavu problematiky a návyky uživatelů. Pro analýzu požadavků bude použit Use case diagram. Analýza poslouží jako výchozí bod pro návrh aplikace, kde je nutné navrhnout nejvhodnější strukturu uchovávaných dat a předběžný návrh uživatelského prostředí. Pro návrh datové struktury bude použit Class model. Kvalitním návrhem aplikace se lze vyhnout nepříjemnostem během implementace, které mohly být odhaleny už v analýze nebo návrhu. Jako implementační nástroj bylo zvoleno vývojové prostředí Delphi. Aplikace vytvořená v tomto prostředí nepotřebuje speciální programové vybavení. Verze Delphi 7 Personal Edition je navíc volně dostupná. Posledním kritériem pro volbu tohoto nástroje je autorova dřívější zkušenost s daným prostředím. V implementační části budou čtenáři přiblíženy nejdůležitější části programového kódu, který řeší stěžejní problematiky výsledné aplikace spolu s významnými principy, které byly při samotném programování aplikace řešeny. Nejprve bude popsána problematika grafické reprezentace grafu a práce uživatele s grafem v aplikaci, dále způsob ukládání grafu do souboru, způsob zpracování exportu do pdf souboru a nakonec bude popsáno API pro tvorbu DLL knihoven. Testování tvorby a editace modelů probíhalo už během vývoje aplikace a veškeré objevené nedostatky byly opraveny. Pro testování správného chodu knihoven obsahující grafové algoritmy bylo použito množství grafových modelů nejrůznějšího charakteru.

25

5 VLASTNÍ PRÁCE

5 5.1

Vlastní práce Analýza požadavků Use Case Diagram Tvorba pracovních formulářů

Tvorba grafu

<>

Načtení grafu

Import z mat. inc. <>

Editace vlastností prvků

<>

Editace rozmístění prvků

Editace grafu

Uživatel

Uložení grafu

Krokování řešení

<>

Aplikace algoritmu

TeXport řešení TeXport zadání <<Extend>> Student

Extension Points Texport dílčích kroků a komentář

Vyučující Přechod mezi formuláři

Obr. 6: Use case diagram aplikace (vytvořeno autorem)

Diagram vyjadřuje případy užití budoucí aplikace. Naznačuje chování systému, aniž by odhaloval jeho vnitřní strukturu (Kučerová, 2009). Je složen ze dvou druhů objektů a vazeb mezi nimi. Aktor (student a vyučující) je objekt, který se systémem (aplikací) přichází do kontaktu. Jednotlivé případy užití (use case) vyjadřují ucelené činnosti, se kterými může aktor přijít v aplikaci do kontaktu. Z diagramu je tedy patrné, že uživateli mohou být dva druhy aktérů, kteří mohou využít stejných případů užití, ale v některých případech s jiným cílem. Z definice požadavků pracovníků ÚSOP vyplývá, že aktor bude mít možnost vytvářet v jedné aplikaci více pracovních formulářů pro střídavou práci na několika grafech. Dále bude uživateli umožněno graf vytvořit manuálně pomocí elementárních grafických nástrojů nebo načtením z uloženého grafu v souboru. Graf lze i naimportovat z textového souboru, ve kterém bude definována matice incidence, přičemž prvky matice na řádku budou odděleny tabulátorem. Další případ užití nabízí editaci existujícího grafu, a to obnáší změnu rozložení uzlů na pracovním plátně nebo změny parametrů prvků. Všechny tyto změny lze dalším případem užití uložit do souboru. Use case (UC) Aplikace grafu nalezne řešení aplikovaného algoritmu, který získá z externích DLL knihoven. Další UC bude celý výsledek krokovat. Aplikace musí umožňovat

5.2 Návrh aplikace

26

exportovat zadání nebo i celé řešení jednotlivých krocích výpočtu vybraného algoritmu tak, aby byl vyexportovaný soubor snadno převeditelný do souboru s rozšířením pdf/ps. Samozřejmě musí být možno mezi jednotlivými rozpracovanými úkoly snadno přecházet.

5.2

Návrh aplikace

Uživatelské rozhraní V diagramu use case značí každé spojení mezi aktorem a dílčím use case vzájemnou interakci. Každý tento vztah musí být pomocí uživatelského rozhraní zprostředkován. Zároveň je jedním z definovaných cílů uživatelsky přívětivé rozhraní. Při tvorbě rozhraní lze s výhodou využít přístup označovaný MDI (Multi Document Interface). Spuštěním aplikace se otevře hlavní rámec maximalizovaný přes celou obrazovku. Zároveň se zajistí inicializace panelů nástrojů a panelu s nastavením. Nakonec další formulář nabídne uživateli volbu parametrů budoucího okna s plátnem, kde bude možno kreslit samotný graf, a po kladném potvrzení tohoto formuláře se vytvoří objekt s plátnem, který je podřízeným oknem hlavního rámce, tzv. MDIChild. Výsledné uživatelské rozhraní je zachyceno v příloze A. Další vytváření podřízených oken hlavního rámce bude umožněno v hlavní standardní nabídce programu spolu s možností otevírání, importu, ukládání, exportu grafu a dalšími funkcemi. Panel Nástroje nabídne základní grafické nástroje pro práci s grafem, a to: Uzel, Hrana, Pohyb, Mazání. Po aplikaci metody na graf tento panel zpřístupní tlačítka pro pohyb řešením algoritmu. Na panelu Vlastnosti bude moci uživatel měnit vlastnosti grafu a jeho prvků. Celý panel se dělí na čtyři záložky – Uzel, Hrana, Graf, Metody. První dvě záložky jsou rozhraní pro změnu parametrů vybraných prvků, v záložce Grafy lze rozhodnout o orientaci a ohodnocení grafu. Poslední záložka Metody nabídne uživateli seznam načtených algoritmů s možností použití. Zvolená reprezentace grafu Reprezentace grafu bude koncipována pomocí dvou dynamických spojových struktur s využitím objektově orientovaného přístupu. Každý prvek strukury je ukazatel odkazující na objekt třídy TUzel nebo THrana. Každý takový objekt současně obsahuje atribut, který značí dalšího člena v seznamu. Je tak zajištěna snadná rozšiřitelnost množiny hran či uzlů. Vzniká otázka, jak vyřešit vzájemné vztahy uzlů a hran. Jak vyplývá z definice hrany, existuje vždy právě dvojice uzlů, které hrana spojuje. Třída THrana tedy navíc obsahuje dva 4B ukazatele na objekt uzlu počátečního a koncového. Tím je zajištěn snadný přechod mezi těmito prvky grafu.

27

5.2 Návrh aplikace

Class Diagram THlavniRozhrani

TFormular

-MDI : array of TFormular

-graf : TGraf -reseni : TKrokGraf

+inicializaceMDI()

+inicializaceGrafu() +nactiGraf() +ulozGraf()

TUzel -id : Word -oznaceni -stred : TPoint -polomer : Byte

TObecnyGraf +pridejHranu() +pridejUzel() +odeberHranu() +odeberUzel()

TGraf THrana

+init()

-id : Word -nazev : String -ohodnoceni : Integer -pocUzel : TUkUzel -konUzel : TUkUzel -attribute

-seznamUzlu : Pointer -seznamHran : Pointer -orientovany : Boolean -ohodnoceny : Boolean +init() +kresliUzel() +kresliHranu()

TKrokGraf -docasneU : Pointer -trvaleU : Pointer -tocasneH : Pointer -trvaleH : Pointer -komentar : String +init()

+init()

TCPMHrana -optim : Integer -mod : Integer -pesim : Integer TCPMUzel -NMZ : Integer -NPK : Integer +init()

+init()

TCPMGraf -seznamCPMUzlu : Pointer -seznamCPMHran : Pointer +init()

TKrokCPMGraf -docasneCPMU : Pointer -trvaleCPMU : Pointer -docasneCPMH : Pointer -trvaleCPMH : Pointer +init()

Obr. 7: Class diagram analytických tříd aplikace (vytvořeno autorem)

Datové struktury Na základě požadavků na aplikaci byla UML diagramem pomocí analytických tříd navržena zjednodušená datová struktura programu. Třída THlavniRozhrani reprezentuje hlavní rámec aplikace. Z důvodů přehlednosti byly vypuštěny méně podstatné formulářové třídy. THlavniRozhrani obsahuje kolekci objektů třídy TFormular. V každém objektu třídy TFormular je po celou dobu existence formuláře zakomponován objekt třídy TGraf obsahující lineární seznamy uzlů a hran. TGraf zajišťuje veškeré operace s vykreslováním grafu. TGraf dědí z abstraktní třídy TObecnyGraf přikazující každému potomkovi implementovat metody pro přidávání a odebírání prvků grafu. Objekt třídy TUzel a THrana uchovává své ID pro jednoznačnou identifikaci. I když bude možno každý objekt bezpečně rozeznat ukazatelem, je použití ID v aplikaci nezbytné ještě z jiného důvodu15 . Dále uzel musí obsahovat své označení a parametry nutné pro vykreslování – střed a poloměr. Hrana mj. uchovává svůj název, ohodnocení a ukazatele na počáteční a koncové uzly. Z TGraf dědí TCPMGraf určená pro použití v případě, že uživatel bude zpracovávat graf pro metody CPM nebo PERT, které pro prvky grafu vyžadují ještě další atributy. Proto i TUzel a THrana mají své potomky TCPMUzel, resp. TCPMHrana. 15

Pro identifikaci vykreslené hrany na plátně v závislosti na její barvě (viz níže).

5.3 Organizace kódu

28

Druhou třídou dědící z obecného grafu je TKrokUzel. Jak už název napovídá, bude základním kamenem pro realizaci krokování algoritmu. Od této třídy je z výše zmíněných důvodů odvozená TKrokCMPUzel. Bližšímu seznámení s krokováním řešení bude v práci věnována samostatná část.

5.3

Organizace kódu

Při tvorbě aplikace byl zdrojový kód pro přehlednost rozdělen do několika modulů. Každá třída, včetně formulářových, je oddělena do jednotlivých modulů (unity), až na rodinu grafových tříd. Dále byly vytvořeny moduly, které jsou pouze množinou metod a zabezpečují zejména vstupně/výstupní funkcionalitu.

5.4

Implementace rozhraní

Programový kód, který implementuje vizuální podobu uživatelského rozhraní není třeba nastavit manulálně, ale RAD nástrojem. Tím lze snadno a rychle vytvořit všechny dílčí formuláře aplikace. Kromě výchozí podoby oken však není nijak zajištěna správná inicializace ostatních ani reakce na události všech formulářů. Implementace MDI Základem aplikace je hlavní formulář, v samotném kódu označovaný jako FrmHlavni, který má tvořit hlavní rám MDI aplikace. Ve vývojovém prostředí Delphi se MDI rozhraní implementuje nastavením hodnoty vlastnosti formulářového okna nazývané FormStyle. Klasický formulář má tuto hodnotu nastavenou na fsNormal. U rodičovského se vlastnost FormStyle nastavuje na hodnotu fsMDIForm, u podřízeného fsMDIChild. Ve zdrojovém kódu jsou dceřinné formuláře třídy TFrmPotomek. Následuje zjednodušená ukázka implementace: procedure TFrmHlavni.FormCreate(Sender: TObject); begin FrmHlavni.FormStyle := fsMDIForm; end; procedure TFrmHlavni. NovyPotomek(Nazev: String; RozmeryPlatna: TPoint); begin // nastaveni noveho formulare jako potomka MDI Potomci.Add(TFrmPotomek.Create(Application)); TFrmPotomek(Potomci.Last).FormStyle := fsMDIChild; end;

5.4 Implementace rozhraní

29

První metoda volána při vytváření rámce, druhá je volána, pokud je třeba vytvořit novou instanci dceřinného okna.16 Ihned po vytvoření rámce je nutné, aby byly volány metody zajišťující inicializaci formulářů s nástroji a vlastnostmi grafu. Tyto formuláře ale musí zůstat po celou dobu běhu aplikace v popředí, žádné podřízené okno rámce je nesmí překrýt, aby byly jejich funkce stále k dispozici. To lze zajistit opět změnou hodnoty vlastnosti FormStyle příslušných formulářů na fsStayOnTop. Následující metoda zajišťuje vytvoření panelu nástrojů: procedure TFrmHlavni.NovyNastroje; begin Nastroje := TFrmNastroje.Create(Application); Nastroje.FormStyle := fsStayOnTop; Nastroje.Top := 60; Nastroje.Left := 20; end; Analogicky je implementováno i vytvoření formuláře (s ukázkou v příloze A), který nabídne nastavení budoucího pracovního okna. Až s kladným potvrzením tohoto dialogového okna dojde k inicializaci pracovního MDI potomka třídy TFrmPotomek – příloha B. Pracovní formulář Okno s pracovní plochou pro tvorbu grafu obsahuje několik nezbytných komponent. Nejdůletižejší komponentou je TImage v aplikaci nazvaná Platno. Tato standardní komponenta knihovny VCL je určena pro zobrazovaní grafiky, zejména obrázků. Lze na ní ale i s výhodou kreslit pomocí vykreslovacích primitiv, které TImage nabízí. Vykreslovat ale lze i bez použití TImage, a to přímo na pozadí formuláře pomocí vlastnosti Canvas. Tento způsob je ale v podstatě nepoužitelný, protože na rozdíl od TImage zde není zajištěno opakované překreslovaní, např. při posunu jiného formuláře přes spuštěnou aplikaci. Většinu okna tedy zaujímá komponenta TImage, dále se zde nachází komponenta TMemo. Své uplatnění nalezne při zobrazování komentáře krokovaného řešení. Poslední významnou komponentou je TStatusBar. Informuje uživatele o důležitých skutečnostech. Takto vybavené pracovní okno nutno dále upravit. Při nemaximalizovaných rozměrech podřízeného MDI okna je plátno nastaveno na celou plochu (kromě prostoru pro komentáře a stavový řádek), avšak při maximalizaci okna je podle dříve definovaných rozměrů vycentrována na střed obrazovky. To lze zajistit odchycením zprávy WM SYSCOMMAND17 vznikající při kliku na tlačítka v titulní liště podřízeného Metoda NovyPotomek obsahuje parametry pro nastavení názvu vytvářeného formuláře a jeho vnitřních rozměrů (resp. pracovní plochy). Zpracování těchto parametrů již není součátí ukázky. 17 Zdroj: http://delphi.about.com/od/delphitips2007/qt/sc_restore.htm 16

5.4 Implementace rozhraní

30

okna. V metodě zpracovávající tuto zprávu lze pak libovolně ošetřit chování aplikace. Princip zpracování této zprávy je účelově zjednodušen v následujícím pseudokódu: CASE zpráva OF Minimalizování: BEGIN Nastav hodnotu WindowState na wsMinimized; Hodnotu Result dané zprávy nastav na 0; END; Maximalizování: BEGIN Nastav hodnotu WindowState na wsMaximized; Velikost okna nastav na roměry obrazovky; IF oba rozměry plátna > rozměry okna THEN BEGIN Posuň plátno do levého horního rohu; END ELSE IF výška plátna > výška okna THEN BEGIN Vycentruj plátno horizontálně; END ELSE IF šířka plátna > šířka okna THEN BEGIN Vycentruj plátno vertikálně; END ELSE BEGIN Vycentruj plátno vertikálně; Vycentruj plátno horizontálně; END Šířku komentářového pole přizpůsob šířce plátna; Koment. pole posuň přesně pod plátno; Hodnotu Result dané zprávy nastav na 0; END; Zmenšení: BEGIN Nastav hodnotu WindowState na wsNormal; Rozměry okna nastav na rozměry před zvětšením; Plátno posuň do levého horního rohu; Koment. pole posuň přesně pod plátno; Hodnotu Result dané zprávy nastav na 0; END; Pokud při práci s programem nastane situace, že uživatel zmenší pracovní okno, pravděpodobně se tím stavový řádek odsune mimo zobrazení. Ten ale můsí být viditelný vždy. Je třeba zajistit, aby se stavový řádek posouval s pohybem posuvníku tak, aby zůstával stále na dolním okraji okna. Standardně neexistuje v Delphi událost vznikající při pohybu posuvníku. Ošetřit toto chování lze opět odchytem systémových správ, konkrétně WM VSCROLL (vertikální posuvník) a WM HSCROLL (horizontální posuvník)18 . Zbývá už jen implementovat metody, které se provedou vždy při vzniku výše zmíněných zpráv. Jako ukázka je přiblížena metoda, která se spouští při pohybu vertikálního posuvníku pracovního okna. 18

Zdroj: http://www.tek-tips.com/viewthread.cfm?qid=1409264&page=29

5.5 Implementace struktur

31

procedure TFrmPotomek.WMVScroll(var Msg : TMessage); begin inherited; StavovyRadek.Top := ClientHeight - StavovyRadek.Height; StavovyRadek.Left := 0; StavovyRadek.Width := ClientWidth; end; Nakonec zbývá upravit chování MDIChild (pracovního formuláře) při zavírání okna. Běžně se totiž podřízená MDI okna při stisknutí křížku pro uzavření pouze minimalizují do levého dolního rohu rámce. Proto je třeba do metody FormClose podřízeného okna vepsat kód: Action := caFree; a takto upravené okno se bude vždy zavírat klasickým způsobem.

5.5

Implementace struktur

Implementace dynamických struktur tvoří součást třídy TGraf. Je uchováván ukazatel na začátek (FPocUzel) a konec (FKonUzel) seznamu. Nový prvek se připojuje vždy na konec. Přidávání prvků zajišťují metody PridejUzel a PridejHranu. Celý jejich kód je součástí přílohy C. Odebírání prvků ze struktury lze uplatnit podle potřeby v jakékoli části seznamu. K tomu slouží metody OdeberUzel a OdeberHranu. Druhá zmiňovaná procedura je přetížená. Jejich jméno i účel je stejný, liší se jen v parametrech. Lze tuto metodu zavolat s parametrem, který odkazuje přímo na odebíranou hranu, nebo s ukazatelem na odebíraný uzel, pak musí být z paměti odstraněny všechny hrany, které s odebraným uzlem incidují. Jak je patrné v kódu v příloze, při vytváření nového člena v seznamu je inicializován příslušný objekt pomocí konstruktoru Init obsahující parametry nezbytné pro prvotní existenci objektu. Aby byla dodržena zapouzdřenost objektů, mají objekty pro každý atribut zmiňovaný v části Datové struktury tzv. get/set metody. Jediný atribut Dalsi (ukazatel na další prvek) je deklarován v části public pro rychlý přístup při procházení seznamu. Takto realizované struktury jsou svým rozsahem limitované jen velikostí operační paměti. V této aplikaci je tento počet shora omezený ještě jedním kritériem. Pro oba seznamy je uchováván počet jejich prvků datového typu Word. Zaujímá 2 B, kterými lze vyjádřit 216 = 65536 možností. Reprezentuje nezáporná čísla, tedy včetně nuly, jeho rozsah je 0–65535. Počet prvků množiny uzlů i hran je tedy omezen hodnotou 65535. Protože je aplikace tvořena jako učební pomůcka, nepředpokládá se, že by toto omezení budoucí výstup nějak limitovalo.

5.6

Princip překreslování a práce nad plátnem

Veškeré zobrazování grafu bude probíhat na komponentě TImage pracovního formuláře. V aplikaci je objekt této třídy pojmenován Platno. Příloha B ukazuje, že

5.6 Princip překreslování a práce nad plátnem

32

kromě stavového řádku a prostoru pro komentář je plátno rozprostřeno po celé ploše okna. Překreslování Vykreslování uzlů a hran se zabývájí kapitoly níže. Nejdříve je nutné se seznámit s principem, díky kterému lze plynule pohybovat s uzly grafu po plátně. Vše závisí na činnosti myši nad plátnem. Vzniká tak celá řada událostí, které lze s výhodou využít. V tomto případě byly stěžejní události spojené se stiskem levého tlačítka, pohybem myši a uvolněním levého tlačítka myši (OnMouseDown, OnMouseMove, OnMouseUp). Při vyvolání jedné z událostí je spuštěna některá z odpovídajících metod: PlatnoMouseDown, PlatnoMouseMove, PlatnoMouseUp. Příliš rozsáhlý kód těchto metod zůstane jen jako součást hmotné přílohy a v tomto textu je příblížen pseudokód všech tří metod v příloze D, E a F. Kód je rozdělen v závislosti na zvoleném režimu. Ovšem hned na začátku metod je nutno rozlišovat, zda bylo stisknuto správné tlačítko. Stisk pravého tlačítka, bude mít svoji funkci pouze, pokud překrývající uzel bude chtít uživatel smazat. Ostatní funkce budou způsobeny stiskem levého tlačítka. Ověření stisku toho správného má podobu porovnání parametru metody Button, a to s konstantou mbLeft, resp. mbRight. Veškeré činnosti, které ovlivňují podobu znázorněného grafu, jsou iniciovány až se stiskem tlačítka myši. Bez stisku tlačítka pohyb myši po plátně neprovede žádné změny grafu. Samotný princip posunu je realizován v metodě vyvolané při pohybu myši. Prvek, který je v pohybu, je hned na začátku procedury překreslen, poté je zaznamenána aktuální pozice prvku. Nakonec je vykreslen v nové pozici. Událost OnMouseMove je volána s každým sebemenším pohybem myši. Vzniká tak iluze plynulého posunu. Režimy práce nad plátnem Překreslování je současně spojeno s aktuálním režimem, ve kterém uživatel pracuje s aplikací. Ty jsou implementovány jako výčtový typ v definici typů příslušného modulu. V metodách reagujících na události myši je jejich činnost ovlivlivněna právě aktuálně zvoleným režimem. Je pochopitelné, že například při návrhu hran a posunu uzlů dělá aplikace dva rozdílné úkony, stále je ale operačním systémem vyvolána stejná událost – pohyb myši. V režimu Uzel se kliknutím levého tlačítka na plochu plátna vytvoří uzel se střed v daném místě a implicitně nastaveným poloměrem 15 px. Tažením myši při státe stisknutém tlačítku se právě vytvořený uzel bude posouvat spolu s myší. Druhý režim Hrana slouží pro vytváření hran. Stiskem levého tlačítka nad počátečním uzlem a uvolněním nad koncovým vznikne hrana spojující tyto dva uzly.

5.7 Implementace vykreslování prvků

33

Pro změnu rozmístění prvků grafu a změnu jejich parametrů je třeba aktivovat režím Pohyb. Klikem na uzel a jeho tažením lze uzly libovolně posouvat. Hrany budou uzly vždy následovat. Kliknutím na prvek grafu v režimu Mazání dojde k odstranení tohoto prvku z plátna i paměti. Kromě čtyř uživatelem volitelných režimů aplikace pracuje ještě s pátým režimem – Překrývání. Ten je aktivován automaticky, pokud se uživatel pokusí vytvořit uzel nad již vytvořeným uzlem a hrozilo by tak jejich překrytí. Překrývající uzel získá inverzní barvu překrývaného a opětovným stiskem ho lze v plátně umístit až na volném místě nebo pravým tlačítkem odstranit.

5.7

Implementace vykreslování prvků

Vykreslování uzlů Kreslení uzlů zajišťuje procedura KresliUzel, viz kód níže. Parametry metody jsou plátno, kam se má uzel vykreslovat, ukazatel na vykreslovaný uzel a barva výplně. Kreslí se na plátno pomocí vlastnosti Canvas a procedury Ellipse. Procedure NastavBarvu nastaví barvu pera podle značky, kterou má daný uzel19 . Do procedury Ellipse vstupují parametry udávající levý horní a pravý dolní roh obdélníku, kam bude vepsána elipsa. Metoda VratVrchol vrací souřadnice rohů v závislosti na poloměru a středu uzlu. procedure TGraf.KresliUzel(var Platno: TImage; UkNaUzel: TUkUzel; BarVyplne: TColor); begin with Platno.Canvas do begin //nastavení barvy pera podle značky prvku NastavBarvu(Platno, UkNaUzel^.VratZnacku); //samotné vykreslení kružnice Ellipse(UkNaUzel^.VratVrchol1.X, UkNaUzel^.VratVrchol1.Y, UkNaUzel^.VratVrchol2.X, UkNaUzel^.VratVrchol2.Y); end; end; Vykreslování hran Ve srovnání s uzly je implementace kreslení hran složitější. Procedura pro kreslení hrany (KresliHranu) je několikrát přetížená. Musí být zajištěno kreslení jak klasických hran v podobě přímek, tak násobných hran (křivky). Znázornění hrany v podobě přímky probíhá pomocí kódu: Značky spojeny s řešením algoritmu, behem kterého mohou prvky grafu nabývat dočasných a trvalých značek nebo mohou být bez značky. 19

5.7 Implementace vykreslování prvků

34

With Platno.Canvas do begin MoveTo(Odkud.X, Odkud.Y); LineTo(Kam.X, Kam.Y); end; Pokud dva uzly spojuje přímo více než jedna hrana, jedná se o násobné hrany a je nutno je vykreslit tak, aby se nepřekrývaly, tedy vykreslit jako křivky. To zajišťuje standardní metoda PolyBezier vykreslující beziérovku křivku na základě souřadnic vrcholů řídícího polygonu křivky. Mějmě hranu (beziérovu křivku) mezi dvěma vodorovně znázorněnými uzly. Řídíci body P 1 a P 2 se v horizontálním směru nachází ve 25 a 75 % vzdálenosti mezi uzly. Vertikální vzdálenost od středů uzlů je 30 px (v případě potřeby se tato hodnota násobí). Vertikální vzdálenost lze chápat jako normálový vektor k pomyslné přímce spojující středy dvou uzlů. Pokud je tedy třeba vytvořit novou křivku, která je zaoblená zrcadlově, stačí pouze normálový vektor vypočítat pro opačný směr, tedy změnit znaménka normálových hodnot. Následující dva řádky kódu přibližují výpočet (řídícího bodu) normálových vektorů v různých směrech20 : RidiciBod := Point(Odkud.X + X - Normal.Y, Odkud.Y + Y + Normal.X); RidiciBod := Point(Odkud.X + X + Normal.Y, Odkud.Y + Y - Normal.X); Umístění ohodnocení hran Rozhodne-li se uživatel pracovat s ohodnoceným grafem, je nutné, aby každá hrana byla jasně označena svým ohodnocením. To do plátna vypisuje standardní procedura vlastnosti Canvas komponenty TImage – TextOut. Text musí být umístěn na hraně, právě uprostřed. V případě, že je hrana tvořena přímkou, není nalezení takového bodu složité. Jakmile se hrana začne vykreslovat jako křivka, je třeba nalézt efektivním způsobem extrémní bod křivky. K tomu lze s výhodou využít rekurzivní algoritmus de Casteljau pro výpočet beziérovy křivky. V tomto případě není použit pro samotné vykreslování, ale pro nalezení kýženého bodu na křivce. Za parametr t byla dosazena hodnota 1/2, jak znázorňuje i obrázek 4. Je tak zajištěno, že hodnota Q(t) bude udávat vždy extrém křivky, kterou určují vrcholy řídícího polygonu Pi . Postup, jak metoda v programu zjišťuje bod Q(t), je znázorněn na obrázku 5, kde Q(t) = P3,3 , což je právě bod, kde se umístí střed textového pole s ohodnocením dané hrany (křivky). Umístění šipky hrany V případě práce s orientovaným grafem, musí být součástí hrany šipka (rovnoramenný trojúhelník) přiléhající ke koncovému uzlu. V Delphi slouží k vykreslování 20

X a Y je posunutí.

35

5.7 Implementace vykreslování prvků

trojúhelníku metoda Polygon, kde počet souřadnic v parametu určuje počet vrcholů polygonu. Šipka hrany, kde hrana má tvar křivky, se otáčí v závoslosti na bodech řídícího polygonu křivky. Pokud by se dle obrázku 4 vykreslovala šipka k bodu P0 , otáčela by se špička šipky A kolem uzlu podle bodu P1 , vrcholy podstavy A a B podle bodu P2 . Použitím obou řídících bodů je dosaženo přesnějšího přiléhaní šipky k hraně. Konkrétně poloha řídícího bodu RB ovlivňuje úhel α (obrázek 8). Algoritmus zjišťuje úhel α na základě vztahu sin α oY α = arctan(tan(α)) = arctan = arctan cos α oX 







kde oY a oX je rozdíl mezi souřadnicemi řídícího bodu a bodu A na osách x, resp. y (viz obrázek 8). Dle hodnoty α se dopočítávají souřadnice vrcholů šipky. Nutno poznamenat, že se zde pracuje s kartézskou soustavou převrácenou podle osy x21 . x oX

RB α

oY

y

C A

B

Obr. 8: Umístění šipky hrany (vytvořeno autorem)

Dle kvadrantů je hodnota α navyšována o π, jak demonstruje následující kód. if oX > Alpha else if Alpha else Alpha

0 then := ArcTan(oY/oX) + Pi oY > 0 then := ArcTan(oY/oX) + Pi + Pi := ArcTan(oY/oX);

Souřadnice bodů C se zjišťují kódem, který následuje. Proměnná Alpha2 reprezentuje úhel, který svírá strana b s přímkou mezi body A a RB. V případě výpočtu bodu B se Alpha2 odčítá. C.X := Round(StranaB * Cos(Alpha + Alpha2); C.Y := Round(StranaB * Sin(Alpha + Alpha2); 21

hodnoty na ose y rostou směrem dolů.

5.8 Indetifikace prvků na plátně

5.8

36

Indetifikace prvků na plátně

Rozpoznávání uzlů Rozpoznání uzlů je jednoduše vyřešeno tak, že při kliknutí myši do plátna se porovná vzdálenost (přepona) aktuálně označeného bodu se středy všech uzlů pomocí Pythagorovy věty. Uzel, který se od aktuálního bodu nachází blíže než jeho poloměr, byl označen kliknutím. Na stejném principu pracuje i ochrana proti vzájemnému překrývání uzlů. Jestliže by další posunutí uzlu způsobilo, že součet jejich poloměrů by byl větší než vzdálenost jejich středů, posunutí se neuskuteční. Rozpoznávání hran Při implementaci rozpoznávání hran mírnou paměťovou složitost vyváží nízká složitost výpočetní. Elegantní řešení spočívá v implementaci skrytého druhého plátna třídy TImage rozměrově kopírující plátno, kde bude pracovat uživatel. Na skryté plátno se, jak mj. naznačuje pseudokód v příloze F, znovu vykreslují hrany, ale tak, aby bylo indentifikovatelné jejich ID. Na skrytém plátně se jednotlivé hrany musí vykreslovat barvou, která odpovídá ID hrany. Kód metody IDNaBarvu demonstruje, jak převod ID na barvu funguje. Standardní funkce RGB vrací barvu na základě tří číselných hodnot v parametrech udávající množství červené (Red), zelené (Green), modré (Blue) v intervalu 0-256. Protože je spojový seznam hran omezen hodnotou 65535, postačí zpracovávát jen dva parametry (2562 = 65536). To přesně postačí ještě pro okolní barvu plátna – černou (0,0,0)22 . function TGraf.IDNaBarvu(IDHrany: Word): TColor; begin Result := RGB(0, IDHrany div 255, IDHrany mod 256); end; Kliknutím uživatele do plátna se nejprve testuje, zda neklikl na uzel. Pokud ne, zjistí se barva, která se vyskytuje na skrytém plátně na stejném pixelu. Z této barvy vrátí funkce BarvaNaID ID hrany, na kterou bylo kliknuto. function TGraf.BarvaNaID(Barva: TColor): Word; begin Result := GetGValue(Barva) * 256 + GetBValue(Barva); end; 22

ID první vytvořené hrany je vždy 1, tedy (0,0,1).

5.9 Vstup a výstup

5.9

37

Vstup a výstup

Jakýkoli graf vytvořený v prostředí aplikace může uživatel v případě potřeby uložit do textového souboru. Ukázka obsahu souboru s grafem je v příloze G. Údaje o grafu se dělí do několika částí. První je Platno, kde jsou uloženy rozměry pracovního plátna v pixelech. Následuje sekce Graf uchovávající údaje o orientaci a ohodnocení grafu vyjádřené v binární soustavě. Dále v části Uzel je výčet množiny všech uzlů, kde jsou reprezentovány svým označením. Tento text se bude objevovat jako text uvnitř uzlů. Ovšem jeho délka nesmí přesahovat tři znaky. Oblast Hrany definuje hrany specifikací počátečního a koncového uzlu zápisem pocateční: koncový(ohodnocení), přičemž se uzly neoznačují názvem, ale jejich pořadím ve výčtu části Uzly. Další hrany se stejným počátečním uzlem lze zapsat na jeden řádek pouze další definicí koncového uzlu a ohodnocení hrany. Posledním oddílem této struktury je Grafika obsahující data o grafické intepretaci uloženého grafu ve tvaru počáteční: (osaX, oxaY, poloměr). Jedná se o volitelnou část. Pokud bude soubor s grafem tvořen ručně, lze tuto část vynechat. Uzly pak budou po plátně rozmístěny náhodně s poloměrem 15 px. Čtení i ukládání dat do souboru je implementováno samostatnými moduly, které byly připojeny k aplikaci. V případě ukládání se jedná o sekvenční zápis údajů do souboru. Při čtení ze souboru existuje mimo klasických výjimek při práci se soubory také výrazné riziko, že samotná struktura a obsah souboru nebude dle vymezených pravidel. Pro ověření správné podoby jednotlivých řádků bylo využito regulárních výrazů. Delphi a jazyk OP však nedisponují těmito prostředky. Proto byla vyvinuta volně dostupná knihovna pcre.dll23 umožňující práci s regulárními výrazy v prostředí Delphi. Knihovna s regulárními výrazy se do projektu přidává prostřednictvím přiloženého modulu PerlRegEx.pas. Dále je nutné inicializovat objekt (zde pojmenovaný RegEx), který je těžištěm práce s reg. výrazy. V modulu pro načítání grafu ze souboru byla implementována metoda Porovnej, kde je zpracováno ověření, zda zkoumaný text vyhovuje masce. Kód metody vypadá takto: function Porovnej: Boolean; begin RegEx.Subject := ZdrojovyRadek; // zkoumany retezec RegEx.RegEx := Maska; // maska if RegEx.Match then Result := True // porovnani else Result := False; end; Tato metoda najde své uplatnění pro ověřování tvaru vstupního řádku v každé sekci struktury souboru. Pro ukázku je zde uvedeno použití nejprve pro ověření správné podoby vstupního řádku v sekci Uzly a na dalším řádku ověření pro sekci Hrany. 23

Dostupná na: http://www.regular-expressions.info/delphi.html.

5.10 Komunikace s knihovnou a krokování řešení

38

if Porovnej(’^ *\(\w{1,3}(;\w{1,3})*\)’, Radek) then ...; while Porovnej(’^ *[0-9]+: +[0-9]+\([0-9]+\) ( +[0-9]+\([0-9]+\))+’, Radek) do ...; V prvním případě Porovnej porovnává načtený řádek s maskou, která říká, že na začátku může být libovolně mezer, poté musí následovat závorka, ve které musí být alespoň jeden uzel označený 1–3 znaky a dále může následovat libovolný počet uzlů oddělených středníkem a na konci uzavření závorky. Analogicky je sestavena i druhá maska, kde se ověřují čísla počátečního a koncového uzlu, přičemž koncových může být 1–n.

5.10

Komunikace s knihovnou a krokování řešení

Knihovna a jeji API Při přibližování problematiky DLL v sekci 3.7 nebyla zmíněna ještě jedna užitečná schopnost DLL. Není totiž nezbytné, aby byly připojovány při startu aplikace, ale mohou být „linkoványÿ explicitně kdykoli během chodu hlavní aplikace a zároveň kdykoli odpojeny. Zbytečně tak nejsou zahlcovány systémové prostředky vyžadované knihovnou v době, kdy není využívána. Navíc může aplikace přepínat knihovny v podobě grafových algoritmů dle potřeby. V prostředí Delphi a jazyku Object Pascal je připojování za běhu aplikace zajištěno standardní funkcí LoadLibrary(Name: AnsiString):TLibHandle. Ta vrací Handle na příslušnou knihovnu, v případě neúspěchu je návratová hodnota 0. Dále je nutné zjistit správnou metodu v knihovně, a to funkcí, která na ni vrací ukazatel a v případě neúspěchu vrací nil : GetProcAddress(Lib: TLibHandle; ProcName: AnsiString):Pointer. Návratová hodnota je pak přiřazena proměnné datového typu funkce (procedura). Tento datový typ musí přesně odpovídat deklaraci metody (počet parametrů a jejich typy) z knihovny. Zavoláním této proměnné je vykonán kód metody v knihovně. Na závěr je nutné dynamickou knihovnu odpojit funkcí FreeLibrary(Lib: TLibHandle):Boolean. Následuje ukázka implementace připojení dynamické knihovny, provedení její metody a následné odpojení knihovny. interface // definice datového typu odpovídající metodě v knihovně type DLLFuncRes = procedure(Graf, Pocatecni, Koncovy: Pointer, var Vystup: Pointer); ... implementation procedure TFrmHlavni.NajdiReseni; // deklarace prom. Metoda nového dat. typu var Metoda: DLLFuncRes; ... begin

5.10 Komunikace s knihovnou a krokování řešení

39

try HandleReseni := LoadLibrary(PChar(Knihovna)); if HandleReseni = 0 then raise EDLLLoadError.Create(’Chyba při práci s knihovnou.’) else begin @Metoda := GetProcAddress(HandleReseni, PChar(’Reseni’)); if @Metoda <> nil then begin Metoda(Pointer(UkGraf), Pointer(Pocatecni), Pointer(Koncovy), Pointer(UkReseni)); end; end; finally FreeLibrary(HandleReseni); end; end; Stále je ale nutné vyřešit, jakým způsobem zajistit komunikaci programu s knihovnami a jak zajistit krokování výsledného řešení. Aplikace komunikuje s knihovnami na základě navrženého API24 . Toto API (příloha H) musí respektovat každá později navržená knihovna, jinak ji hlavní aplikace vůbec nenačte. Spolupráce hlavního programu a knihoven funguje tak, že při startu aplikace se otestují všechny dostupné knihovny ve složce .\Libraries na přítomnost všech metod definovaných v API. Dalších metod může obsahovat libovolný počet. U knihoven, které vyhoví tomuto ověření, se zavolá hlavním programem metoda Info, která vrací název zpracovávaného algoritmu. Označení tohoto algoritmu se následně objeví ve výčtu grafových algoritmů, kde má uživatel na výběr, který algorimus aplikovat. Zaroveň se vytvoří seznam vyhovujících knihoven. Přítomnost všech metod v knihovně je nezbytná. Výběrem uživatele jakéhokoli grafového algoritmu se nejprve porovnají vlastnosti aktuálního grafu s hodnotami, které vrací jednotlivé metody z API, aby bylo zajištěno, že na aktuální graf lze vybraný algoritmus aplikovat. Nejsou-li aktuální vlastnosti grafu v souladu s požadavky knihovny, algoritmus se na graf neaplikuje a uživatel je aplikací vyzván, aby provedl potřebné změny. Volání metod API hlavním programem pracuje na stejném principu, jako volání knihovní metody Reseni, jejíž zkrácený zdrojový kód je uveden výše. Mění se pouze definice datového typu metody a druhý parametr metody GetProcedureAdress, tedy název volané knihovní metody. Krokování řešení Návratovou hodnotu předá knihovní metoda Reseni do svého posledního parametru. Konkrétně se jedná opět o spojový seznam objektů, nyní třídy TKrokGraf. Prvky reprezentují jednotlivé kroky řešení. Jak je patrné z obrázku 7, obsahují objekty této 24

Application Programming Interface – sbírka procedur a funkcí knihovny

5.11 Export grafu

40

třídy kromě podpůrných metod hlavně atributy, které jsou seznamy obsahující ukazatele na prvky zpracovávaného grafu. Jedna skupina atributů reprezentuje dočasné prvky, druhá trvalé. Tím, že objekt uchovává pouze ukazatele na části zpracovávaného grafu, je zajištěna minimální velikost řešení uchovávaného v paměti. Obecná struktura článku seznamu v jednom objektu (kroku) pro uchování ukazatele na prvek grafu je: PrvekSeznamu = record PrvekGrafu: Pointer; DalsiVSeznamu: ^PrvekSeznamu; end; Pohyb řešením je pak implementován pouhým posunem ve spojovém seznamu objektů jednotlivých kroků. Jakmile proběhne posun na jiný krok, projdou se postupně spojové seznamy v objektu s ukazateli na prvky grafu a podle příslušnosti prvku v daném spojovém seznamu (v podobě ukazatele) se změní značka konkrétního prvku grafu, což při překreslení zajistí i změnu barvy. Poté dojde i ke změně komentáře pod plátnem, který uchovával nový krok. Kód knihovny Obsah knihovny zpracovávající grafový algoritmus je kromě dodržení API zcela na libovůli programátora. Kromě nezbytných metod pro komunikaci s hlavní aplikací lze dále použít v kódu neomezený počet jiných procedur i funkcí. Pokud však hlavní aplikace zavolá knihovní metodu Reseni, musí v posledním parametru metody být řešení algoritmu v podobě spojového seznamu, kde prvky jsou jednotlivé kroky řešení. Do každé knihovny ale musí být připojeny moduly zdrojUzel, zdrojHrana, zdrojGraf, zdrojZnackyVycet, aby bylo možno v knihovně pracovat s grafem. Zdrojový kód knihoven nc.dll (nejkratší cesta) byl vytvořen v souladu s postupem popisovaným v teoretické části práce. Princip hledání minimální kostry grafu (kg.dll) není příliš složitý, a tak je zbytečné se konkrétním obsahem knihoven zabývat.

5.11

Export grafu

Dle požadavků pracovníků ÚSOV má být navíc v aplikaci zpracován export vytvořeného grafu nebo celého řešení takovým způsobem, aby umožňoval snadnou tvorbu prezentačních materiálů do výuky nebo přípravu zadání zápočtového testu, nejlépe v podobě PDF souborů. K tomuto účelu byl využit systém LATEX a jeho rozšiřující makra, konkrétně balíky pstricks a pst-node. První zmiňovaný je základní balík maker celého systému PSTricks. Makra této rodiny umožňují nejrozmanitější práci s grafikou v systému

5.11 Export grafu

41

TEX/LATEX díky možnostem PostScriptu. Druhý balík (pst-node) jsou připravené příkazy pro práci s grafy25 . Výstupem aplikace bude textový soubor s příponou .tex obsahující příkazy systému LATEX a zmiňovaných balíků maker. Uživatel pak jen daný soubor přeloží například pomocí služby webového serveru univerzity http://tex.mendelu.cz. Pokud upřednostňuje lokální zpracování překladu, může využít překladače například v distribuci TeXLive26 . Nelze však přímo vygenerovat PDF soubor, ale soubor s příponou .ps (PostScript), protože příkazy PSTricks PDF soubor zobrazit neumí. Pokud by uživatel nebyl spokojen s tímto formátem, lze ho následně převést různými způsoby na PDF. Pro tyto účely stojí za zmínku server http://ps2pdf.com, kde lze na adrese http://ps2pdf.com/convert.cgi jednoduše soubor s příponou .ps konvertovat na PDF. Vztahy mezi grafem v aplikaci a grafem exportovaným Ve fázi definice požadavků a návrhu bylo nutné rozhodnout, v jakých rozměrech a na jaký formát stránky vykreslovat graf. V aplikaci je standardně zobrazován v rozlišení 96 DPI27 . Pokud platí, že 1 in = 2,54 cm, potom při rozlišení 96 DPI se . 1 px = 0,0265 cm. Vykreslením uzlu, který má v aplikaci výchozí poloměr 15 px, bude mít na stránce průměr přibližně 0,8 cm, což je rozměr vyhovující. Není proto třeba DPI měnit. Po dohodě s pracovníky ÚSOP postačí rozměrově stránka formátu A4. Těmto rozměrům musely být přizpůsobeny zpětně i maximální rozměry pracovního plátna, aby uzly vykreslené kdekoli na plátně byly zobrazitelné na jedné stránce formátu A4. Rozložení stránky je nastaveno „na šířkuÿ, čemuž odpovídají i výchozí rozměry pracovního plátna. Aby byl zachován „zlatý řezÿ28 a současně mohl být u spodního okraje vyčleněn prostor pro komentář kroku řešení grafového algoritmu, jsou s ohledem na rozměry stránky a DPI nastaveny maximální rozměry pracovního plátna aplikace na 850 px ve vodorovném směru a 600 px ve svislém směru. Tvorba exportu K hlavnímu programu byl naprogramován modul zdrojTeX, který tento způsob exportu zajišťuje. V tomto textu bude příblížena stěžejní část kódu v exportovaném souboru, tedy vykreslování samotných hran a uzlů. Obrázek 9 byl vytvořený kódem uvedeným níže. Vykreslovat uzly lze několika příkazy, například příkazem \cnode[parametry](x,y){poloměr}{jméno} nebo \cnodeput[parametry](x,y){jméno}{text}. První příkaz vytvoří kružnici se středem na souřadnicích a o poloměru uvedených ve složených závorkách. Nelze však do Bližší informace o PSTricks na http://ftp.cstug.cz/pub/tex/CTAN/graphics/pstricks/ base/doc/pst-user.pdf. 26 http://tug.org/texlive/. 27 Dots Per Inch – obrazových bodů (pixelů) na jeden palec. 28 http://www.karlin.mff.cuni.cz/katedry/kdm/diplomky/chmelikovabp/Zlaty_rez.pdf. 25

42

5.11 Export grafu

něj vepsat text. To naopak umožňuje druhý zmiňovaný příkaz, kde je však poloměr volen automaticky pouze podle velikosti písma29 . Poloměr je ale v aplikaci volitelný. Proto bylo využito obou příkazů. Nejprve je vykreslen uzel s textem, ale barva kružnice je v parametru nastavena na bílou (jako podklad) a poté je na shodných souřadnicích vykreslena kružnice s požadovaným poloměrem. Všechny hrany v podobě přímky se interpretují příkazem \ncline[parametry] {šipka}{počáteční u.}{koncový u.}. V parametru šipka lze zvolit směr orientace hrany (->, -, <-). Na hrany ve tvaru křivky je použit příkaz \ncarc[parametry]{šipky}{počáteční u.}{koncový u.}. Nelze zde definovat beziérovu křivku pomocí vrcholů řídícího polygonu. K přesné definici křivky jsou v části [parametry] nastavovány hodnoty arcangle a ncurv. První hodnota znamená úhel, který svírá úsečka mezi středy uzlů a úsečka mezi středem uzlu a nejbližším bodem P řídícího polygonu od uzlu. Hodnota ncurv definuje vzálenost od počátku křivky a nejbližším řídícím bodem P . Pokud ncurv nabývá hodnoty 1, je vzdálenost mezi danými body právě polovina vzdálenosti mezi uzly. 220 CZ

SK

123

Obr. 9: Multigraf (vytvořeno autorem)

\begin{pspicture}(0cm,0cm)(9cm,3cm) \cnodeput[linecolor=white](2.9864,1.5675){1_}{CZ} \cnode(2.9864,1.5675){0,4}{1} \cnodeput[linecolor=white](7.0135,2.4324){2_}{SK} \cnode(7.0135,2.4324){0,4}{2} \ncarc[arcangle=-38, ncurv=0.6280,linestyle=solid]{->}{1}{2} \mput*{123} \ncarc[arcangle=-38, ncurv=0.6280,linestyle=solid]{->}{2}{1} \mput*{220} \end{pspicture}

29

Velikost písma je 10 pt.

6 DISKUSE

6

43

Diskuse

Praktická část práce seznamuje čtenáře hlavně s implementačními postupy, které vedly k výsledné aplikaci. Vzhledem k limitovanému rozsahu práce nebylo možné se všemi oblastmi zabývat tak, jak by si zasloužili. Současně ale byly zmíněny všechny stěžejní principy nutné pro komplexní porozumění problematiky. Pro předposlední část životního cyklu vývoje aplikace – testování – bylo použito nejrůznějších typů modelů grafu a všechny objevené funkční potíže byly opraveny. V budoucnu odhalené nedostatky však nelze vyloučit. Přínosy řešení Uplatnění výstupu závěrečné práce je široké. Užitečný může být hned v několika předmětech vyučovaných na PEF MENDELU v Brně, zejména však poslouží jako učební pomůcka pro studenty prezenční a hlavně kombinované formy studia předmětu EMM. Pravidelně dosahuje počet studentů předmětu EMM v semestru řádů stovek. Nasazení do výuky tak bohatě ověří stabilitu řešení. Pro další okruhy předmětu Ekonomicko matematické metody již podobné podpůrné programy existují a od studentů přichází velmi kladná odezva. Mohou se důkladněji, spolehlivě a s menší námahou prostřednictvím podpůrných aplikací připravit na absolvování předmětu. Vyučující mají naopak možnost jednoduše vytvořit zadání testu a pohodlně ověřit řešení i několika variant. Návrhy na zlepšení a rozšíření aplikace Problematika grafových algoritmů a jejich využití v praxi je velmi rozsáhlá, a tak existuje mnoho směrů, kterými aplikaci dále vyvíjet. Rozšiřování aplikace o další algoritmy je vyřešeno dynamickými knihovnami, i ty je ale třeba naprogramovat. Zde navrhovaná rozšíření směřují zejména na hlubší propracování rozhraní. Aplikace by mohla být doplněna o větší variabilitu práce s grafem. Aplikaci by prospělo automatizované rozmísťování uzlů tak, aby vznikl rovinný graf s důrazem na zarovnání uzlů. Dále například změna tvaru uzlů, či tvorba smyček. Další možnost zkvalitnění aplikace je v oblasti exportu. Nepochybně by byl velmi užitečný export grafu například do SVG grafiky.

7 ZÁVĚR

7

44

Závěr

Teoretická část seznámuje čtenáře s grafy a grafovými algoritmy. Zároveň přibližuje postupy a nástroje využité při tvorbě výstupu závěrečné práce. V druhé části práce je navržena a implementována aplikace umožňující studentům snadnou a rychlou tvorbu libovolných modelů grafů. Na vytvořené nebo ze souboru načtené modely lze dále aplikovat grafové algoritmy. Výsledné řešení je zpřístupněno uživateli tak, aby mohl libovolně řešením procházet v obou směrech. Množinu grafových algoritmů lze snadno rozšířít stažením nové knihovny do odpovídajícího adresáře. Řešení aplikace algoritmu na graf aplikace dle potřeby exportuje do textového souboru s rozšířením .tex. Po přeložení souboru překladačem systému LATEX a další drobné úpravě získá uživatel PDF soubor s řešením. S pracovníky Ústavu statistiky a operačního výzkumu PEF MENDELU v Brně byly možnosti aplikace během vývoje konzultovány a dále upraveny podle jejich potřeb, aby vyhovovala jak studentům tak pracovníkům ustavu. Práce splňuje všechny body předsevzatého plánu a v nejbližším novém semestru bude nasazena jako učební pomůcka studentům, kde až statistika výsledků zkoušky odhalí skutečné splnění cílů závěrečné práce.

8 LITERATURA

8

45

Literatura

Cantu, M. Myslíme v jazyku Delphi 6. 1. vyd. Praha: Grada Publishing, 2002. 496 s. Knihovna programátora. ISBN 80-247-0334-3. Čada, R., Kaiser, T., Ryjáček, Z. Diskrétní matematika. 1. vyd. Plzeň : Západočeská univerzita v Plzni, 2004. 170 s. ISBN 80-7082-939-7. Černý, J. Základní grafové algoritmy. 1. vyd. Praha: KAM, MFF UK, 2008. 113 s. Dostupný z WWW: . Demel, J. Grafy a jejich aplikace. 1. vyd. Praha: Academia, 2002. 257 s. ISBN 80200-0990-6. . Fajmon, B., Koláček, J. Pravděpodobnost, statistika a operační výzkum. 2005. 311 s. Dostupný z WWW: . Foltýnek, T. a kol. Teoretické základy informatiky. E-learningová opora k předmětu TZI [online]. 5.4.2006 [cit. 19.2.2010]. Dostupná z WWW: . Holoubek, J. Ekonomicko-matematické metody. Brno: Mendelova zemědělská a lesnická univerzita v Brně, 2009. 153 s. ISBN 978-80-7157-970-0. Koucký, M., Zelinka, B. Diskrétní matematika I. 1. vyd. Liberec : Technická univerzita v Liberci, 2003. 90 s. ISBN 80-7083-715-2. Kučerová, H. Use Case diagram [online]. 29.10.2009 [cit. 24.3.2010]. Use Case model. Dostupné z WWW: . Microsoft Corporation. Windows Developer Center: Multiple Document Interface [online]. 2010 [cit. 13.2.2010]. Dostupný z WWW: . Polách E. Programování v jazyku Turbo Pascal: Dynamické datové struktury [online]. 1999 [cit. 14.2.2010]. Dostupný z WWW: . Pošta, J. Delphi: Dynamické datové struktury [online]. 2010 [cit. 14.2.2010]. Dostupný z WWW: . Rybička, J. LATEX pro začátečníky. 3. vyd. Brno: Konvoj, 2003. 238 s. ISBN 807302-049-1. Šeda, M. Teorie grafů. 2003. 89 s. Dostupný z WWW: . Teixeira, S., Pacheco, X. Mistrovství v Delphi 6. 1. vyd. Praha: Computer Press, 2002. 822 s. Profi: Programování. ISBN 80-7226-627-6. Žára, J., Beneš, B., Felkel, P. Moderní počítačová grafika. 1. vyd. Praha: Computer Press, 1998. 488 s. ISBN 80-7226-049-9.

Přílohy

A GUI PŘI STARTU APLIKACE

A

GUI při startu aplikace

Obr. 10: GUI při startu aplikace

47

B PRACOVNÍ FORMULÁŘ

B

Pracovní formulář

Obr. 11: Pracovní formulář

48

C IMPLEMENTACE DYNAMICKÝCH STRUKTUR

C

49

Implementace dynamických struktur

procedure TGraf.PridejUzel(Stred: TPoint; Polomer: Word; SirkaP: Byte; StylP: TPenStyle); var Pom: TUzel; MaxI: Word; begin Inc(PocetUzlu); Inc(ID_Uzel); MaxI := VratMaxIDUzlu; Pom := TUzel.Init(ID_Uzel, IntToStr(MaxI + 1), Stred, Polomer, SirkaP, StylP); if FPocUzel = nil then begin new(FPocUzel); FPocUzel^ := Pom; FPocUzel^.Dalsi := nil; FKonUzel := FPocUzel; end else begin new(FKonUzel^.Dalsi); FKonUzel^.Dalsi^ := Pom; FKonUzel := FKonUzel^.Dalsi; end; end; procedure TGraf.PridejHranu(PocUzel: Word; KonUzel: Word; Ohodnoceni: Integer; Zaobleni: Integer); var PomZac, PomKon: TUkUzel; Pom: THrana; begin Inc(PocetHran); Inc(ID_Hrana); PomZac := VratUkazatelNaUzel(PocUzel); PomKon := VratUkazatelNaUzel(KonUzel); Pom := THrana.Init(ID_Hrana, Ohodnoceni, PomZac, PomKon); if FPocHrana = nil then begin new(FPocHrana); FPocHrana^ := Pom; FPocHrana^.Dalsi := nil; FKonHrana := FPocHrana; end else begin new(FKonHrana^.Dalsi); FKonHrana^.Dalsi^ := Pom; FKonHrana := FKonHrana^.Dalsi; end; SpocitejNasobne(PomZac, PomKon, Zaobleni); end;

D

PSEUDOKÓD METODY PLATNOMOUSEDOWN

D

Pseudokód metody PlatnoMouseDown

Nalezni id uzlu, na který bylo kliknuto; IF Stisknuto levé THEN BEGIN CASE Režim OF Uzel: BEGIN IF aktuální uzel nepřekrývá jiný THEN BEGIN Přidej uzel do seznamu; Vykresli nový uzel; END ELSE BEGIN Přidej uzel do seznamu; Vykresli nový uzel v inverzních barvách; Nastav aktuální režim na Překrývání; END; Pohyb: BEGIN IF byl vybrán uzel THEN BEGIN Změň šipku myši na ruku; Zobraz v panelu Vlastnosti parametry uzlu; Zjisti pseudostřed vybraného uzlu; END ELSE byla vybrána hrana THEN BEGIN Změň šipku myši na ruku; Zobraz v panelu Vlastnosti parametry hrany; END; END; Hrana: BEGIN IF byl vybrán počáteční uzel THEN Zapamatuj si ho; END; Mazání: BEGIN IF byl vybrán uzel THEN Odeber uzel; ELSE IF byla vybrána hrana THEN Odeber hranu; Aktualizuj plátno; END; END; END ELSE IF Stisknuto pravé THEN BEGIN IF byl vybrán uzel AND režim = Překrývání THEN BEGIN Odeber uzel; Aktualizuj plátno; Režim := Uzel; END; END;

50

E PSEUDOKÓD METODY PLATNOMOUSEMOVE

E

Pseudokód metody PlatnoMouseMove

IF Stisknuto levé THEN BEGIN CASE Režim OF Uzel: BEGIN Překresli graf; IF nový uzel překrývá jiný THEN BEGIN Zjisti novou vhodnou pozici pro nový uzel; IF nová pozice nezasahuje mimo plátno THEN Zapiš pozici uzlu; END ELSE IF není mimo plátno THEN Zapiš pozici uzlu; ELSE IF je mimo plátno THEN IF nová pozice uzlu nepřekrývá jiný THEN Zapiš pozici uzlu; Vykresli graf; END; Prekryvani: BEGIN Překresli graf; IF nový uzel překrývá jiný THEN BEGIN IF není mimo plátno THEN Zapiš pozici uzlu ELSE Zapiš pozici uzlu, aby nekryla jiný; Vykresli graf; END ELSE BEGIN Režim nastav na Uzel; Vykresli uzel s neinvertovanými barvami; END; END; Pohyb: BEGIN Proveď to stejné, co v režimu uzel; END; Hrana: BEGIN IF začíná hrana v nějakém uzlu THEN BEGIN vykresli graf; Kresli hranu od poč. uzlu ke kurzoru myši; END; END; END;

51

F PSEUDOKÓD METODY PLATNOMOUSEUP

F

Pseudokód metody PlatnoMouseUp

CASE Režim OF Překrývání: BEGIN IF nový uzel nepřekrývá jiný THEN Režim nastav na Uzel ELSE Režim nastav na Překrývání; END; Pohyb: BEGIN Vymaž pomocné plátno; Vykresli údaje na pomocné plátno; END; Hrana: BEGIN IF koncový uzel není označen THEN BEGIN Překresli hranu; Vykresli graf; END ELSE BEGIN Překresli hranu; Překresli graf; Přidej novou hranu do seznamu; Vykresli graf i s novou hranou; Zapiš změny do pomocného plátna; END; END; END;

52

G GRAF V SOUBORU

G

53

Graf v souboru

PLATNO(osax;osay) (700;500) GRAForientace ohodnocenost 1 1 UZLY(nazev1; nazev2;.. nazevN) (1;2;ABC;XYZ;5;6;7) HRANYpocatecni_uzel: koncovy_uzel(delka_hrany) [koncovy_uzel(delka_hrany)]) 2: 3(1) 1(4) 3: 4(1) 7(12) 4: 2(1) 1(1) 7(1) 5: 2(1) 6(9) 6: 3(1) 7(1) 7: 3(1) GRAFIKA--volitelna cast--pocatek souradnic v levem hornim rohu uzel: (souradnice_x,souradnice_y,polomer) 1: (192;397;15) 2: (123;298;15) 3: (266;221;15) 4: (394;357;15) 5: (195;103;15) 6: (465;135;15) 7: (599;261;15)

H API KOMUNIKACE S KNIHOVNOU

H

API komunikace s knihovnou

// vrací název zpracovávaného algoritmu function Info: PChar; // vrací true, pokud algoritmus vyžaduje síťový graf function Sitovy: Boolean; // vrací True, pokud alg. pracuje i s orient. grafem function Orient: Boolean; // vrací True, pokud alg. pracuje i s neorient. grafem function NeOrient: Boolean; // vrací True, pokud alg. pracuje i s ohodnoceným grafem function Ohodnoc: Boolean; // vrací True, pokud alg. pracuje i s neohodnoc. grafem function NeOhodnoc: Boolean; // vrací True, pokud alg. pracuje i nad nesouvislým grafem function Nesouv: Boolean; // vrací True, pokud alg. funguje i nad cyklickým grafem function Cyklus: Boolean; // vrací True, pokud alg. umožňuje uživateli výběr poč. u. function PocatUzel: Boolean; // vrací v parametru Vystup výsledný seznam kroků řešení procedure Reseni(Graf, Pocatecni, Koncovy: Pointer; var Vystup: Pointer);

54