Využití grafové databáze pro hledání vlakových spojů

Mendelova univerzita v Brně Provozně ekonomická fakulta

Využití grafové databáze pro hledání vlakových spojů Bakalářská práce

Vedoucí práce: Ing. Jan Kolomazník

Michal Vachler

Brno 2014

Touto cestou bych chtěl poděkovat vedoucímu této bakalářské práce Ing. Janu Kolomazníkovi za připomínky, cenné rady a čas, který mi věnoval. Dále bych chtěl poděkovat vývojovému týmu z kj.cz za bezproblémovou spolupráci.

Čestné prohlášení Prohlašuji, že jsem práci: Využití grafové databáze pro hledání vlakových spojů vypracoval samostatně a veškeré použité prameny a informace jsou uvedeny v seznamu použité literatury. Souhlasím, aby moje práce byla zveřejněna v souladu s § 47b zákona č. 111/1998 Sb., o vysokých školách ve znění pozdějších předpisů, a v souladu s platnou Směrnicí o zveřejňování vysokoškolských závěrečných prací. Jsem si vědom, že se na moji práci vztahuje zákon č. 121/2000 Sb., autorský zákon, a že Mendelova univerzita v Brně má právo na uzavření licenční smlouvy a užití této práce jako školního díla podle § 60 odst. 1 Autorského zákona. Dále se zavazuji, že před sepsáním licenční smlouvy o využití díla jinou osobou (subjektem) si vyžádám písemné stanovisko univerzity, že předmětná licenční smlouva není v rozporu s oprávněnými zájmy univerzity, a zavazuji se uhradit případný příspěvek na úhradu nákladů spojených se vznikem díla, a to až do jejich skutečné výše. V Brně dne 19. května 2014

_______________________________

Abstract Vachler, M. Use of graph database for train connections search. Bachelor thesis. Brno: Mendel University, 2014. This bachelor's thesis addresses a design of alternative solution of train connections search for website kj.cz. Individual database systems and graph algorithms are presented in the theoretical part. The practical part then focuses on the design of the application itself and its testing. Keywords Train connections search, graph database, Neo4j, graph algorithms, Dijkstra's algorithm, A*

Abstrakt Vachler, M. Využití grafové databáze pro hledání vlakových spojů. Bakalářská práce. Brno: Mendelova univerzita v Brně, 2014. Tato bakalářská práce se zabývá návrhem alternativního řešení vyhledávání vlakových spojů pro webové stránky kj.cz. V teoretické části jsou představeny jednotlivé databázové systémy a grafové algoritmy pro hledání nejkratší cesty. Praktická část popisuje návrh samotné aplikace včetně testování. Klíčová slova Vyhledávání vlakových spojů, grafová databáze, Neo4j, grafové algoritmy, Dijkstrův algoritmus, A*.

Obsah

9

Obsah 1

2

Úvod a cíl práce 1.1

Úvod....................................................................................................................................... 15

1.2

Cíl práce................................................................................................................................ 15

Teoretická část

16

2.1

Graf......................................................................................................................................... 16

2.2

Hledání optimální cesty ................................................................................................. 16

2.3

Database management system (DBMS)................................................................... 16

2.3.1

Relational database management system (RDMBS) ................................ 16

2.3.2

Key-value databáze ............................................................................................... 17

2.3.3

Column-oriented databáze ................................................................................. 17

2.3.4

Dokumentová databáze ....................................................................................... 17

2.3.5

Grafová databáze .................................................................................................... 18

2.4

Neo4j ..................................................................................................................................... 18

2.4.1

Cypher query language ........................................................................................ 19

2.4.2

Datové typy ............................................................................................................... 20

2.4.3

Import dat ................................................................................................................. 20

2.4.4

Labels .......................................................................................................................... 20

2.4.5

Indexace ..................................................................................................................... 20

2.4.6

Upgrade ...................................................................................................................... 21

2.4.7

Standalone mode (REST API) ............................................................................ 21

2.4.8

Embedded mode (JAVA) ...................................................................................... 22

2.4.9

Grafové algoritmy .................................................................................................. 23

2.5

3

15

Grafové algoritmy............................................................................................................. 23

2.5.1

Floyd-Warshallův algoritmus ............................................................................ 23

2.5.2

Dijkstrův algoritmus ............................................................................................. 24

2.5.3

Bellman-Fordův algoritmus ............................................................................... 25

2.5.4

A* algoritmus ........................................................................................................... 26

Metodika

27

10

4

Obsah

Návrh samotného řešení

28

4.1

Výběr typu databáze........................................................................................................ 28

4.2

Optimální grafový algoritmus ...................................................................................... 28

4.3

Návrh grafové databáze ................................................................................................. 29

4.4

Grafový algoritmus .......................................................................................................... 36

4.4.1

Expander .................................................................................................................... 36

4.4.2

Cost Evaluator .......................................................................................................... 37

4.4.3

Estimate evaluator ................................................................................................. 38

4.5

Testování v praxi .............................................................................................................. 38

5

Diskuze

41

6

Závěr

42

7

Literatura

43

A

Program

46

Obsah

11

12

Seznam obrázků

Seznam obrázků Obr. 1

Ukázka výstupu z grafové databáze Neo4j

18

Obr. 2

Schéma relační databáze

30

Obr. 3

Návrh grafové databáze

31

Obr. 4

Návrh spojů a přestupů

33

Obr. 5

Hledaný spoj z jizdnirady.idnes.cz

39

Seznam tabulek

13

Seznam tabulek Tab. 1

Ukázka key-value databáze

17

Tab. 2

Ukázková databáze

17

Tab. 3

Srovnání rychlosti relační s grafovou databází

28

Tab. 4

Srovnání výsledků Dijkstrova algoritmu

40

Tab. 5

Srovnání výsledků A* algoritmu

40

Úvod a cíl práce

15

1 Úvod a cíl práce 1.1

Úvod

Každý z nás jel alespoň jednou v životě vlakem, tudíž si potřeboval najít vhodný spoj. Dříve existovali jízdní řády pouze na papíře, ale s příchodem internetu dostalo vyhledávání spojů nový rozměr. Spojení je možné vyhledat na základě různých parametrů, jakou jsou přímé spoje, bezbariérový přístup, vlaky bez nutnosti rezervace a mnoho dalších. S příchodem nových dopravců na železniční trať Praha - Ostrava nastal problém, kterého dopravce zvolit. Uživatel musí učinit volbu, u kterého bude spoj nejrychlejší, nejlevnější a nejpohodlnější. Za účelem zlepšení orientace vznikl i projekt kj.cz. Jedná se o srovnávač vlakových spojů, který kombinuje všechny dopravce a umožňuje i jízdenky přímo zakoupit. Projekt je založený na OpenTripPlanner, což je open-source pro plánování a analyzování cest. Vývojový tým z kj.cz v návaznosti oslovil Mendelovu univerzitu a konzultoval bakalářskou práci na zmíněnou tématiku.

1.2

Cíl práce

Bakalářská práce se bude zabývat návrhem alternativního řešení vyhledávání vlakových spojů pro webové stránky kj.cz. Většina projektů používá automaticky relační databázi, i když to nemusí být vždy nejoptimálnější, proto hlavním předmětem práce bude pro tuto problematiku najít vhodnější typ databáze. V teoretické části budou rozebrány jednotlivé databázové systémy. Nepůjde jen o vytvoření nové databáze, ale také o nalezení nejkratší cesty mezi zastávkami. Proto budou v teoretické části objasněny některé grafové algoritmy, které slouží k nalezení nejkratší cesty. V praktické části bude popsáno zhotovení samotné aplikace. V první fázi bude potřeba vybrat vhodný databázový systém a samotnou databázi vytvořit. Samozřejmě půjde také o to, aby vyhledávání vlakových spojů bylo časově co nejméně náročné. Tohle bude potřeba brát v potaz, jak při návrhu databáze, tak při tvorbě samotné aplikace. V druhé fázi bude na základě teoretické části implementován vhodný algoritmus. Praktická část bude také testovat funkčnost v praxi. Na závěr proběhne zhodnocení bakalářské práce a budou rozebrány případné návrhy na zlepšení aplikace do budoucna.

16

Teoretická část

2 Teoretická část Teoretická část zkoumá jednotlivé databázové systémy a poskytuje úvod pro práci s grafovou databází Neo4j. Dále se věnuje základním poznatkům z grafové teorie, zaměřuje se především na grafové algoritmy. Jelikož značná část bakalářské práce vychází z grafové teorie, je potřeba objasnit, co to graf vůbec je.

2.1

Graf

Graf se skládá z množiny uzlů (vrcholů) a hran (vazeb). Entity jsou reprezentovány uzly a vztahy mezi entitami vyjadřují hrany. Každá hrana může mít orientaci neboli směr. Graf může být ohodnocený, což znamená, že uzly a hrany můžou nabývat určité hodnoty. V grafu se dá zachytit mnoho situací z reálného světa, například síťová infrastruktura mezi městy. (Even 2012)

2.2

Hledání optimální cesty

Pro vlaková spojení bude potřeba nalézt optimální cestu mezi počáteční a cílovou zastávkou. Optimální cestu může například reprezentovat nejrychlejší spojení, co se týče časového hlediska nebo nejmenší vzdálenosti v kilometrech a podobně. Touto problematikou se zabývá grafová teorie a konkrétně se jedná o problém nejkratší cesty. Cestou se rozumí sled hran, které spojují vždy dva uzly. Pro výpočet nejkratší cesty se může vycházet z hodnot hran a uzlů. Je taky možné zvolit nejkratší cestu na základě počtu hran, přes které vede cesta z počátečního do cílového uzlu. Ještě před rozebráním samotných algoritmů, které budou problém nejkratší cesty řešit, je potřeba si uvědomit, jak budou data uloženy, respektive jaký typ databáze zvolit. (Skiena 2008)

2.3

Database management system (DBMS)

Databázové systémy slouží pro efektivní uchovávání dat. Každý DBMS by měl uživateli umožnit vytvářet databáze, být schopen uchovávat velké množství dat a umožnit pracovat s daty pomocí dotazovacího jazyka. DBMS se rozděluje na dvě hlavní skupiny. První a starší skupinou je RDMBS (relational database management system) a druhou skupinu tvoří NoSQL databáze, které vznikly kvůli náročnějším požadavkům na výkon a množství uchovaných dat. NoSQL databáze upustily od relační struktury. Tyto databáze se dělí dále do čtyř kategorií. Jsou to key-value, column-oriented, dokumentové a grafové databáze. (Redmond, Wilson a Carter 2012) 2.3.1

Relational database management system (RDMBS)

Název napovídá, že se jedná o relační databázové systémy. Strukturu relační databáze tvoří dvourozměrné tabulky, které se nazývají relace. Každá tabulka se skládá

Teoretická část

17

z řádků a sloupců. Tyto řádky představují jednotlivé záznamy a sloupce reprezentují atributy. Atributu nebo množině atributů může být přidělen primární klíč. Atributy, kterým byl přidělen primární klíč, tvoří unikátní záznamy. Kromě primárních klíčů, existují také cizí klíče, které vyjadřují vazby mezi relacemi. V podstatě cizí klíče odkazují na atribut s primárním klíčem. Pro dotazování se používá jazyk SQL (structured query language). Mezi nejznámější RDBMS patří Oracle, MySQL, PostgreSQL, Microsoft SQL Server a další. (Garcia-Molina, Ullman a Widom 2009) 2.3.2

Key-value databáze

Struktura key-value databáze uchovává vždy klíč a hodnotu. Výhodou je rozhodně výkon za předpokladu, že nepotřebujeme provádět složité dotazování. Příkladem key-value databází mohou být Riak a Redis. (Garcia-Molina, Ullman a Widom 2009) Tab. 1

Ukázka key-value databáze

City12_name City45_name City12_population 2.3.3

Brno Praha 400000

Column-oriented databáze

Tato struktura ukládá data ze sloupce dohromady, narozdíl od relačních databází, které ukládají data z řádku dohromady. Následující příklad ukazuje, jak vypadá struktura column-oriented databáze. (Garcia-Molina, Ullman a Widom 2009) Tab. 2

Ukázková databáze

ID 1 2

Město Brno Praha

Z výše uvedené databáze má struktura column-oriented databáze tvar 1,2;Brno,Praha;. Databáze orientovaná podle řádku by měla tvar 1,Brno;2,Praha;. Hlavní výhodou je větší výkon nad dotazy s agregací, jedná se například o AVG,COUNT,MAX a podobně. Další výhodou je datová komprese. Například HBase je reprezentantem column-oriented databáze. (Garcia-Molina, Ullman a Widom 2009) 2.3.4

Dokumentová databáze

Hlavní prvek dokumentové databáze jsou dokumenty, které tvoří datovou strukturu dokumentových databází. Výhodou je uložení dokumentů ve známých formátech jako XML,PDF,DOC a další. Tento typ databáze je vhodný tam, kde nejsou vazby a hodí se pro různorodá data, tudíž se dá použít i když nevíme s jakými daty

18

Teoretická část

budeme pracovat. Mezi tyto databáze patří MongoDB a CouchDB. (Garcia-Molina, Ullman a Widom 2009) 2.3.5

Grafová databáze

Jak již z názvu napovídá, grafová databáze používá grafovou strukturu. To znamená, že se skládá z uzlů, jejich atributů a vztahů mezi uzly pomocí hran. Každá hrana je pojmenovaná, může být ohodnocená pomocí atributů a má směr. Grafové databáze se vyplatí použít především tam, kde vzniká velké množství vazeb mezi daty. Typickým příkladem může být sociální síť, kde jedna osoba se přátelí s dalšími lidmi. Dalším příkladem můžou být dopravní problémy, hledání nejkratší cesty mezi městy a podobně. Naopak, čím méně vazeb databáze má mít, tím menší má smysl jí použít. (Robinson, Webber a Eifrem 2013)

Obr. 1

2.4

Ukázka výstupu z grafové databáze Neo4j

Neo4j

Neo4j je nejpoužívanější grafová databáze. Je kompatibilní s velkou škálou programovacích jazyků. Jedná se například o Javu, .NET, PHP, Python, Ruby a další. Jako dotazovací jazyk Neo4j používá Cypher query language, který je rozebrán v další podkapitole. Neo4j je dostupné ve verzi Comunnity zdarma pod licencí GPL. Dále existují i placené verze, které přidávají například on-line zálohování, clustering, pokročilé monitorování. Vývojáři můžou Neo4j spustit na platformách Windows, Linux a Mac OS X, jedinou podmínkou je mít nainstalován Java JDK. (Neo Technology, 2014a). V následujících kapitolách bude Neo4j představeno blíže, teorie vychází z Neo4j 2.0.

Teoretická část

2.4.1

19

Cypher query language

Pro manipulaci s daty, respektive provádění dotazů nad daty, je zapotřebí si osvojit Cypher query language. Jedná se o dotazovací jazyk, speciálně navrhnutý pro Neo4j. Syntaxe jazyka je jednoduše čitelná a inuitivní. Pro manipulaci s daty bych zařadil jako nejdůležitější především tyto příkazy: MATCH, RETURN a CREAT. Tato kapitola pouze stručně shrnuje základní a pro tuto bakalářskou práci nejdůležitější syntaxi. Pro podrobnější pochopení problematiky doporučuji navštívit oficiální dokumentaci http://docs.neo4j.org nebo pro stručné shrnutí všech příkazů se podívat na Neo4j Cypher Refcard. (Robinson, Webber a Eifrem 2013) RETURN Slouží ke specifikování hodnot, které budou vráceny. MATCH Slouží k získávání dat z databáze, podle určitého vzoru. Pro získání všech uzlů slouží vzor MATCH (n) RETURN n. Písmeno „n“ v příkazu funguje jako proměnná, mohl by tam být jakýkoli text. Příkaz pro získání všech uzlů, ze kterých vychází (outgoing) vazba typu RELATED, by vypadal takto MATCH (n)-[r:RELATED]->(m) RETURN n. Pro získání všech vazeb typu RELATED z předchozího příkladu by stačilo zaměnit RETURN n za RETURN r. Pokud stačí vybrat všeobecně jakýkoli vztah, bez typového omezení, bez omezení směru vazby, pak se dá použít zápis MATCH (n)--(m). (Neo Technology, 2014f) Od verze 2.0 se používá pro získání dat příkaz MATCH, v nižších verzí se používal příkaz START. Ten je již zastaralý, ale pořád ho je možné použít. WHERE Používá se s příkazy START, MATCH a WITH. Vkládá se za tyto příkazy a slouží k vytvoření omezujících podmínek. Například MATCH (n) WHERE n.city=“Brno“ vybere uzly, které mají v atributu city hodnotu Brno. (Neo Technology, 2014k) CREATE Tímto příkazem se vytváří uzly a nebo vztahy mezi uzly. Příklad pro uzel může vypadat takto CREATE (n {name: “Brno“, population: 1000}). Pro vztah mezi uzly CREATE (n)-[:TYPVAZBY]->(m). Předpokladem je, že proměnné n a m obsahují uzly, získané například pomocí MATCH. (Neo Technology, 2014b) MERGE MERGE slouží k vytvoření unikátních dat. Dalo by se říci, že tento příkaz vznikl sloučením MATCH a CREATE. MERGE nejprve prohledá databázi, jestli už požadovaný vzor neexistuje (v podstatě vykoná příkaz MATCH), pokud neexistuje, tak jej vytvoří (CREATE). Pokud existuje, tak vrátí data podle požadovaného vzoru. MERGE (n {name: “Brno”}) vytvoří uzel s atributem name “Brno” za předpokladu, že ta-

20

Teoretická část

kový uzel už v databázi neexistuje. MERGE (n)-[:TYPVAZBY]->(m) vytvoří za předpokladu neexistujícího vzoru, nejen vazbu, ale i dva prázdné uzly. Existuje ještě příkaz CREATE UNIQUE, který plní obdobnou funkci jako MERGE. Tento příkaz fungoval původně před MERGE, tudíž je zastaralý i když o tom v dokumentaci není zmínka a pro začátečníka to může být matoucí. (Neo Technology, 2014g) 2.4.2

Datové typy

Neo4j rozlišuje automaticky, jestli jsou atributy uzlů z řetězců, číselné nebo logické a vykonává potřebné operace nad daty (matematické, logické, porovnávací a operace s řetězci). Při vytváření databáze, tak není nutno specifikovat o jaký konkrétní datový typ se jedná. Datové typy pro atributy vychází z datových typů jazyka JAVA. Speciální hodnotou je hodnota NULL, kterou může dotaz vrátit, pokud například neexistuje požadovaný atribut u uzlu. (Neo Technology, 2014j) 2.4.3

Import dat

Data do grafové databáze můžeme importovat data v podstatě třemi způsoby. První a nejjednodušší způsob je přes konzoli, pomocí Cypher query language. Je však potřeba si nejdříve data do požadované syntaxe vhodně upravit. Další možností je využít, již nějaké hotové řešení pro import dat. Například Neo4j (CSV) Batch Importer (https://github.com/jexp/batch-import). Jak název napovídá, pro import budou potřeba data ve formátu csv. Poslední možností je napsat si vlastní řešení, například pomocí jazyka JAVA. 2.4.4

Labels

Od verze 2.0 přibyla užitečná vlastnost v podobě labels. Labels slouží k lepší identifikaci uzlů. Na rozdíl od vazeb mezi uzly, které se dají identifikovat pomocí typu vazby (types), se uzly ve verzi 1.9 nedaly jednoznačně identifikovat jakého typu jsou. V praxi můžeme mít například zákazníky a prodavače, oba mají stejné atributy (jméno, příjmení, telefon, …). Pokud mají stejné atributy, těžko rozlišíme jestli se jedná o zákazníka nebo prodavače. Potom je potřeba vytvořit pomocný uzel a na ten vytvářet vazby. Takže z uzlu, který reprezentuje zákazníka se vytvoří vazba typu ZAKAZNIK na pomocný uzel, prodavač bude mít vazbu typu PRODAVAC. Pomocí těchto vazeb jsme schopni určit, jestli uzel reprezentuje zákazníka nebo prodavače. Aby se nemuselo takhle postupovat, zavedly se labels. Takže již je možné uzel přímo označit, podle toho jaké data reprezentuje. Uzel může obsahovat jeden label nebo více. Label se vytvoří při vytváření uzlu CREATE (n:Label {property:“value“}). Dá se nastavit i existujícím uzlům SET n:Label. Pro odstranění slouží příkaz REMOVE n:Label. (Neo Technology, 2014e) 2.4.5

Indexace

Neo4j umožňuje indexaci atributů, jak pro uzly, tak pro vztahy mezi uzly. Indexace se vyplatí kvůli lepší časové náročnosti při přístupu k uzlům a vztahům.

Teoretická část

21

U uzlů se používá velmi často, naopak u vztahů mezi uzly jen výjimečně. Indexace se vztahuje vždy k určitému atributu, může být indexováno i více atributů. Pokud jsou před vytvořením indexu v databázi uzly (vazby), nedojde k indexování těchto uzlů (vazeb). Nabízí se dva způsoby řešení. První možností je smazat uzly (vazby) z databáze a opětovně je po vytvoření indexu nahrát. Druhou možností je využít příkazu SET, který aktualizuje hodnoty a dojde k indexování. Celý příkaz by mohl vypadat takto match (n) where has(n.property) set n.property=n.property;. Během psaní bakalářské práce vyšla nová verze 2.0, kde je nastavení indexace uživatelsky přívětivější. V následujících dvou odstavcích je popsáno jak se s indexací pracuje ve verzi 1.9 a 2.0. (Neo Technology, 2014d) Ve verzi 1.9 se indexace nastavuje v souboru neo4j.properties. Nejdříve je potřeba odstranit komentovaný řádek #node_auto_indexing=true, hodnota musí být nastavena na true. Dále je potřeba odkomentovat #node_keys_indexable a přiřadit jména atributů, které chceme zaindexovat. Pokud bychom chtěli zaindexovat vazby mezi uzly, budeme postupovat analogicky jako s nastavením uzlů s rozdílem, že budeme upravovat relationship_auto_indexing a relationship_keys_indexable. Posledním krokem je zadání příkazu index --create node_auto_index -t Node do konzoly. Dojde tak k vytvoření indexu pro uzly. Místo node_auto_index se dá použít jakýkoliv název. Pomocí příkazu index –indexes se dá zkontrolovat, jestli se index opravdu vytvořil. Při dotazování se potom používá tato syntaxe: START n=node:node_auto_index(property="value") return n;. (Mulholland, 2012) Verze 2.0 umí manipulovat s indexací prostřednictvím Cypher query language. Tudíž již není potřeba zasahovat do souboru neo4j.properties. Pro vytvoření slouží příkaz CREATE INDEX ON :Label(property). Pokud chceme pracovat s indexovaným atributem, dochází k tomu automaticky, aniž bychom ho museli volat jako ve verzi 1.9 (START n=node:node_auto_index(property="value") return n;). Výjimkou jsou pouze konfliktní situace, kdy může být použito více indexů. Pak je potřeba pomocí příkazu USING INDEX n:Label(property) definovat, s kterým indexem se má pracovat. V této verzi lze indexy i dokonce mazat příkazem DROP INDEX ON :Label(property). Seznam vytvořených indexů se dá získat příkazem :schema. (Neo Technology, 2014d) 2.4.6

Upgrade

Při přechodu na novou verzi Neo4j, je potřeba udělat upgrade stávající databáze. Po instalaci nové verze Neo4j, je nutné u databáze v konfiguračním souboru neo4j.properties odstranit komentář #allow_store_upgrade=true. Podmínkou však je, že upgrade se dá provést jen pro předchozí verzi. Neboli je možné provést upgrade z verze 1.8 na 1.9, ale nikoli z 1.8 na 2.0. (Neo Technology, 2014i) 2.4.7

Standalone mode (REST API)

Neo4j umožňuje přijímat požadavky ve formátu JSON přes protokol HTTP. Vždy je nutnost si uvědomit, na jakou adresu je potřeba požadavek odeslat. Kořenový adresář je /db/data/, takže adresa může vypadat například takto:

22

Teoretická část

http://localhost:7474/db/data/. Pokud chceme pracovat s uzly odesíláme požadavek na /db/data/node, pro práci s indexy /db/data/schema/index a podobně. Na každý požadavek existuje také odpověď o vykonání požadavku. (Neo Technology, 2014h) Výhodou REST API je, že se dá použít ve všech programovacích jazycích, které podporují formát JSON a HTTP protokol. Jedním z takových může být například JAVA. Použití REST API z Javy je dokonce popsáno v dokumentaci Neo4j, kde jsou ustanoveny základní postupy. Nevýhodou je, že komunikace s Neo4j prostřednictvím REST API je vždy pomalejší než embedded mode. (Robinson, Webber a Eifrem, 2013) 2.4.8

Embedded mode (JAVA)

Pro použití tohoto řešení je potřeba stáhnout knihovnu Neo4j a to buď přímo jako jar soubory nebo vložit do projektu dependency. Pokud chceme pracovat v embedded mode, je potřeba nejdříve vytvořit spojení s databází. Následující ukázka kódu vytvoří spojení s existující databází (pokud zadaná cesta neexistuje, vytvoří novou databázi): graphDb = new GraphDatabaseFactory().newEmbeddedDatabase(path);

Pro provádění operací nad zadanou databází je vše potřeba mít obaleno transakcí. // Java 1.7 try (Transaction tx = graphDb.beginTx()) { // Operace // V případě úspěšné transakce je potřeba zavolat tx.success(). // V případě neúspěšné transakce tx.failure(). tx.success(); } // Java 1.6 a nižší verze Transaction tx = graphDb.beginTx(); try { // Operace tx.success(); } finally { // Uzavření transakce tx.close(); }

Pokud se zavolá success, tak jsou operace potvrzeny a vykonají se i v databázi. Naopak failure požadované operace nad databází nevykoná, respektive je vše vráceno

Teoretická část

23

do původního stavu před transakcí. Pokud například chceme v jedné transakci přidat tisíc uzlů, tak nejdříve se tyto uzly vytvoří v operační paměti a až potom se na základě úspěšnosti transakce buď do databáze přidají a nebo nepřidají. Pro uzavření spojení s databází slouží graphDb.shutdown().(Neo Technology, 2014c) 2.4.9

Grafové algoritmy

Neo4j má zabudované základní grafové algoritmy, které usnadní práci při hledání všech možných cest nebo nejkratší cesty na základě počtu hran. Pro nalezení nejkratší cesty na základě váhy hran nebo uzlů je možné použít Dijkstrův algoritmus nebo A* algoritmus, které jsou implementovány přímo v Neo4j. Pro oba algoritmy je nutno definovat, jak budou uzly procházeny (expandovány), neboli které uzly a hrany má algoritmus do svého procházení zahrnout. K tomu slouží expander. Druhým kritériem je určit cost evaluator, který definuje jak budou vypočteny skutečné vzdálenosti (váhy) mezi dvěma uzly. Expander a cost evaluator využívá jak Dijkstra, tak A*. A* algoritmus navíc pro svou heuristickou funkci potřebuje estimate evaluator. (Robinson, Webber a Eifrem, 2013)

2.5

Grafové algoritmy

Grafové algoritmy se zabývají v teorii grafů různým výčtem úloh. Pod tyto úlohy může spadat například problém nejkratší cesty, nalezení minimální kostry grafu a mnoho dalších. Ze zadání bakalářské práce vyplývá, že klíčové budou grafové algoritmy, které řeší problém nejkratší cesty v ohodnocených a orientovaných grafech. (Even 2012). Grafové algoritmy pro nalezení nejkratší by se dali rozdělit následovně. První skupinu budou tvořit algoritmy, které najdou nejkratší cesty mezi všemi uzly v grafu. Potom jsou algoritmy, které hledají nejkratší cestu z počátečního uzlu do všech ostatních uzlů a do poslední skupiny patří algoritmy, které hledají cestu z počátečního do koncového. V následujících kapitolách budou vysvětleny blíže čtyři základní algoritmy, ale samozřejmě algoritmů existuje více. 2.5.1

Floyd-Warshallův algoritmus

Autoři jsou Robert Floyd a Stephen Warshall. Algoritmus najde nejkratší cestu mezi všemi uzly v grafu. Vstupem je matice, jejíž hodnoty reprezentují váhy orientovaných hran do sousedních uzlů. Cílem algoritmu je postupně sestavit takovou matici, která bude tvořit hodnoty nejkratších cest mezi všemi uzly. Mezi stejnými uzly jsou v matici nastaveny nulové hodnoty, takže nuly vzniknou na diagonále matice. Tam kde zatím není známá cesta je hodnota nekonečno. Algoritmus provede k iterací, kde k je počet uzlů v grafu. Každá taková iterace představuje, kolik může mít nejkratší cesta přechodných uzlů. Přechodné uzly jsou takové uzly, které leží mezi počátečním a koncovým uzlem. V první iteraci nejsou povolené žádné přechodné uzly, v druhé je povolen jeden přechodný uzel, ve třetí dva a tak dále. V každé takové iteraci, pokud mezi dvěma uzly najde kratší cestu, přepíše původní

24

Teoretická část

hodnotu novou. V poslední iteraci k, je už jisté, že budou nalezeny vždy nejkratší cesty mezi uzly. // http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm let dist be a |V| × |V| array of minimum distances initialized to infinity for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) // the weight of the edge (u,v) for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if

V nejhorším případě bude mít algoritmus složitost (| V |3 ) . (Skiena 2008). Bohužel tímto je v matici vyjádřena pouze hodnota nejkratší cesty. Pokud je potřeba zjistit všechny uzly této nejkratší cesty, je nutno implementovat například strom, který zachytí nejkratší cestu a její uzly. (Wikipedia, 2014b) 2.5.2

Dijkstrův algoritmus

Tento algoritmus objevil v roce 1956 Edsger Dijkstra. Vstupními parametry pro tento algoritmus jsou množina uzlů, délky hran a počáteční uzel. Podmínkou je, aby hrany nebyly ohodnocené záporně. Algoritmus používá prioritní frontu, do které si ukládá uzly podle vzdálenosti od počátečního uzlu. Algoritmus s prioritní frontou funguje následovně. Vždy vybere z fronty uzel s nejnižší vzdáleností od již zpracované části. Na začátku vybere počáteční uzel, protože má nastavenou hodnotu 0 (všechny ostatní mají hodnotu nekonečno). Z vybraného počátečního uzlu zjistí hodnoty cest (váhu) do všech sousedních uzlů a hodnoty si zapamatuje (změní hodnoty nekonečno těchto sousedních uzlů na skutečné hodnoty). Zároveň tento počáteční uzel označí jako vyřešený (uvolní se z množiny otevřených uzlů a přidá do množiny uzavřených uzlů). Následně vybere uzel z prioritní fronty, který není vyřešený (nenachází se v množině uzavřených uzlů) a zároveň do něj vede nejkratší cesta (při stejných hodnotách lze vybrat libovolně). Algoritmus nadále probíhá analogicky a tento postup se opakuje, dokud algoritmus neprojde všechny uzly. Asymptotická časová složitost závisí na implementaci prioritní fronty. V nejlepším případě bude časová složitost (| R |  | V | log | V |) , za použití Fibonacciho haldy. V nejhorším případě (| N | 2 ) . (Wikipedia, 2014a)

Teoretická část

25

// http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm function Dijkstra(Graph, source): for each vertex v in Graph: dist[v] := infinity ; previous[v] := undefined ; end for dist[source] := 0 ; Q := the set of all nodes in Graph ; while Q is not empty: u := vertex in Q with smallest distance in dist[] ; remove u from Q ; if dist[u] = infinity: break ; end if for each neighbor v of u: alt := dist[u] + dist_between(u, v) ; if alt < dist[v]: dist[v] := alt ; previous[v] := u ; decrease-key v in Q; end if end for end while return dist[], previous[]; end function

2.5.3

Bellman-Fordův algoritmus

Richard Bellman a Lester Ford jsou tvůrci tohoto algoritmu. Na rozdíl od Dijkstrova algoritmu je schopný najít nejkratší cestu i když jsou hrany záporné, podmínkou však je, že neobsahuje cyklus záporné délky. Tento problém je však schopen zachytit, což je vidět v přiloženém pseudokódu. Nejdůležitější částí algoritmu je operace relax, která na základě konkrétní hrany porovnává vzdálenosti mezi uzly. Konkrétně funguje tak, že sečte hodnotu hrany a dosavadní zjištěnou délku cesty do počátečního uzlu hrany. Pokud je výsledná hodnota menší než dosavadní zjištěná délka cesty do koncového uzlu hrany, tak se výsledná hodnota (nová nejkratší cesta) přepíše aktuální hodnotu (původní nejkratší cestu). Operace relax se provede pro všechny hrany v grafu. Zmíněný postup je potřeba pro správný výpočet provést tolikrát, kolik má graf uzlů mínus jedna. (Mička, © 2008-2014)

26

Teoretická část

// http://www.algoritmy.net/article/7478/Bellman-Forduv-algoritmus function <predecessors> Bellman-Ford(G, source) for i in 1 to |U| do distance[i] = +inf predecessors[i] = null distance[source] = 0 for i in 1 to (|U| - 1) do for each Edge e in Edges(G) do // Relax if distance[e.from] + length(e) < distance[e.to] do distance[e.to] = distance[e.from] + length(e) predecessors[e.to] = e.from // Kontrola, že neobsahuje cyklus záporné délky for each Edge e in Edges(G) do if distance[e.from] + length(e) < distance[e.to] do error("Graf obsahuje cyklus zaporne delky") return predecessors

2.5.4

A* algoritmus

Jedná se o vylepšený Dijkstrův algoritmus pomocí heuristické funkce. Heuristickým prvkem může být například vzdálenost vzdušnou čarou mezi počátečním městem a cílovým městem. A* algoritmus expanduje cestu pomocí funkce f(n) = g(n) + h(n). Funkce g(n) je známá z Dijkstrova algoritmu, je to délka (cena) cesty z počátečního uzlu na základě ohodnocení hran. Funkce h(n) je ona zmíněná heuristická funkce a udává kolik zbývá do cílového uzle. A* algoritmus volí takovou strategii, že se snaží najít nejkratší možnou cestu, ale zároveň se snaží expandovat co nejméně cest. (Robinson, Webber a Eifrem, 2013)

Metodika

27

3 Metodika Teoretická část obsahuje objasněnou problematiku, z které bude vycházet návrh samotného řešení. Samotné řešení bude probíhat v následujících krocích. Na úvod bude potřeba zvolit vhodný typ databázového systému pro tuto problematiku. Po výběru databázového systému bude nutné vytvořit návrh samotné databáze. Pro lepší pochopení problematiky však bude vhodné zpětně zrekonstruovat návrh relační databáze ze zapůjčených dat a až potom vytvořit návrh nové databáze. Návrh databáze bude dbát na dodržování standardů a pravidel, ale také na použitelnost pro grafové algoritmy. Dále bude potřeba databázi vytvořit, respektive naplnit daty. Data musí být upravena do určitého tvaru, zde pomůže zrekonstruovaná relační databáze a pomocí SQL dotazů nad daty, dojde k vhodné selekci dat. Po zhotovení databáze budou vybrány vhodné algoritmy pro nalezení nejkratší cesty. Výběr algoritmů se bude opírat o teoretické poznatky. Vybrané algoritmy budou implementovány v programovacím jazyce JAVA. Tato aplikace bude schopná komunikovat s vytvořenou databází. V závěru samotného řešení dojde k otestování funkčnosti aplikace. Především půjde o otestování nalezení nejkratší cesty. Testována bude také rychlost algoritmů a výsledky budou stručně prezentovány.

28


4 Návrh samotného řešení 4.1

Výběr typu databáze

Pro tuto problematiku byla zvolena grafová databáze a to hned z několika důvodů. Hlavním faktorem pro změnu na grafovou databázi je vyšší výkonnost než u relační databáze. U relační databáze klesá výkonnost s růstem počtu, naopak u grafových databází zůstává výkonnost konstantní i když roste množství uzlů a vazeb. Příčinou je odlišný způsob prohledávání příslušných dat. Zatímco u relačních databází se prohledává celá množina dat, u grafových databází je to vždy jen určitá část. Jedná se o tu část, která je přímo propojená s dalšími uzly pomocí hran. Další výhodou je flexibilita. Pozdější zásahy do struktury databáze nejsou problematické. Následující tabulka zachycuje výkonnost mezi grafovou a relační databází. Srovnání databází proběhlo na datech, které tvořily osoby a každá osoba měla v průměru padesát přátel, cílem bylo získat přátele konkrétní osoby. (Robinson, Webber a Eifrem, 2013) Tab. 3

Srovnání rychlosti relační s grafovou databází

Databáze Relační Grafová Grafová

Počet osob

Čas dotazu

1000 1000 1000000

I2000ms 2ms 2ms

Zdroj: Mahata, 2014

Po rozhodnutí použít grafovou databází, bylo ještě potřeba vyřešit, kterou konkrétní grafovou databázi použít. Grafových databází existuje poměrně dost a nakonec pro tuto práci bylo použito Neo4j. Důvody byly následující. Neo4j je vhodné pro začátečníky, má přehledně zpracovanou dokumentaci, projekt se neustále a rychle vyvíjí, podporující komunita je velká. Poslední dva důvody nasvědčují tomu, že vývoj Neo4j v blízké budoucnosti jen tak neskončí, což je další pozitivum. Tím největším důvodem ovšem je Cypher query language. Je to dotazovací jazyk, který je výkonný, jednoduchý a tudíž se dá rychle osvojit.

4.2

Optimální grafový algoritmus

Jelikož ohodnocení hran nebude záporné, připadají v úvahu všechny algoritmy zmíněné v teoretické části. První algoritmus, který rozhodně nepřipadal v úvahu je Floyd-Warshallův algoritmus a je to kvůli jeho náročné asymptotické složitosti (doplnit hodnotu). Další rozhodování probíhalo mezi Dijkstrovým a BellmanFordovým algoritmem. Co se týče časové složitosti, vychází z této dvojice a i celkově nejlépe Dijkstrův algoritmus. Je to z toho důvodu, že Dijkstrův algoritmus vybere uzel s nejmenší váhou, který nebyl zpracován a dále vychází jen z hran


29

z tohoto uzlu. Naproti tomu Bellam-fordův algoritmus prochází vždy všemi hranami. S výběrem Dijkstrova algoritmu je vždy potřeba se zamyslet, jestli by se nedal použít A* algoritmus, který Dijsktrův algoritmus vylepšuje. Aby mohl být A* použit, je nutné mít data pro sestavení heuristické funkce. Zdrojová data obsahují u zastávek jejich zeměpisnou šířku a délku (viz schéma relační databáze v další kapitole Obr. 2). Z těchto údajů se dá vypočítat vzdálenost vzdušnou čarou mezi zastávkami. Tato vypočtená vzdálenost může sloužit jako heuristická funkce pro A*, a proto bude nejvhodnější použit tento algoritmus. Pro srovnání rychlosti a funkčnosti, bude kromě A* algoritmu, implementován i Dijkstrův algoritmus.

4.3


Návrh grafové databáze vycházel ze zdrojových dat, které tvořily relační databázi. Z těchto dat bylo potřeba nejprve zpětně sestavit relační databázi pro lepší pochopení problematiky. Jedná se o jízdní řády pro rok 2013. Pro vytvoření relační databáze jsem zvolil MySQL a databázi navrhl v programu MySQL Workbench. Výsledná relační databáze vypadá následovně.

30

Obr. 2


Schéma relační databáze

Databáze obsahuje celkem šest tabulek. Tabulka agency obsahuje informace o dopravcích. Routers zachycuje konkrétní typy vlaků a ke kterému dopravci spadají (agency_id). Calendar_dates uchovává dny, kdy vlaky jezdí. Trips zachycuje určitou jízdu konkrétního vlaku (route_id) a dny kdy vlak jezdí (service_id). Zastávky vlaků jsou uloženy v tabulce stops včetně zeměpisné šířky a délky. Stop_times zachycuje jízdu vlaku (trips_id) konkrétní zastávkou (stop_id) a v určitý čas. Z výsledné databáze už se dalo uvažovat o tom, jak by se tato relační databáze dala zachytit v grafové databázi. Při návrhu byl kladen důraz na tři požadavky. Jak už to bývá při návrhu jakékoli databáze, prvním požadavkem je co nejmenší velikost celkové databáze, neboli vyhnout se zbytečné redundanci. Druhý požadavek byl kladen na časovou náročnost získávání spojů pomocí grafových algoritmů. Druhý požadavek měl větší prioritu než první. Posledním požadavkem bylo zachovaní určité struktury z relační databáze, neboli neměnit logickou myšlenku databáze relační. Takže by se dalo říct, že nejde o vytvoření zcela nového schématu databáze, ale spíše o převod relační databáze do grafové s drobnými úpravami. Pro lepší přehlednost byly zachovány názvy atributů. Na následujícím obrázku je zachyceno, jak vypadá finální návrh grafové databáze při převodu z relační databáze. Jak bylo tohoto návrhu dosaženo, bude objasněno dále.


Obr. 3

31


Nejzásadnější rozdíl mezi grafovou a relační databází z pohledu modelování, je ve vazbách mezi entitami. Jelikož grafová databáze obsahuje vazby mezi uzly přímo, není tak potřeba „pomocných“ tabulek, které by tyto vazby zachycovaly, jako tomu je u relační databáze. Prvním krokem tedy je najít takové tabulky a vynechat je z návrhu grafové databáze. V návrhu relační databáze (Obr 2.) je taková tabulka v podstatě jen jedna a to trips. Ta však z důvodu, aby nevznikaly redundantní data zůstala. Tudíž budou brány v potaz všechny tabulky. Z toho vyplývá, že se dají také vynechat pomocné unikátní identifikátory (id), které jsou zároveň primárními klíči a které slouží v relační databázi k vytvoření vztahů v „pomocných“ tabulkách za pomoci cizího klíče. Takže již není potřeba uchovávat agency_id, stop_id a podobně. Výjimku budou tvořit dočasné id, které nám můžou usnadnit import dat z relační databáze a po importu dojde k jejich smazání. Budou se nacházet především tam, kde bez id není možné vytvořit jednoduchý primární klíč. V tomto případě jsem zachoval route_id a service_id. Primární a cizí klíče v Neo4j vůbec neexistují, avšak za primární klíč by se dalo považovat id uzlu. Každému vytvořenému uzlu je automaticky přiděleno unikátní id, které se nedá změnit. Při převodu záznamů z tabulek na uzly, je potřeba určit, o jaké uzly se jedná, respektive pod kterou tabulku v relační databázi by spadaly. Dalo by se říci, že v grafové databázi jsou všechny uzly jakoby v jedné tabulce a je vhodné je od sebe rozlišit, není to však povinností. K tomu slouží Lables. Takže při převodu záznamu z tabulky agency, vznikne uzel se stejnými daty a navíc bude mít label Agency. Z tabulky routes bude mít uzel label Route a podobně. Jména labels byly zachovány podle názvů tabulek. Takže vznikly následující labels:  Agency  CalendarDates

32


 Route  Stop  StopTimes  Trip V grafové databázi je potřeba pracovat s hranami, které reprezentují vazby mezi uzly. Každé vazbě je nutno nastavit, jakého je typu (type). Dalo by se říci, že typ hrany je něco podobného jako labels u uzlů a slouží také k bližší specifikaci. Typ vazby je však důležitější než labels, protože tyto vazby určují, jak se bude grafem procházet. Z toho plyne, že typ vazby, na rozdíl od labels, je povinný. Databáze bude obsahovat tyto typy vazeb:  AGENCY  CALENDAR  ROUTE  STOP  STOPTIMES  TRIP  RELATED  CHANGE Typy vazeb se vždy píší velkými písmeny. Labels a typy vazeb se v tomto případě shodují, až na vazbu RELATED a CHANGE. Jelikož se jedná o grafovou databázi, je zde možné bez problému zachytit spoje mezi jednotlivými zastávkami na stejné trase. V tom je hlavní síla grafové databáze. V relační databázi vzniká docela problém při zachycení spojů. V poskytnuté relační databázi to firma vyřešila tak, že jsou záznamy z tabulky stops_times seřazeny pod sebou, tak jak je možné v trase jet, za předpokladu že záznamy mají stejný atribut trip_id, který říká, že se jedná o stejnou trasu. Takže máme například situaci, kdy tabulka stops_times obsahuje pod sebou tři záznamy, které obsahují stanice v následujícím pořadí A,B,C. Všechny tři záznamy mají stejné trip_id. Pak tento zápis říká, že je možný spoj ze stanice A do B a z B do C, nikoli z B do A nebo z C do A a podobně. Zatímco v relační databázi kontroluje až samotná aplikace jestli je spoj možný, tak v grafové databázi se o to stará samotná databáze. Tyto spoje jsou v grafové databázi zachyceny vazbou RELATED. Vedle spojů mezi jednotlivými zastávkami na stejné trase, budou existovat i přestupy mezi vlaky z různých tras. Poskytnutá relační databáze tyto situace nezachycuje vůbec, za to grafová databáze je schopná přestupy opět zachytit bez problému. Teoreticky by se tyto přestupové vztahy daly zřejmě zachytit i v relační databázi, ale prakticky by vznikla příliš obsáhlá tabulka, co se po stránce záznamů týče a těžko by se v ní vyhledávalo v rozumném čase. V grafové databázi jsou tyto vazby typu CHANGE.


Obr. 4

33

Návrh spojů a přestupů

Schéma (Obr. 4) znázorňuje spoje a přestupy, jak jsou zachyceny v databázi. Na obrázku jsou zachyceny dva vlaky, označeny číslem jedna a dva. Dále jsou na obrázku čtyři zastávky A až D. Vlak číslo jedna může jet ze zastávky A do B a následně do C, díky vazbě RELATED. Vlak číslo dva ze zastávky A do D. Je zde zachycen i přestup z vlaku jedna na vlak číslo dva ve stanici A, tento přestup je zachycen vazbu CHANGE. Z toho plyne, že na jiný vlak se dá přestoupit pouze, pokud se oba nachází ve stejné stanici. Ještě zde budou rozhodovat jiná kritéria pro přestup, ale ty budou objasněny dále. Kromě typu vazby, je potřeba určit i směr vazby. V Neo4j musí mít každá hrana směr, nejdou vytvářet neorientované hrany. Směr tak v podstatě nemá žádnou váhu u vazeb, které jen reprezentují nějaký všeobecný vztah a stačilo by, kdyby tyto hrany byly neorientované. Směr v tomto případě bude určovat, který uzel na vazbě se bere jako počáteční a který jako koncový. Pokud jsou propojovány uzly, které mají label Route s uzly, které mají label Agency, nezáleží jestli vazba bude vycházet z uzlu Route nebo naopak z uzlu Agency. Díky správnému dotazování, jsme schopni získat data, bez ohledu na směr vazby. Nebude to mít vliv ani na výkon. Jedinou zásadou je, že pokud bude vycházet vazba z Route do Agency, pak je potřeba, aby se toto pravidlo dodrželo u všech vazeb mezi Route a Agency. Respektive, že směr vazby mezi těmito uzly se nebude střídat. Z toho je i patrné, že v takových případech není potřeba tvořit obousměrné vazby, neměly by žádný smysl. Více vazeb mezi uzly má smysl jen tehdy, pokud jde například o graf reprezentující cesty mezi městy (cest mezi městy může být více). Posledním a nejdůležitějším krokem při modelování grafové databáze je správně nastavit indexaci dat. Tento krok není povinný, ale jak již bylo zmíněno v teorii, díky indexaci dojde k rychlejšímu dotazovaní nad určitou množinou dat. Indexaci je možné vytvořit i po naplnění daty, ale je potřeba data potom aktualizo-

34


vat. Proto je lepší indexy vytvořit před naplněním databáze daty. V podstatě by se indexy daly rozdělit do dvou skupin. První skupinu budou tvořit indexy, které slouží pro dotazování nad atributy, které budou použity v aplikaci. Do druhé by se daly zařadit dočasné indexy, které pomáhají při importu dat a po importování dat dojde k jejich odstranění (tohle je možné od verze 2.0). Do první skupiny bude spadat atribut stop_name, který patří uzlu Stop. V aplikaci podle něj bude hledána počáteční a cílová stanice. Do druhé skupiny budou patřit atributy agency_id, route_id a service_id. Na základě výše zmíněných informací už se dala vytvořit grafová databáze. V teoretické části byly ukázány možnosti importu dat. Přes samotnou konzoli to nebylo možné z důvodu objemu dat a tak tato možnost nepřipadala v úvahu. Rozhodoval jsem se mezi hotovým řešením Neo4j (CSV) Batch Importer a vlastním řešením. Zvolil jsem vlastní řešení z důvodu lepší kontroly nad daty. Vlastní řešení jsem napsal ve dvou variantách jak embedded, tak standalone mode přes REST API. Programy fungují tak, že čtou ze souboru připravené dotazy v cypher query language a vykonají je nad příslušnou databází. Pro embedded mode je klíčový ExecutionEngine, který slouží k vykonávání dotazů. Knihovna s ExecutionEngine je součástí základní knihovny Neo4j. graphDb = new GraphDatabaseFactory().newEmbeddedDatabase("pathDb"); ExecutionEngine engine = new ExecutionEngine(graphDb); engine.execute("query");

V standalone mode jsem pro REST API využil knihovnu neo4j-rest-graphdb, která není součástí základní knihovny Neo4j. Tato knihovna není bohužel ani zdokumentovaná v oficiální dokumentaci a obsahuje dvě klíčové třídy RestAPIFacade a RestCypherQueryEngine. RestAPI graphDb = new RestAPIFacade("http://localhost:7474/db/data/"); QueryEngine engine = new RestCypherQueryEngine(graphDb); engine.query("query", Collections.EMPTY_MAP);

Pro úspěšný import dat bylo potřeba si připravit dotazy v cypher query language, ty následně uložit do souborů a postupně spustit v jednom výše zmíněném řešení. Z MySQL jsem si exportoval potřebná data do csv souborů, které jsem otevřel pro další úpravu v Excelu. V Excelu jsem si vedle dat sestavil potřebné cypher dotazy a ty poté zkopíroval do textového souboru. Dotazy jsem vytvářel postupně po jednotlivých tabulkách. Dotazy vypadají následovně (ukázka přeměny jednoho záznamu na uzel z každé tabulky). Uzel Agency: CREATE (:Agency{agency_name: 'ARRIVA Morava a.s.', agency_url: 'http://www.zeleznicedesna.cz', agency_timezone: 'Europe/Prague', agency_phone: '420583242242'});


35

Uzel Route: MATCH (agency:Agency{agency_name:'ARRIVA Morava a.s.'}) CREATE (route:Route{route_id: '7029', route_short_name: 'Os 13752', route_long_name: '', route_typ: '2', route_desc: '¤¤R293'}), (route)-[:AGENCY]->(agency);

Vyhledá uzel Agency a uloží do proměnné agency. Potom vytvoří nový uzel Route a zároveň si ho uloží do proměnné route. Posledním krokem je vytvoření vazby typu AGENCY, která přiděluje uzlu Route příslušnou agenturu z proměnné agency. Dalo by se to rozdělit i na dva dotazy. Nejdříve vytvořit uzel Route, to by byl první dotaz. Druhý dotaz by vytvořil vzabu, neboli vyhledání uzlu Agency, nově vytvořeného uzlu Route a propojení vazbou AGENCY. První varianta je však efektivnější a časově vyjde rychleji, protože není potřeba vyhledat uzel Route, který je uložen do proměnné route přímo při vytváření uzlu. Uzel Stop: CREATE (:Stop{stop_name: 'Smolensk', stop_lat: '54.8387', stop_lon: '32.4392'});

Uzel CalendarDates: CREATE (:CalendarDates{service_id:0, date:'20121210', exception_type:1});

Uzel Trip: MATCH (calendar:CalendarDates) WHERE calendar.service_id=477 MERGE (trip:Trip{trip_id:3000, service_id:477}) CREATE (trip)-[:CALENDAR]>(calendar);

Je tu aplikován stejný postup jako při vytváření uzlu Route, avšak při vytváření uzlu Trip, je příkaz CREATE nahrazen příkazem MERGE. Jde o to, že u Route se vytvořil jeden uzel a ten se pomocí vazby spojil zase pouze s jedním uzlem Agency. U Trip dochází k vytvoření jednoho uzlu, ale vychází z něj více vazeb na další uzly Calendar. Například pokud by jeden vytvořený uzel Trip, měl být spojen vazbami CALENDAR s pěti již vytvořenými uzly CalendarDates a použil by se příkaz CREATE, tak by došlo k vytvoření pěti stejných uzlů Trip a pěti vazeb CALENDAR, namísto vytvoření jednoho uzlu Trip. MERGE v podstatě říká najdi požadovaný uzel Trip, pokud neexistuje, tak ho vytvoř. Díky tomu dojde k vytvoření pouze unikátního uzlu Trip. Bude vytvořen pouze jeden uzel Trip a vazby CALENDAR na příslušné uzly CalendarDates. Uzel StopTimes: MATCH (stop:Stop),(route:Route),(trip:Trip) WHERE stop.stop_name='Lčovice' AND route.route_id=0 AND trip.trip_id=0 MERGE (stopTimes:StopTimes{arrival_time: '04:00:00', departure_time: '04:00:00', stop_sequence: 0, pickup_type: 0, drop_off_type: 0}) CREATE (stopTimes)[:STOP]->(stop), (stopTimes)-[:ROUTE]->(route), (stopTimes)-[:TRIP]->(trip);

36


Bylo potřeba si vytvořit algoritmus, který by prošel databázi a vazbou CHANGE spojil všechny uzly StopTimes, mezi kterými je realizovatelný přestup. Algoritmus jsem navrhl následovně. Prochází postupně všechny zastávky, neboli uzly, které reprezentují zastávku Stop. Pro každý uzel Stop vytvoří spojový seznam, který budou tvořit uzly StopTimes pro příslušnou zastávku. Tyto uzly StopTimes ze seznamu se budou porovnávat mezi sebou a podle pravidel spojovat vazbou. Prvním pravidlem je, že se nevytvoří vazba na stejný uzel (sám na sebe) a zároveň nesmí jít o stejnou trasu, neboli nechci přestup na vlak, který jede identickou trasu třeba o hodinu později. Další kontrolu bude představovat časové omezení, jeli možné přestoupit v požadovaném čase. V projektu je tento algoritmus vytvořen v třídě RouteChange.java. Třída má metodu run s jedním parametrem, kterým je hodnota v minutách. Tato hodnota představuje možný čas na přestup.

4.4

Grafový algoritmus

Pro porovnání výsledků jsem použil jak Dijkstrův, tak A* algoritmus. Je potřeba nejdříve implementovat finder, který určuje o jaký algoritmus prohledávací se bude jednat a jeho parametry expander, cost evaluator a pro A* ještě estimate evaluator. //Dijkstra PathFinder<WeightedPath> finder = GraphAlgoFactory.dijkstra(expander, costEvaluator); //A* PathFinder<WeightedPath> finder = GraphAlgoFactory.aStar(expander, costEvaluator, estimateEvaluator); WeightedPath path = finder.findSinglePath(this.startStopNode, this.endStopNode);

4.4.1

Expander

Jak již bylo řečeno v teoretické části, expander určuje pomocí pravidel, jak procházet graf. V tom jednodušším případě se dá vystačit s třídou PathExpanders. Tato třída má pět statických metod, pomocí kterých se dá nastavit procházení grafem. Metody umožní nastavit typy vazeb a směry pro procházení grafem. Pokud je procházení grafem specifičtější a existují složitější podmínky, je potřeba vytvořit si vlastní expander. Jelikož bylo potřeba omezit určité uzly, byl zvolen tento způsob. Půjde o třídu Expander, která implementuje rozhraní PathExpander. Toto rozhraní má dvě metody expand a reverse. Je potřeba obě metody překrýt. V metodě expand se určuje způsob procházení a to konkrétně tak, že z parametru metody je získána cesta a na základě této cesty (většinou podle koncového uzle) je rozhodnuto, které typy vazeb metoda vrátí pro další procházení. V tomhle případě bylo


37

nutno se vyhnout všem uzlům Stops, kromě počáteční a cílové stanice. Jde o to, že za počáteční a koncový uzel se berou uzly Stops, které ale reprezentují jen jméno zastávky, skutečné zastávky s časy zachycují až uzly StopTimes. Jelikož je potřeba zvolit vždy jeden počáteční a jeden koncový uzel pro Dijsktrův algoritmus nebo A*, je jedinou možností zvolit uzly Stops. Uzly StopTimes se v tomhle případě nedají jako vstupní nebo koncové použít z toho důvodu, že pokud chceme například vyjíždět ze zastávky Brno, tak by byla vytvořena množina uzlů StopTimes a ne jeden konkrétní uzel. @Override public Iterable expand(Path neoPath, BranchState state) { if (neoPath.endNode().hasLabel(Labels.StopTimes) && (neoPath.endNode().getSingleRelationship(Relationships.STOP, Direction.OUTGOING).getEndNode().getId() != endNode.getId())) { return neoPath.endNode().getRelationships(direction, Relationships.RELATED, Relationships.CHANGE); } else if (neoPath.endNode().hasLabel(Labels.Stop) && (neoPath.endNode().getId() == startNode.getId())) { return neoPath.endNode().getRelationships(Direction.INCOMING, Relationships.STOP); } else { return neoPath.endNode().getRelationships(direction, Relationships.STOP); } }

Vytvořený exander rozlišuje tři situace. První podmínkou je, že vrací vazby RELATED a CHANGE ve směru OUTGOING, pokud konečný uzel cesty je StopTimes a zároveň to není uzel cílové stanice. Pokud se algoritmus nachází v počáteční stanici, konkrétně v uzlu Stops, pak jsou navráceny vazby STOP ve směru INCOMING z důvodu získání uzlů StopTimes. Poslední variantou je získání vazby STOP ve směru OUTGOING, což povede k získání cílového uzlu STOP. Bylo abstrahováno od problému, že vlak může jet jen v určité dny. Důvodem bylo, že mi firma nestihla poskytnout potřebné informace pro tuto problematiku. 4.4.2

Cost Evaluator

Cost evaluator bude vypočítávat vzdálenost mezi dvěma uzly na základě času. Čas se určí pomocí odjezdů a příjezdů vlaků do zastávek. Pokud se pro cost evaluator používají hodnoty z ohodnocení hran, stačí jen zadat název atributu hrany, kde je požadovaná hodnota. Bohužel v této aplikaci to nebylo takto jednoduché a bylo potřeba si vytvořit vlastní cost evaluator, který reprezentuje třída Cost. Je to z toho důvodu, že doba ujetí trasy mezi dvěma uzly se vypočítává z atributů arrival_time a departure_time, které se nachází u uzlů StopTimes. Tato třída implementuje rozhraní CostEvaluator. Bylo nutné překrýt metodu getCost, která na základě dvou parametrů (vazby a směru) vrátí hodnotu. Metoda getCost se řídí čtyřmi pravidly.

38


Prvním pravidlem je, že pokud je parametrem vazba, jejíž počáteční uzel je zastávka Stop a koncový uzel StopTimes, tak se hodnota vypočte jako rozdíl mezi výjezdem vlaku a času, od kterého se spojení hledá. Jedná se vlastně o rozdíl mezi odjezdem vlaku, který se zjistí z atributu deprature_time v uzlu StopTimes a časem, od kterého chce uživatel spoj nalézt (buď zadaný čas nebo aktuální čas). Druhým pravidlem je, že pokud vazba obsahuje počáteční i koncový uzel StopTimes, tak se časy vypočítávají z rozdílů atributů arrival_time. Existuje však výjimka, že pokud se jedná o uzly StopTimes a zároveň počáteční uzel z této dvojice je i počáteční stanicí, tak se bere rozdíl mezi arrival_time a departure_time. Jde o to, že při nástupu na vlak v počáteční stanici je podstatné, kdy vlak odjíždí a ne kdy přijíždí. V podstatě tento stejný problém vzniká při přestupech na jiný vlak. Opět je potřeba zachytit rozdíl mezi arrival_time následujícího uzlu a departure_time počátečního uzlu. Poslední pravidlem je, že situace kdy vazba z parametru má koncový uzel Stop, tak je navrácena hodnota nula. 4.4.3

Estimate evaluator

Estimate evaluator vypočítává vzdálenost mezi dvěma stanicemi vzdušnou čarou na základě zeměpisné šířky a délky. Evaluator implementuje rozhraní EstimateEvaluator, které má jednu povinnou metodu a to getCost. Parametry pro tuto metodu jsou aktuální uzel a konečný uzel. Výsledek není vrácen v kilometrech, ale v kilometrech přepočtené na milisekundy. Je to z toho důvodu, že CostEvaluator a EstimateEvaluator musí být ve stejných jednotkách pro korektní výpočet. Proto jsou jednotky v milisekundách jako tomu je u CostEvaluatoru. Pro převod z kilometrů na milisekundy je potřeba určit vhodnou průměrnou rychlost vlaků. Průměrná rychlost a její vliv bude rozebrán v další kapitole.

4.5

Testování v praxi

Po vytvoření celé aplikace bylo potřeba otestovat její funkčnost. Především otestovat nalezení nejkratší cesty. Pro ověření se daly porovnat výsledky přes jizdnirady.idnes.cz. Bohužel k testování došlo v roce 2014, ale na aplikaci se začalo pracovat již v roce 2013 a proto také byly výchozí data z roku 2013. Většinou se nové řády zásadně nemění a jde spíše o drobné úpravy časů, zpravidla jen o několik minut. Tohle bylo potřeba brát na vědomí. Problémem při testování bylo, jak projít všechny možné spoje, navíc v různých časech a ověřit, že se spoje shodují s jízdním řádem dopravců. První myšlenkou bylo nejprve získat nejkratší cesty mezi všemi městy a v různých časech ve vytvořené aplikaci. Potom získat nejkratší cesty pro stejné města, stejné časy z jizdnirady.idnes.cz a dalších dopravců, protože aplikace zahrnuje všechny dopravce na trhu. Ve finále tyto data porovnat a hledat odchylky. Bohužel by to bylo technicky náročné, navíc by byl pořád problém s novým jízdním řádem oproti starému. Proto byly testovány jen určité spoje. Především komplikované spoje, kde


39

je hodně přestupů nebo vlaky jezdí přes půlnoc. Pro ukázku jsem vybral spoj mezi Libercem a Ostravou, který jede přes půlnoc. První výstup je z vytvořené aplikace pomocí algoritmu A*, druhý výstup (Obr. 4) jsou data z jizdnirady.idnes.cz. --A*-Liberec R 997 - arrival: 20:02:00 - departure: 20:02:00 Rychnov u Jabl.n.Nisou R 997 - arrival: 20:19:00 - departure: 20:20:00 Turnov R 997 - arrival: 20:39:00 - departure: 20:42:00 Malá Skála R 997 - arrival: 20:50:00 - departure: 20:51:00 Železný Brod R 997 - arrival: 20:58:00 - departure: 21:00:00 Semily R 997 - arrival: 21:07:00 - departure: 21:08:00 Stará Paka R 997 - arrival: 21:25:00 - departure: 21:27:00 Dvůr Králové n.Labem R 997 - arrival: 21:56:00 - departure: 22:01:00 Jaroměř zast. R 997 - arrival: 22:11:00 - departure: 22:12:00 Jaroměř R 997 - arrival: 22:15:00 - departure: 22:21:00 Smiřice R 997 - arrival: 22:27:00 - departure: 22:27:00 Hradec Králové hl.n. R 997 - arrival: 22:37:00 - departure: 22:40:00 Opatovice n.Labem R 997 - arrival: 22:45:00 - departure: 22:46:00 Čeperka R 997 - arrival: 22:50:00 - departure: 22:50:00 Pardubice-Rosice n.L. R 997 - arrival: 23:03:00 - departure: 23:03:00 Pardubice hl.n. R 997 - arrival: 23:07:00 - departure: 23:07:00 Pardubice hl.n. R 443 - arrival: 23:35:00 - departure: 23:38:00 Česká Třebová R 443 - arrival: 00:17:00 - departure: 00:19:00 Zábřeh na Moravě R 443 - arrival: 00:43:00 - departure: 00:45:00 Olomouc hl.n. R 443 - arrival: 01:10:00 - departure: 01:13:00 Ostrava-Svinov R 443 - arrival: 02:08:00 - departure: 02:11:00 Ostrava hl.n. R 443 - arrival: 02:18:00 - departure: 02:20:00

Obr. 5

Hledaný spoj z jizdnirady.idnes.cz

Z porovnání je patrné, že se cesty shodují, jen časy se mírně liší z důvodu nového jízdního řádu. Všechny testované spoje se nakonec shodovali s jízdními řády dopravců. Po otestování nejkratší cesty bylo nezbytné zjistit, jak rychle algoritmy pracují. Pro testování byly vybrány náhodně spoje napříč republikou. Každý spoj byl testován několikrát a výsledkem byla průměrná hodnota z naměřených hodnot. Pro testování byla použit notebook s procesorem Intel® Core™2 Duo T6600 2.20 GHz a 4GB operační paměti. Na výsledný čas mají vliv dva faktory. První je počet vazeb RELATED, jedná se o trasu vlaku a tyto vazby se nedají ovlivnit. Druhým faktorem je počet vazeb CHANGE, jde o přestupy na jiné vlaky. Tenhle faktor už se ovlivnit dá a to docela zásadním způsobem. Čím více takových vazeb je, tím více je expander vytěžován a proto je potřeba vytvořit přestupy, které opravdu mají smysl. Proto při vytváření

40


databáze byly povoleny přestupy, které zabraly maximálně sto minut. Je potřeba vyloučit i vlaky, na které nemá smysl přestoupit. Jedná se o situace, kdy vlak jede stejnou trasu, ale třeba jen o hodinu později. I přes provedení těchto opatření nejsou přestupy podchyceny úplně optimálně a určitě by se daly do budoucna ještě vylepšit. Tab. 4

Srovnání výsledků Dijkstrova algoritmu

Počáteční stanice Tachov Uherský Brod Břeclav Příbor Praha hl.n. Tab. 5

Cílová stanice Ostrava hl. n. Aš Hlubočky Praha hl.n. Příbor

Vzdálenost v km 545 589 133 347 347

Dijkstrův algoritmus (sekundy) I10,85 17,20 5,61 5,126 16,63

Srovnání výsledků A* algoritmu

Počáteční stanice Tachov Uherský Brod Břeclav Příbor Praha hl.n.

Cílová stanice Ostrava hl. n. Aš Hlubočky Praha hl.n. Příbor

Vzdálenost v km

A* estimate80 (sekundy)

A* estimate50 (sekundy)

545

I2,7

2,27

589 133 347 347

14,93 3,974 1,188 5,938

10,47 3,12 1 3,68

Z výše uvedené tabulky je jasně patrné, že A* byl vždy rychlejší než Dijkstrův algoritmus, což jen potvrzuje teorii. V průměru A* (estimate50) najde spoj zhruba za 4 sekundy, kdežto Dijkstrův algoritmus za 11 sekund. V některých případech byl A* skoro pětkrát rychlejší. A* je v tabulce zachycen dvakrát. Jedná se o testování, kdy jednou bylo pro estimate evaluator stanoveno, že jedna hodina se rovná padesáti kilometrům. Podruhé se jedna hodina rovnala osmdesáti kilometrům. Jak je patrné ze srovnání (Tab. 5), estimate50 byl vždy rychlejší. Z toho je zřejmé, že je potřeba vždy vhodně nastavit estimate evaluator. Zkoušel jsem zvolit pro výpočet i jiný poměr kilometrů ku hodinám, ale už se mi výsledek nepovedlo nějak zásadně vylepšit. Z tabulky lze i vidět, že při prohození počáteční stanice s cílovou, je spoj vyhledán v jiném časovém intervalu. Konkrétně to v tabulce zachycuje čtvrtý a pátý řádek, spoj Příbor – Praha hl.n. a naopak. Je to zapříčiněno tím, že pokud vyjíždí vlak z Příboru, nemá tolik možností, jak expander v počáteční stanici zatížit, jako když vyjíždí z Prahy.

Diskuze

41

5 Diskuze I když byla databáze úspěšně navržena a vytvořena, jednalo se pouze o převod relační databáze na grafovou s drobnými změnami, bez porušení logiky dodané relační databáze. Tím tu vzniká prostor pro vylepšení návrhu už samotné relační databáze, což by se projevilo i v grafové. Především by se dala určitě lépe navrhnout tabulka calendar_dates, aby se zabránilo zbytečné redundanci. Grafové algoritmy pracovali správně a jediné možné vylepšení, co se týče časové náročnosti, je opět u návrhu databáze. Prvotní schéma vypadalo tak, že v každé zastávce by byly dva uzly StopTimes, namísto jednoho, jako tomu je ve finálním návrhu. První uzel by reprezentoval příjezd vlaku a druhý uzel odjezd vlaku ze stanice. Původně mi tento návrh přišel zbytečně redundantní a proto jsem ho zavrhl, ale později jsem zjistil, že by měl svou výhodu v tom, že by se daly ohodnotit hrany atributem s časem jízdy přímo a tudíž by cost evaluator nemusel hodnoty vypočítávat, ale jen by je získal z databáze. Ve finálním návrhu není možné ohodnotit hrany z toho důvodu, že hodnota hrany závisí na tom, jestli ze stanice vyjíždíme nebo jí pouze projíždíme, což by se vyřešilo vznikem dvou uzlů. V praxi by se mohla aplikace nasadit na výkonnější server, tím by se vyhledávání vlakových spojů dalo taky urychlit. V závěrečném testování bohužel nebylo z časových důvodů firmy možné porovnat aplikace. Avšak si myslím, že využití grafové databáze v tomhle případě, bude vždy efektivnější, než relační databáze, bez ohledu na to, jaký je použit prohledávací algoritmus.

42

Závěr

6 Závěr Cílem bakalářské práce bylo navrhnout alternativní vlakový vyhledávač k již vytvořenému vyhledávači, konkrétně se jednalo o projekt kj.cz. Cíl práce byl ve všech bodech splněn. Na základě zpracované teorie byla vybrána vhodná databáze a to konkrétně grafová, po té byla navržena a naplněna daty. Grafová databáze byla zrealizována v Neo4j. Při návrhu databáze byl kladen důraz jak na velikost databáze, tak na vhodné schéma pro grafové algoritmy. Byl vysvětlen i postup a zásady, při převodu relační databáze na grafovou. Při importu dat byly otestovány oba způsoby, jak REST API, tak embedded mode. Další kapitola byla věnována grafovým algoritmům. Výběr grafového algoritmu vycházel z asymptotické složitosti. Proto byl vybrán Dijkstrův algoritmus a jeho vylepšení A*. I když už jsou v Neo4j tyto algoritmy naimplementovány, bylo potřeba vytvořit expander, cost evaluator a pro A* ještě estimate evaluator. Samotná aplikace byla zhotovena v programovacím jazyce JAVA a na závěr proběhlo testování ve dvou fázích. V první fázi byly testovány nejkratší spoje, respektive jestli je cesta opravdu nejkratší. V druhé fázi se testovala rychlost algoritmů. V praxi byl rychlejší A* algoritmus před Dijkstrovým, což jen potvrdilo teoretické poznatky.

Literatura

43

7 Literatura EVEN, SHIMON. Graph algorithms. 2. vyd. Cambridge, NY: Cambridge University Press, 2012, xii, 189 p. ISBN 978-052-1736-534. GARCIA-MOLINA, HECTOR, JEFFREY D. ULLMAN A JENNIFER WIDOM. Database systems: the complete book. 2. vyd. Upper Saddle River, N.J.: Pearson Prentice Hall, c2009, xxxvi, 1203 p. ISBN 01-318-7325-3. MAHATA, DEBANJAN. An Introduction to NOSQL, Graph Databases and Neo4j. SlideShare [online]. 2014 [cit. 2014-04-02]. Dostupné z: http://www.slideshare.net/debanjanmahata/an-introduction-to-nosqlgraph-databases-and-neo4j MIČKA, PAVEL. Bellman-Fordův algoritmus. Algoritmus - Algoritmy.net [online]. © 2008-2014 [cit. 2014-05-10]. Dostupné z: http://www.algoritmy.net/article/7478/Bellman-Forduv-algoritmus MULHOLLAND, ARAN. Neo4j: Step by Step to create an automatic index. In: Stack Overflow [online]. 2012 [cit. 2014-05-09]. Dostupné z: http://stackoverflow.com/questions/12877678/neo4j-step-by-step-tocreate-an-automatic-index NEO TECHNOLOGY. Download and Install Neo4j. Neo4j [online]. 2014a [cit. 201404-09]. Dostupné z: http://www.neo4j.org/download NEO TECHNOLOGY. Create. Neo4j documentation [online]. 2014b [cit. 2014-05-15]. Dostupné z: http://docs.neo4j.org/chunked/stable/query-create.html NEO TECHNOLOGY. Hello World. Neo4j documentation [online]. 2014c [cit. 201404-09]. Dostupné z: http://docs.neo4j.org/chunked/stable/tutorials-javaembedded-hello-world.html NEO TECHNOLOGY. Indexes. Neo4j documentation [online]. 2014d [cit. 2014-0407]. Dostupné z: http://docs.neo4j.org/chunked/stable/query-schemaindex.html NEO TECHNOLOGY. Lables. Neo4j documentation [online]. 2014e [cit. 2014-04-07]. Dostupné z: http://docs.neo4j.org/chunked/stable/graphdb-neo4jlabels.html NEO TECHNOLOGY. Match. Neo4j documentation [online]. 2014f [cit. 2014-04-02]. Dostupné z: http://docs.neo4j.org/chunked/stable/query-match.html NEO TECHNOLOGY. Merge. Neo4j documentation [online]. 2014g [cit. 2014-04-05]. Dostupné z: http://docs.neo4j.org/chunked/stable/query-merge.html NEO TECHNOLOGY. Service root. Neo4j documentation [online]. 2014h [cit. 201404-08]. Dostupné z: http://docs.neo4j.org/chunked/stable/rest-api-serviceroot.html NEO TECHNOLOGY. Upgrading. Neo4j documentation [online]. 2014i [cit. 2014-0407]. Dostupné z: http://docs.neo4j.org/chunked/stable/deploymentupgrading.html

44

Literatura

NEO TECHNOLOGY. Values. Neo4j documentation [online]. 2014j [cit. 2014-04-06]. Dostupné z: http://docs.neo4j.org/chunked/stable/cypher-values.html NEO TECHNOLOGY. Where. Neo4j documentation [online]. 2014k [cit. 2014-04-05]. Dostupné z: http://docs.neo4j.org/chunked/stable/query-where.html REDMOND, ERIC, JIM R. WILSON A JACQUELYN CARTER. Seven databases in seven weeks: a guide to modern databases and the NoSQL movement. Dallas, Tex.: Pragmatic Bookshelf, 2012, xiii, 333 p. Pragmatic programmers. ISBN 19-3435692-1. ROBINSON, IAN, JIM WEBBER A EMIL EIFREM. Graph databases. 1. vyd. Sebastopol: O'Reilly Media, 2013. ISBN 978-144-9356-262. SKIENA, STEVEN S. The algorithm design manual: a beginner's guide. 2. vyd. London: Springer, c2008, xvi, 730 s. ISBN 978-1-84800-069-8. WIKIPEDIA. Dijkstra's algorithm. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2014a [cit. 2014-05-10]. Dostupné z: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm WIKIPEDIA. Floyd–Warshall algorithm. Wikipedia, the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2014b [cit. 2014-03-29]. Dostupné z: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Přílohy

45

Přílohy

46

A Program Zdrojový kód programu je přiložen na CD.

Program

Využití grafové databáze pro hledání vlakových spojů

Recommend Documents