Projekt webové grafové služby (wgs)



Rozšiřování webové grafové služby (2018)

V hlavních obrysech je aktuální služba, v pilotní podobě popsané v dolní části této stránky, funkční a v provozu s 12293475 grafy v databázi k 17. 5. 2018 na adrese graphs.felk.cvut.cz a s vyřešenou otázkou izomorfizmu, tj. se zamezením jakýmkoli duplicitám.
Autoři:
Sergej Kurbanov (kurbaser@fel.cvut.cz)
Tomáš Roun (rountoma@fel.cvut.c)
Herbert Ullrich (http://bertik.net/)

Zájemci o spolupráci, projekt apod., mohou kontaktovat vedoucího práce RNDr. Berezovského berezovs@fel.cvut.cz .

Další možné směry vývoje wgs jsou naznačeny v následujících několika bodech.

1. Vlastnosti, algoritmy a implementace
V projektu zatím byly využity/vyzkoušeny balíky SageMath, Mathematica, NetworkX. Tyto i další balíky typicky pokrývají svými algoritmy pouze část známých vlastností grafů. Pro mnohé specifické vlastnosti je zapotřebí vyhledat specifický SW, který je rozptýlený po publikacích a webu, rozhodnout o jeho integrovatelnosti do wgs, otestovat jeho chování (k tomu se dobře hodí právě sama wgs) a poté ho případně integrovat do wgs. Těžiště této činnosti je ve volbě a především v ověření jednotlivých specifických implementací, sama integrace do wgs je již automatizována. Viz také Appendix B.

2. HW/SW podpora výpočtů a úložiště
Výpočet vlastností skupin grafů lze efektivně rozdělit do nezávislých paralelních procesů. Je žádoucí, nakolik to bude možné, využít služeb superpočítačů v (alespoň) ČR, www.it4i.cz, www.metacentrum.cz. Stejně tak bude rostoucí objem dat klást rostoucí nároky na databázový stroj, bude vhodné určit alespoň přibližné výkonnostní limity pro dostupné HW/OS konfigurace a podle možností je využívat.

3. On-demand plnění databáze
Pokud je odpověď na dotaz uživatele prázdná, nebo pokud je zřejmé, že hledané grafy obecně existují, ale nejsou v databázi, systém by měl zareagovat tak, že s pomocí integrovaného generátoru grafů hledané grafy vygeneruje a uživateli podá zprávu/výsledek. Podle velikosti úlohy by pak bylo možno volit instantní nebo opožděnou reakci. Při anylýze dotazu by se výhledově uplatnily i nástroje zmíněné v odstavci Teoretické vztahy a výsledky.

4. Integrace generátorů významných tříd grafů
Pokud bude mít wgs k dispozici výkonný HW, lze uvažovat o průběžném rozšiřování globálního korpusu těchto tříd grafů, tj. o konstrukci dosud nenalezených grafů s určitými předpovězenými vlastnostmi. Generátory jsou dostupné buď v tradičních instalacích (http://pallini.di.uniroma1.it/) nebo v separátních rozptýlených programech jednotlivých autorů nebo v grafových SW knihovnách. I bez výkonného HW by bylo pohodlné, kdyby wgs alespoň částečně poskytovala rychlý centralizovaný přístup k těmto generátorům.

5. Teoretické vztahy a výsledky
Lze uvažovat o zařízení pro alespoň částečně automatizované testování hypotéz teorie grafů a/nebo otevřených otázek teorie grafů. Aktuálně dokáže wgs analyzovat uživatelský dotaz a v některých případech potvrdit teoretickou kompletnost nalezené množiny grafů nebo přímo bez komunikace s databází určit, že dotaz musí mít prázdnou množinu odpovědí. Teoretické vztahy mezi jednotlivými vlastnostmi jsou někdy známy, mnohdy ne, leckteré patří mezi otevřené problémy teorie grafů. Dá se čekat, že rozsáhlý korpus grafů s navázanými výpočty může přispět výzkumníkům k lepší orientaci v této oblasti.

6. Uživatelské rozhraní
Rozšířené možnosti wgs bude vhodné reflektovat v UI, bezprostřední náměty viz Appendix A.

7. Náměty dalších a doplňkových souvisejících projektů
- Robotické prohledávání webu s detekcí grafových diagramů, integrace nalezených diagramů do databáze.
- Delegování různých výpočtů na stranu návtěvníkova stroje během jeho návštěvy wgs, inspirace: http://treedecompositions.com/#/twathomebatch. Též lze podle vyzkoušených modelů distribuovaných projektů typu xyz@home vyzkoušet spuštění projektu graphs@home.
- Knihovnická práce: Tvorba a udržování informační přehledové stránky na Wikipedii nebo rovnou ve wgs s odkazy na další online grafové služby a korpusy s případným jejich porovnáním a možnostmi, které poskytují.


Appendix A
Možná bezprostřední rozšíření UI: Podpora většiny rozšířených grafových datových formátů, Sparse6, GraphML, DXL, LEDA apod, uživatelské I/O v těchto formátech. Zobrazování grafů resp. ukládání a registrace "pěkných" diagramů grafů. Integrace některého z hotových grafových editorů (nejspíše v online variantě) do wgs.

Appendix B
Neúplný seznam zatím neregistrovaných grafových vlastností ve wgs: https://gitlab.fel.cvut.cz/graphs/Links_and_sources/blob/master/graph_properties.txt.



Původní návrh wgs (2016)
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í.