Grafalgoritmer

Introduktion till nätverksanalys i Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Hitta vägar

Vägfinnande är viktigt för
- Optimering: t.ex. kortaste transportvägar
- Modellering: t.ex. sjukdomsspridning, informationsflöde
Algoritm: Bredden-först-sökning

En graf med ett dussintal noder. Två noder som är indirekt förbundna är markerade.

Samma graf som tidigare, men grannoden till en av de markerade noderna är också markerad.

Samma graf som tidigare, men grannoderna till alla markerade noder är också markerade.

Samma graf som tidigare, men ytterligare grannoder till de redan markerade noderna är nu markerade, vilket innebär att målnoden har nåtts.

<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]

Introduktion till nätverksanalys i Python