In [2]:
heawood = nx.heawood_graph()
nx.draw(heawood)
Na tomto cvičení si osaháme základní manipulaci s grafy a sítěmi. Budeme používat balík networkx pro Python.
import networkx as nx
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.
G = nx.Graph()
Objekt Graph podporuje základní operace jako přidávání vrcholu
G.add_node(1)
přidávání seznamu vrcholů
G.add_nodes_from([2,3])
G.add_nodes_from(range(4, 10))
Vypsat seznam všech vrcholů můžeme pomocí
G.nodes()
NodeView((1, 2, 4, 5, 6, 7, 8, 9, 3))
Přidávat můžeme samozřejmě i hrany a to opět jednotlivě
G.add_edge(1,2)
nebo pomocí seznamu
G.add_edges_from([(1,3), (2,3), (3,4), (4,5)])
G.edges()
EdgeView([(1, 2), (1, 3), (2, 3), (4, 5), (4, 3)])
Podobně můžeme také odebírat vrcholy
G.remove_node(3)
print("Nodes: {}, Edges: {}".format(G.nodes(), G.edges()))
Nodes: [1, 2, 4, 5, 6, 7, 8, 9], Edges: [(1, 2), (4, 5)]
a hrany
G.remove_edge(4,5)
print("Nodes: {}, Edges: {}".format(G.nodes(), G.edges()))
Nodes: [1, 2, 4, 5, 6, 7, 8, 9], Edges: [(1, 2)]
Užitečné může být i aktualizovat graf pomocí zadaného seznamu hran a vrcholů.
G.update([(1,3), (2,3)], [3, 10])
print("Nodes: {}, Edges: {}".format(G.nodes(), G.edges()))
Nodes: [1, 2, 4, 5, 6, 7, 8, 9, 3, 10], Edges: [(1, 2), (1, 3), (2, 3)]
Následující funkce vrátí všechny sousedy zadaného vrcholu
G.neighbors(3)
for n in G.neighbors(3):
print(n)
1 2
Pokud však chceme projít sousedy postupně všech vrcholů, existují i sofistikovanější funkce G.adjacency() a G.adj, viz dokumentace.
G.adj
AdjacencyView({1: {2: {}, 3: {}}, 2: {1: {}, 3: {}}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {}, 9: {}, 3: {1: {}, 2: {}}, 10: {}})
G.adjacency()
<dict_itemiterator at 0x7fd519b70360>
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.
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.
p5 = nx.path_graph(5)
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ů.
Předávání grafů pomocí seznamu hran je poměrně běžné. Jak vygenerujeme seznam hran jsme si již ukázali výše.
Dostáváme se konečně k prvnímu "skutečnému" formátu. Podívejte se, jak vypadá.
nx.write_gml(p5, 'example.gml')
example_file = open('example.gml', 'r')
print(example_file.read())
graph [
node [
id 0
label "0"
]
node [
id 1
label "1"
]
node [
id 2
label "2"
]
node [
id 3
label "3"
]
node [
id 4
label "4"
]
edge [
source 0
target 1
]
edge [
source 1
target 2
]
edge [
source 2
target 3
]
edge [
source 3
target 4
]
]
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
Pozor, nezaměňovat s předchozím formátem. Jedná se o speciální verzi formátu xml.
nx.write_graphml(p5, 'example.xml')
example_file = open('example.xml', 'r')
print(example_file.read())
<?xml version='1.0' encoding='utf-8'?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"><graph edgedefault="undirected"><node id="0"/> <node id="1"/> <node id="2"/> <node id="3"/> <node id="4"/> <edge source="0" target="1"/> <edge source="1" target="2"/> <edge source="2" target="3"/> <edge source="3" target="4"/> </graph></graphml>
Další podrobnosti k tomuto formátu jsou na https://networkx.org/documentation/stable/reference/readwrite/graphml.html
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
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
nx.write_graph6(p5, 'example.g6')
example_file = open('example.g6', 'r')
print(example_file.read())
>>graph6<<DhC
nx.write_sparse6(p5, 'example.s6')
example_file = open('example.s6', 'r')
print(example_file.read())
>>sparse6<<:DaYn
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
nx.write_pajek(p5, 'example.paj')
example_file = open('example.paj', 'r')
print(example_file.read())
*vertices 5 1 0 0.0 0.0 ellipse 2 1 0.0 0.0 ellipse 3 2 0.0 0.0 ellipse 4 3 0.0 0.0 ellipse 5 4 0.0 0.0 ellipse *edges 1 2 1.0 2 3 1.0 3 4 1.0 4 5 1.0
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.
football = nx.read_pajek('football.paj')
undir_football = nx.Graph(football)
nx.write_graph6(undir_football, 'football.g6')
example_file = open('football.g6', 'r')
print(example_file.read())
>>graph6<<b??CAAG[O?zNYSOA?GA?i?CBj~O?A?Q???A@?D`????Cao_GFP@?DX?BG?A?OG?OGDW?_?J?@??c?_?aO_GOAp?E??DpO?AGmGKA?
nx.write_sparse6(undir_football, 'football.s6')
example_file = open('football.s6', 'r')
print(example_file.read())
>>sparse6<<:bb?GK?H@@?o{e?@@`?w_QI____[R@DPwGcULco?GGGEBa@GgUKEbxkONKHqPWobV@@PGkWP`APOkYPJqPWs[P``?xUGJJO`GkYMKQ`_srHEDWW[SNJfGo_QLJeHGkWLGcwGSQJEBQH[o^
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.
import matplotlib.pyplot as plt
heawood = nx.heawood_graph()
nx.draw(heawood)
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.
circ = nx.circular_layout(heawood)
nx.draw(heawood, circ)
Nejčastější layouty jsou podporované přímo variantami funkce draw.
nx.draw_circular(heawood)
spir = nx.spiral_layout(heawood)
nx.draw(heawood, spir)
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 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.
nx.drawing.nx_agraph.write_dot(heawood, 'heawood.dot')
example_file = open('heawood.dot', 'r')
print(example_file.read())
strict graph "Heawood Graph" {
graph [name="Heawood Graph"];
0 -- 1;
0 -- 5;
0 -- 13;
1 -- 2;
1 -- 10;
2 -- 3;
2 -- 7;
3 -- 4;
3 -- 12;
4 -- 5;
4 -- 9;
5 -- 6;
6 -- 7;
6 -- 11;
7 -- 8;
8 -- 9;
8 -- 13;
9 -- 10;
10 -- 11;
11 -- 12;
12 -- 13;
}
Z vygenerovaného souboru si pak můžeme nechat vygenerovat obrázek pomocí programu dot následovně: dot -Tjpg heawood.dot > heawood.jpg
nx.drawing.nx_agraph.write_dot(football, 'football.dot')
example_file = open('football.dot', 'r')
print(example_file.read())
digraph "" {
ARG [id=1,
shape=0.5,
x=0.3784,
y=0.7257];
ESP [id=12,
shape=0.5,
x=0.558,
y=0.5982];
ARG -> ESP [key=0,
weight=4.0];
ITA [id=18,
shape=0.5,
x=0.4556,
y=0.6498];
ARG -> ITA [key=0,
weight=9.0];
AUT [id=2,
shape=0.5,
x=0.707,
y=0.3091];
DEU [id=10,
shape=0.5,
x=0.6178,
y=0.2022];
AUT -> DEU [key=0,
weight=7.0];
AUT -> ESP [key=0,
weight=1.0];
FRA [id=13,
shape=0.5,
x=0.6993,
y=0.2113];
AUT -> FRA [key=0,
weight=1.0];
GBR [id=14,
shape=0.5,
x=0.8284,
y=0.4099];
AUT -> GBR [key=0,
weight=1.0];
AUT -> ITA [key=0,
weight=1.0];
BEL [id=3,
shape=0.5,
x=0.3112,
y=0.3627];
BEL -> DEU [key=0,
weight=2.0];
BEL -> FRA [key=0,
weight=2.0];
BEL -> ITA [key=0,
weight=2.0];
NLD [id=25,
shape=0.5,
x=0.6541,
y=0.5668];
BEL -> NLD [key=0,
weight=2.0];
BGR [id=4,
shape=0.5,
x=0.4901,
y=0.2231];
BGR -> DEU [key=0,
weight=4.0];
BGR -> ESP [key=0,
weight=1.0];
PRT [id=27,
shape=0.5,
x=0.1998,
y=0.4088];
BGR -> PRT [key=0,
weight=1.0];
TUR [id=32,
shape=0.5,
x=0.5347,
y=0.3531];
BGR -> TUR [key=0,
weight=4.0];
BRA [id=5,
shape=0.5,
x=0.4183,
y=0.8734];
BRA -> ESP [key=0,
weight=4.0];
BRA -> FRA [key=0,
weight=1.0];
BRA -> ITA [key=0,
weight=5.0];
JPN [id=20,
shape=0.5,
x=0.7505,
y=0.9353];
BRA -> JPN [key=0,
weight=1.0];
BRA -> PRT [key=0,
weight=1.0];
CHE [id=6,
shape=0.5,
x=0.8277,
y=0.771];
CHL [id=7,
shape=0.5,
x=0.057,
y=0.466];
CHL -> ARG [key=0,
weight=1.0];
CHL -> ITA [key=0,
weight=1.0];
USA [id=33,
shape=0.5,
x=0.3644,
y=0.183];
CHL -> USA [key=0,
weight=1.0];
CMR [id=8,
shape=0.5,
x=0.6661,
y=0.4183];
CMR -> AUT [key=0,
weight=1.0];
CMR -> DEU [key=0,
weight=1.0];
CMR -> ESP [key=0,
weight=2.0];
CMR -> FRA [key=0,
weight=7.0];
GRE [id=15,
shape=0.5,
x=0.8529,
y=0.5632];
CMR -> GRE [key=0,
weight=1.0];
CMR -> ITA [key=0,
weight=2.0];
CMR -> JPN [key=0,
weight=2.0];
CMR -> PRT [key=0,
weight=2.0];
CMR -> TUR [key=0,
weight=2.0];
COL [id=9,
shape=0.5,
x=0.1708,
y=0.7309];
COL -> ARG [key=0,
weight=3.0];
COL -> BRA [key=0,
weight=2.0];
COL -> ESP [key=0,
weight=1.0];
COL -> ITA [key=0,
weight=1.0];
COL -> USA [key=0,
weight=2.0];
DEU -> ESP [key=0,
weight=1.0];
DEU -> FRA [key=0,
weight=1.0];
DEU -> ITA [key=0,
weight=2.0];
DNK [id=11,
shape=0.5,
x=0.7995,
y=0.3587];
DNK -> DEU [key=0,
weight=3.0];
DNK -> ESP [key=0,
weight=1.0];
DNK -> GBR [key=0,
weight=6.0];
DNK -> ITA [key=0,
weight=1.0];
DNK -> NLD [key=0,
weight=1.0];
SCO [id=30,
shape=0.5,
x=0.943,
y=0.4508];
DNK -> SCO [key=0,
weight=3.0];
DNK -> TUR [key=0,
weight=1.0];
HRV [id=16,
shape=0.5,
x=0.657,
y=0.7437];
HRV -> AUT [key=0,
weight=1.0];
HRV -> DEU [key=0,
weight=2.0];
HRV -> ESP [key=0,
weight=4.0];
HRV -> GBR [key=0,
weight=2.0];
HRV -> ITA [key=0,
weight=4.0];
HRV -> TUR [key=0,
weight=1.0];
IRN [id=17,
shape=0.5,
x=0.6526,
y=0.0804];
IRN -> DEU [key=0,
weight=3.0];
ITA -> ESP [key=0,
weight=2.0];
ITA -> FRA [key=0,
weight=1.0];
ITA -> GBR [key=0,
weight=2.0];
JAM [id=19,
shape=0.5,
x=0.8974,
y=0.5263];
JAM -> GBR [key=0,
weight=7.0];
KOR [id=21,
shape=0.5,
x=0.906,
y=0.8003];
KOR -> FRA [key=0,
weight=1.0];
KOR -> JPN [key=0,
weight=4.0];
MAR [id=22,
shape=0.5,
x=0.4052,
y=0.5224];
MAR -> DEU [key=0,
weight=3.0];
MAR -> ESP [key=0,
weight=4.0];
MAR -> FRA [key=0,
weight=1.0];
MAR -> ITA [key=0,
weight=1.0];
MAR -> PRT [key=0,
weight=3.0];
TUN [id=31,
shape=0.5,
x=0.4882,
y=0.0647];
MAR -> TUN [key=0,
weight=1.0];
MEX [id=23,
shape=0.5,
x=0.5903,
y=0.8579];
NGA [id=24,
shape=0.5,
x=0.4846,
y=0.506];
NGA -> BEL [key=0,
weight=2.0];
NGA -> CHE [key=0,
weight=1.0];
NGA -> DEU [key=0,
weight=1.0];
NGA -> ESP [key=0,
weight=4.0];
NGA -> FRA [key=0,
weight=3.0];
NGA -> ITA [key=0,
weight=2.0];
NGA -> NLD [key=0,
weight=3.0];
NGA -> TUR [key=0,
weight=3.0];
NGA -> USA [key=0,
weight=1.0];
ZAF [id=35,
shape=0.5,
x=0.7861,
y=0.6645];
NGA -> ZAF [key=0,
weight=1.0];
NLD -> DEU [key=0,
weight=1.0];
NLD -> ESP [key=0,
weight=5.0];
NLD -> GBR [key=0,
weight=4.0];
NLD -> ITA [key=0,
weight=2.0];
NOR [id=26,
shape=0.5,
x=0.7761,
y=0.4672];
NOR -> DEU [key=0,
weight=3.0];
NOR -> ESP [key=0,
weight=1.0];
NOR -> GBR [key=0,
weight=12.0];
NOR -> GRE [key=0,
weight=2.0];
NOR -> ITA [key=0,
weight=1.0];
NOR -> SCO [key=0,
weight=3.0];
PRY [id=28,
shape=0.5,
x=0.5335,
y=0.8248];
PRY -> BRA [key=0,
weight=10.0];
PRY -> ESP [key=0,
weight=2.0];
PRY -> MEX [key=0,
weight=1.0];
ROM [id=29,
shape=0.5,
x=0.6593,
y=0.5079];
ROM -> BEL [key=0,
weight=1.0];
ROM -> DEU [key=0,
weight=2.0];
ROM -> ESP [key=0,
weight=6.0];
ROM -> GBR [key=0,
weight=2.0];
ROM -> GRE [key=0,
weight=2.0];
ROM -> NLD [key=0,
weight=1.0];
ROM -> TUR [key=0,
weight=4.0];
SCO -> FRA [key=0,
weight=1.0];
SCO -> GBR [key=0,
weight=7.0];
TUN -> DEU [key=0,
weight=2.0];
TUN -> FRA [key=0,
weight=3.0];
USA -> DEU [key=0,
weight=2.0];
USA -> GBR [key=0,
weight=2.0];
USA -> NLD [key=0,
weight=1.0];
YUG [id=34,
shape=0.5,
x=0.5178,
y=0.772];
YUG -> DEU [key=0,
weight=1.0];
YUG -> ESP [key=0,
weight=9.0];
YUG -> FRA [key=0,
weight=1.0];
YUG -> GBR [key=0,
weight=1.0];
YUG -> ITA [key=0,
weight=7.0];
YUG -> JPN [key=0,
weight=2.0];
ZAF -> AUT [key=0,
weight=1.0];
ZAF -> CHE [key=0,
weight=1.0];
ZAF -> DEU [key=0,
weight=2.0];
ZAF -> ESP [key=0,
weight=2.0];
ZAF -> FRA [key=0,
weight=1.0];
ZAF -> GBR [key=0,
weight=4.0];
ZAF -> ITA [key=0,
weight=1.0];
ZAF -> NLD [key=0,
weight=2.0];
ZAF -> TUR [key=0,
weight=3.0];
}
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/
