Cvičení 1: Práce s grafy a sítěmi pomocí networkx, formáty, zobrazování

Balík NetworkX

Na tomto cvičení si osaháme základní manipulaci s grafy a sítěmi. Budeme používat balík networkx pro Python.

Než balík začnete používat, je potřeba ho přiinstalovat do vašeho Pythonu, například pomocí pip3 install networkx.

Tento balík poskytuje mnoho důležitých funkcí (a nejen to, předpřipravených je například i mnoho užitečných grafů, třeba Petersenův). Některé funkce si ukážeme v rámci cvičení, zdaleka však ne všechny. Pokud budete cokoli potřebovat, doporučuji hledat v dokumentaci: https://networkx.org/documentation/stable/

V této knihovně budeme používat objekt Graph.

Objekt Graph podporuje základní operace jako přidávání vrcholu

přidávání seznamu vrcholů

Vypsat seznam všech vrcholů můžeme pomocí

Přidávat můžeme samozřejmě i hrany a to opět jednotlivě

nebo pomocí seznamu

Podobně můžeme také odebírat vrcholy

a hrany

Užitečné může být i aktualizovat graf pomocí zadaného seznamu hran a vrcholů.

Následující funkce vrátí všechny sousedy zadaného vrcholu

Pokud však chceme projít sousedy postupně všech vrcholů, existují i sofistikovanější funkce G.adjacency() a G.adj, viz dokumentace.

Kompletní seznam metod spojených s objektem Graph najdete na: https://networkx.org/documentation/stable/reference/classes/graph.html?highlight=graph#networkx.Graph

Úloha 1: Naimplementuj funkci cycle(n), která vrátí kružnici délky n.

Úloha 2: Naimplementuj fukci cartesian(G,H), která pro dva zadané objekty typu Graph vrátí jejich kartézský produkt.

Grafové formáty

S grafy a sítěmi budeme občas potřebovat pracovat v různých programech a jazycích. K tomu se budou hodit různé reprezentace grafů. Ukážeme si některé z nich. Pro jednoduchost si jako příklad vezmeme graf odpovídající cestě na pěti vrcholech.

Matice sousednosti

První možností, jak reprezentovat grafy, je matice sousednosti. Matice sousednosti $A$ je definována jako $A_{ij} = 1$ pro $(i,j) \in E(G)$ a $A_{ij} = 0$ jinak. Vzhledem k prostorové náročnosti se hodí zejména pro reprezentaci grafů s mnoha hranami.

Úloha 3: Naimplementuj funkci adjacency_matrix(G), která pro zadaný graf vrátí matici sousednosti jako seznam řádků.

Seznam hran

Předávání grafů pomocí seznamu hran je poměrně běžné. Jak vygenerujeme seznam hran jsme si již ukázali výše.

GML

Dostáváme se konečně k prvnímu "skutečnému" formátu. Podívejte se, jak vypadá.

Podrobnosti k tomuto formátu, včetně informací, jak graf v takovém formátu načíst, najdete na https://networkx.org/documentation/stable/reference/readwrite/gml.html?highlight=gml#module-networkx.readwrite.gml

GraphML

Pozor, nezaměňovat s předchozím formátem. Jedná se o speciální verzi formátu xml.

Další podrobnosti k tomuto formátu jsou na https://networkx.org/documentation/stable/reference/readwrite/graphml.html

JSON

Je univerzální formát, který je velmi jednoduše generovaný a čtený Pythonem. Můžeme v něm exportovat například výše zmíněný seznam hran či matici sousednosti. Existují programy, které používají více specifikovaný JSON jako jeden z nativních způsobů ukládání grafů, např. Cytoscape, o kterém si povíme později. Více informací o tom, jak generovat a načítat grafy ve formátu JSON najdete zde: https://networkx.org/documentation/stable/reference/readwrite/json_graph.html

SparseGraph6

Tento formát je určený ke kompaktnímu ukládání neorientovaných grafů pomocí ASCII znaků. Na rozdíl od předchozích formátů není lidsky čitelný. Hlavní výhodou je prostorová úspornost tohoto formátu. Pěkným příkladem využití tohoto formátu jsou předgenerované seznamy všech neisomorfních neorientovaných grafů, které jsou k nalezení na stránkách profesora Brendana McKaye: https://users.cecs.anu.edu.au/~bdm/data/graphs.html

Tento formát má dvě varianty, Graph6 pro malé nebo velmi husté grafy (tj. s řádově kvadratickým počtem hran), a Sparse6 pro velké a řídké grafy (tj. s řádově spíše lineárním počtem hran). Více informací a možností importu a exportu najdete opět v dokumentaci k NetworkX: https://networkx.org/documentation/stable/reference/readwrite/sparsegraph6.html

Pajek

Toto je další z mnoha formátů pro ukládání grafů. Jeho specifikace je zde: http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/draweps.htm

Další formáty podporované balíkem NetworkX najdete na této stráce: https://networkx.org/documentation/stable/reference/readwrite/index.html

Úloha 4: Načti graf z http://vlado.fmf.uni-lj.si/pub/networks/data/sport/football.htm a vyexportuj ho do několika různých formátů.

U formátů Sparse6 a Graph6 narazíme na to, že jsou definované pouze pro neorientované grafy. Stažená síť je však orientovaná. Převod z orientovaného grafu na neorientovaný (zapomenutím orientace hran), je možné uskutečnit pomocí funkce G.to_undirected(), ale v tomto případě dostaneme neorientovaný multigraf. Na převod však můžeme využít následující jednoduchý trik.

Zobrazování grafů

Grafy a sítě, se kterými budeme pracovat, si vzhledem k jejich velikosti budeme často potřebovat nějakým způsobem zobrazit. Většinou se navíc bude velmi hodit zobrazení, které nám pomůže nahlédnout a pochopit hlavní struktury dané sítě.

Základní zobrazování a nastavování umí samotný balík NetworkX. Přesněji, pomocí NetworkX vygenerujeme množinu souřadnic, které pak můžeme zobrazit jiným programem/balíkem, například matplotlib. Opět je potřeba balík nejdříve nainstalovat, třeba pomocí pip install matplotlib.

Mezi hlavní možnosti nastavení patří tzv. layouty. Zjednodušeně řečeno si můžeme zvolit, do jaké formace budou uspořádané vrcholy zobrazovaného grafu. (Ne)vhodné kombinace některých layoutů pro konkrétní grafy si ukážeme na příkladu níže.

Nejčastější layouty jsou podporované přímo variantami funkce draw.

Další layouty a možnosti ohledně vykreslování grafů přímo pomocí NetworkX jsou opět popsané v dokumentaci: https://networkx.org/documentation/stable/reference/drawing.html#

Úloha 5: Zkus najít vhodný layout pro zobrazení sítě stažené v rámci předchozí úlohy.

Balík NetworkX je primárně určený k výpočetní analýze sítí. Vhodné vykreslování grafů je složitý problém a proto je často nejlepší využít k němu speicializovaný software.

GraphViz

GraphViz je soubor několika programů k vykreslování grafů a sítí. Automaticky umí nalézt poměrně vhodná nakreslení různých struktur a navíc je velmi dobře konfigurovatelný. Tato sada programů, zejména program Dot, se může hodit nejen při analýze sítí, ale například i ve chvíli, kdy si v programu udržujete nějakou složitější datovou strukturu a chcete se přesvědčit, že jsou ukazatele všude nastavené správně. Více informací k programu Dot najdete v dokumentaci: https://www.graphviz.org/pdf/dotguide.pdf

GraphViz je opět potřeba nainstalovat, například pomocí pip install pygraphviz.

Z vygenerovaného souboru si pak můžeme nechat vygenerovat obrázek pomocí programu dot následovně: dot -Tjpg heawood.dot > heawood.jpg

heawood.jpg

football.jpg

Cytoscape

Tento software je speciálně určený pro analýzu komplexních sítí. Kromě možnosti vypočítání několika parametrů sítí, o kterých se dozvíte v průběhu přednášek, se tento program dá využít i k zobrazování sítí. Jednou z jeho výhod je to, že na rozdíl od ostatních nástrojů je možné si s otevřenou sítí trochu pohrát a vykreslení měnit nejen změnami parametrů, ale i ručním posouváním jednotlivých vrcholů. Pro analýzu malých sítí a grafů se tato vlastnost může hodit.

Více informací a možnost stažení je na https://cytoscape.org/

football-tree.png

football-tree-orthogonal.png

football.xml.png

football-radial.png

football-hierarchic.png