SciPy - CSGraph

SciPy - CSGraph: Compressed Sparse Graphs

scipy.sparse.csgraph is a SciPy submodule dedicated to graph algorithms that operate on sparse matrix representations of graphs. Using sparse matrices is highly efficient for graphs with many nodes but relatively few edges (connections).

Graph Representations

Before diving into algorithms, let’s understand how graphs can be represented, especially sparse graphs.

What is a Sparse Graph?

A graph is a collection of nodes (or vertices) connected by links (or edges). Graphs can model diverse systems: social networks (people as nodes, friendships as edges), molecular structures (atoms as nodes, bonds as edges), web pages (pages as nodes, hyperlinks as edges), and much more.

One common way to represent a graph is using an adjacency matrix, say G. For a graph with N nodes, G is an N x N matrix where G[i, j] represents the connection (and possibly its weight) between node i and node j. A sparse graph is one where most nodes are connected to only a few other nodes, meaning its adjacency matrix contains mostly zeros. This sparsity is common in real-world graphs and allows for significant memory and computational savings.

The scipy.sparse.csgraph module was developed to support various algorithms, including those used in machine learning and data analysis tasks such as:

• Shortest path finding: Used in routing, network analysis (e.g., Isomap).
• Minimum spanning tree: Used in network design, clustering (e.g., Hierarchical clustering).
• Connected components: Identifying groups of connected nodes.
• Graph traversals: Exploring graph structures (e.g., Breadth-First Search, Depth-First Search).

Consider representing the following undirected graph: Node 0 and Node 1 are connected by an edge of weight 2, and Node 0 and Node 2 are connected by an edge of weight 1. Node 1 and Node 2 are not directly connected.

We can represent this using dense, masked, or sparse matrices. For an undirected graph, the adjacency matrix is symmetric.

import numpy as np
from scipy.sparse import csr_matrix

# Dense representation
G_dense = np.array([
    [0, 2, 1],
    [2, 0, 0],
    [1, 0, 0]
])
print("Dense representation:\n", G_dense)

# Masked representation (useful if 0 is a valid edge weight)
# G_masked = np.ma.masked_values(G_dense, 0) # Non-edges are masked

# Sparse representation (CSR format is common and efficient)
G_sparse = csr_matrix(G_dense)
print("\nSparse representation (CSR format data):\n", G_sparse.data)
print("Sparse representation (full matrix view):\n", G_sparse.toarray())

The output for G_sparse.data will show the non-zero values:

Dense representation:
 [[0 2 1]
 [2 0 0]
 [1 0 0]]

Sparse representation (CSR format data):
 [2 1 2 1]
Sparse representation (full matrix view):
 [[0 2 1]
 [2 0 0]
 [1 0 0]]

If zero is a meaningful edge weight (e.g., a connection with zero cost), dense representations become ambiguous. For instance, if Node 0 and Node 2 were connected by an edge of weight 0. In such cases, a masked array (where non-edges are explicitly marked) or a sparse representation (which only stores actual edges) is necessary to avoid confusion.

from scipy.sparse.csgraph import csgraph_from_dense

# Example where 0 is a valid edge weight, and np.inf represents no edge
G2_data_with_inf = np.array([
    [np.inf, 2,    0   ],
    [2,    np.inf, np.inf],
    [0,    np.inf, np.inf]
])

# Convert to sparse, treating np.inf as the null value (no edge)
G2_sparse = csgraph_from_dense(G2_data_with_inf, null_value=np.inf)
print("\nGraph with explicit nulls (sparse data):\n", G2_sparse.data)
print("Graph with explicit nulls (full matrix view):\n", G2_sparse.toarray())

This will output:

Graph with explicit nulls (sparse data):
 [2. 0. 2. 0.]
Graph with explicit nulls (full matrix view):
 [[0. 2. 0.]
 [2. 0. 0.]
 [0. 0. 0.]]

Example: Word Ladders using Sparse Graphs

A word ladder is a puzzle where one transforms a starting word into an ending word by changing only one letter at each step, with each intermediate step also being a valid word. For example: APE → APT → OPT → OAT → MAT → MAN. We want to find the shortest such ladder.

This problem can be modeled as finding the shortest path in a graph. Nodes are words, and an edge exists between two words if they differ by exactly one letter.

Building the Word Graph and Finding a Ladder

First, we need a list of valid words. For this tutorial, we’ll use a small, predefined list of 3-letter words.

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

# A small list of 3-letter words for our example
word_list_py = ['ape', 'apt', 'asp', 'oat', 'opt', 'map', 'man', 'men', 'tap', 'top', 'mat', 'pat']
word_list_py.sort() # Sorting is good practice, especially for searchsorted later

word_list = np.array(word_list_py)
num_words = len(word_list)

# Function to check if two words are connected (differ by one letter)
def are_connected(word1, word2):
    if len(word1) != len(word2):
        return False
    diff_count = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            diff_count += 1
    return diff_count == 1

# Create an adjacency matrix (dense first, then convert to sparse)
adj_matrix = np.zeros((num_words, num_words))

for i in range(num_words):
    for j in range(i + 1, num_words): # Avoid self-loops and duplicate checks
        if are_connected(word_list[i], word_list[j]):
            adj_matrix[i, j] = 1 # Edge weight is 1 (one step)
            adj_matrix[j, i] = 1 # Undirected graph

# Convert to a sparse matrix
graph = csr_matrix(adj_matrix)

print(f"Number of words: {num_words}")
print(f"Shape of adjacency matrix: {graph.shape}")
print(f"Number of connections (edges): {graph.nnz // 2}") # //2 because undirected

Now that our graph is set up, let’s find the shortest path between ‘ape’ and ‘man’.

# Find indices of the start and end words
# np.searchsorted requires a sorted array
start_word = 'ape'
end_word = 'man'

try:
    idx_start = np.searchsorted(word_list, start_word)
    idx_end = np.searchsorted(word_list, end_word)
    # Verify that the words were actually found at these indices
    if word_list[idx_start] != start_word or word_list[idx_end] != end_word:
        raise ValueError("Start or end word not in list")
except (IndexError, ValueError):
    print(f"Error: One or both words ('{start_word}', '{end_word}') not in the word list.")
    exit()

print(f"\nFinding path from '{word_list[idx_start]}' (index {idx_start}) to '{word_list[idx_end]}' (index {idx_end})")

# Use Dijkstra's algorithm to find shortest paths from idx_start
# It returns distances and predecessors (for path reconstruction)
distances, predecessors = dijkstra(csgraph=graph, directed=False, indices=idx_start, return_predecessors=True)

shortest_distance = distances[idx_end]
print(f"Shortest distance (number of steps): {shortest_distance}")

# Reconstruct the path
if np.isinf(shortest_distance):
    print(f"No path found between '{start_word}' and '{end_word}'.")
else:
    path = []
    curr_node_idx = idx_end
    while curr_node_idx != idx_start:
        path.append(word_list[curr_node_idx])
        prev_node_idx = predecessors[curr_node_idx]
        if prev_node_idx == -9999: # No predecessor, path broken or start reached
            print("Error in path reconstruction.")
            path = [] # Clear partial path
            break
        curr_node_idx = prev_node_idx
    if path: # if loop completed correctly
        path.append(word_list[idx_start])
        print(f"Shortest path: {' → '.join(path[::-1])}")

The output will show the number of steps and the reconstructed path:

Number of words: 12
Shape of adjacency matrix: (12, 12)
Number of connections (edges): 10

Finding path from 'ape' (index 0) to 'man' (index 4)
Shortest distance (number of steps): 3.0
Shortest path: ape → apt → pat → man

This example demonstrates how sparse graph representations and algorithms from scipy.sparse.csgraph can solve interesting problems. Other algorithms like breadth_first_order, depth_first_order, connected_components, and minimum_spanning_tree are also available for more complex graph analyses.