Projekt webové grafové služby



Motivace a okolnosti
Australští výzkumníci v oboru kombinatoriky a teorie grafů shromáždili do dnešního dne více než 100 000 000 různých grafů a poskytují je na svých stránkach volně všem uživatelům. Pro odborníky jak z oblasti abstraktní matematiky tak z oblasti praktické výpočetní vědy má tato kolekce nemalý význam, velmi těžko se však s ní manipuluje, což mnohé potenciální zájemce odrazuje od jejího použití. Grafy, tak jak byly vygenerovány, jsou pouze podle počtu vrcholů a hran rozděleny do souborů (ve vtipném, ale obskurním formátu), které obsahují bez jakéhokoli dalšího členění typicky stovky až statisíce grafů. Zájemce, který chce s touto kolekcí pracovat, případně se chce soustředit na určitý druh grafů, tak má k dispozici pouze surová data, k nimž si prakticky všechny SW prostředky musí vytvořit sám. Přitom mnohé základní otázky a požadavky související s takto rozsáhlou kolekcí mají uniformní strukturu: Které grafy mají zároveň vlastnost A, vlastnost B,... vlastnost Z? Existuje takový graf vůbec? Kolik jich je? Chci si je stáhnout v nějakém rozumném formátu. Atd.
Zřejmě by tedy byla vítána každá nadstavba nad uvedenými daty, která by uživatelům možnila o poznání strukturovanější přístup a ušetřila by jim zdlouhavou práci s extrakcí grafů požadovaných vlastností, případně by dovolila porovnávat vlastnosti různých skupin grafů apod. Kolekce je po částech přístupná ze stránek:
http://cs.anu.edu.au/~bdm/data/graphs.html
http://staffhome.ecm.uwa.edu.au/~00013890/data.html.


Služba uživateli
Optimálně by grafová služba v počátcích poskytla uživateli jednoduché rozhraní, v němž by specifikoval požadované vlastnosti grafů a získal by zpět reference na přislušné konkrétní grafy s možností jejich stažení a případně převedení do jiného formátu.

Správa služby
Důležitou okolností při takto rozsáhlých datech je to, že se mohou objevovat nové požadavky na vlastnosti, které by měly být spolu s daty (grafy) registrovány. Například může po čase vzniknout zájem o grafy s velkým průměrem, a přitom průměr grafu nebude ještě v datech registrován. Správce by tedy měl mít možnost
A. Spustit SW, který tuto novou vlastnost u každého grafu určí a kvantifikuje.
B. Zanést zjištěné poznatky do dat.
C. Přidat pro uživatele do rozhraní možnost volby této nové vlastnosti.
Služba by ve své implementaci měla podporovat část B a C, samotnou výrobu SW v bodě A podporovat ovšem nemůže :-). Správce by neměl být grafový odborník.

Otázka izomorfizmu
Přidávání grafů do databáze služby musí předejít duplicitám. Přidávaný graf nesmí být izomorfní (= totožný) s žádným grafem již obsaženým v databázi. Obecně je ale otázka izomorfizmu velmi těžká a nelze ji rozhodnout běžnými databázovými nástroji (někdy ano, ale ne pokaždé). Stávající patrně nejefektivnější nástroj na určování izomorfizmu je volně přístupný http://users.cecs.anu.edu.au/~bdm/nauty/, který by musel být ve službě integrován.

Pilotní projekt
Pilotní projekt -- ať už v rozsahu semestrálního projektu, BP, DP či v jiné formě -- by nejspíše měl prakticky implementovat alespoň částečnou funkčnost navržené služby, možná s omezenou množinou grafů. Záleží na zájmech a orientaci řešitele. Je možno se soustředit na databázové řešení, návrh a implementací rozhraní, návrh mechanizmu umožňujícího rozšiřování služby popsaného výše.

Doména graphs.felk.cvut.cz
Jednoduché funkční rozhraní ilustrující základní možnou variantu je k dispozici na stránce graphs.felk.cvut.cz. Počet indexovaných grafů je ( 06. 2017 ) asi 22 milionů. Další vývoj tohoto rozhraní a jeho služeb je žádoucí.