Algorytmy grafowe

Wprowadzenie do analizy sieci w Pythonie

Eric Ma

Data Carpentry instructor and author of nxviz package

Wyznaczanie ścieżek

Wyznaczanie ścieżek jest istotne dla:
- Optymalizacji: np. najkrótsze trasy transportu
- Modelowania: np. rozprzestrzenianie chorób, przekazywanie informacji
Algorytm: przeszukiwanie wszerz

Graf z kilkunastoma węzłami. Dwa pośrednio połączone węzły są wyróżnione.

Ten sam graf, ale wyróżniony jest również węzeł sąsiadujący z jednym z zaznaczonych węzłów.

Ten sam graf, ale wyróżnione są również węzły sąsiadujące ze wszystkimi zaznaczonymi węzłami.

Ten sam graf, ale kolejny zestaw węzłów sąsiadujących z wyróżnionymi jest również zaznaczony – węzeł docelowy został osiągnięty.

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

len(G.nodes())

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]

Wprowadzenie do analizy sieci w Pythonie