SciPy Graphs

Representing a Network as a Sparse Matrix

Many real-world systems are naturally graphs: road networks connecting cities, computer networks connecting servers, or social networks connecting people. SciPy models these as adjacency matrices, where entry (i, j) holds the weight of the edge between node i and node j, and a value of zero means no direct connection exists. Because most large networks are sparse - each node only connects to a handful of others out of thousands - SciPy stores the graph using scipy.sparse.csr_matrix, which only keeps track of the non-zero entries instead of wasting memory on every possible pair of nodes.

import numpy as np
from scipy.sparse import csr_matrix

# Rows/columns represent 4 cities: 0=Delhi, 1=Mumbai, 2=Bangalore, 3=Chennai
# A value of 0 means there is no direct road between two cities
distances = np.array([
    [0, 3, 0, 12],
    [3, 0, 4, 0],
    [0, 4, 0, 2],
    [12, 0, 2, 0],
])

graph = csr_matrix(distances)
print(graph)

Finding Shortest Paths with Dijkstra's Algorithm

scipy.sparse.csgraph.dijkstra computes the shortest total distance from one or more starting nodes to every other node in the graph, similar to how a navigation app finds the quickest route between cities. It requires all edge weights to be non-negative - for graphs that might include negative weights, use bellman_ford instead. Setting return_predecessors=True additionally returns, for every node, the previous node visited along its shortest path, which lets you reconstruct the full route rather than just its total length.

from scipy.sparse.csgraph import dijkstra

dist_matrix, predecessors = dijkstra(
    csgraph=graph,
    directed=False,
    indices=0,
    return_predecessors=True
)

print(dist_matrix)     # shortest travel distance from Delhi to every other city
print(predecessors)    # the city visited just before reaching each destination

• csgraph - the sparse adjacency matrix describing the network
• directed - set to False to treat every edge as usable in both directions
• indices - restrict the calculation to one or more specific starting nodes instead of computing from every node
• return_predecessors - also return the node visited just before each destination, so you can trace back the actual path taken

Grouping Nodes into Connected Components

Not every graph is fully connected - sometimes a network splits into separate clusters that have no path between them. connected_components scans the graph and assigns every node a label identifying which cluster it belongs to, and also reports how many distinct clusters exist. This is useful for spotting isolated machines on a network, disconnected regions on a map, or separate communities within a larger social graph.

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

# City 4 is a fifth location with no road connecting it to the rest of the network
adjacency = csr_matrix([
    [0, 3, 0, 12, 0],
    [3, 0, 4, 0, 0],
    [0, 4, 0, 2, 0],
    [12, 0, 2, 0, 0],
    [0, 0, 0, 0, 0],
])

n_components, labels = connected_components(adjacency, directed=False)
print(n_components)   # 2 separate groups of cities
print(labels)          # which group (0 or 1) each city belongs to