Graphs as sparse matrices in Python

csgraph treats a sparse adjacency matrix as a graph.

import numpy as np
from scipy import sparse
from scipy.sparse import csgraph

edges = np.array([
    [0, 2, 0, 0],
    [2, 0, 3, 0],
    [0, 3, 0, 0],
    [0, 0, 0, 0],
])
graph = sparse.csr_array(edges)

count, labels = csgraph.connected_components(graph, directed=False)
print(count, labels)

distances = csgraph.dijkstra(graph, directed=False, indices=0)
print(distances)
print(csgraph.minimum_spanning_tree(graph).toarray().astype(int))

How it works

connected_components labels each node's component.
dijkstra gives shortest paths from a source.
minimum_spanning_tree returns another sparse matrix.

Keywords and builtins used here

as
int
print

The run, in numbers

Lines: 18
Characters to type: 424
Tokens: 129
Three-star pace: 110 tpm

At the three-star pace of 110 tokens a minute, this run takes about 70 seconds.

Type this snippet

Step 2 of 4 in Sparse & spatial, step 20 of 23 in Scientific computing with SciPy.

← Previous Next →