SciPy - CSGraph

SciPy - CSGraph：压缩稀疏图

scipy.sparse.csgraph 是 SciPy 的一个子模块，专门用于在图的稀疏矩阵表示上运行的图算法。对于节点很多但边（连接）相对较少的图来说，使用稀疏矩阵（sparse matrix）效率非常高。

图的表示

在深入探讨算法之前，先了解图是如何表示的，特别是稀疏图（sparse graph）。

什么是稀疏图？

图（graph）是由节点（nodes 或 vertices）和连接它们的边（edges 或 links）组成的集合。图可以建模各种系统：社交网络（人是节点，友谊是边）、分子结构（原子是节点，化学键是边）、网页（页面是节点，超链接是边）等等。

表示图的一种常用方法是使用邻接矩阵（adjacency matrix），例如 G。对于一个有 N 个节点的图，G 是一个 N x N 矩阵，其中 G[i, j] 表示节点 i 和节点 j 之间的连接（以及可能的权重）。稀疏图是大多数节点只连接到少数其他节点的图，这意味着其邻接矩阵包含大量零。这种稀疏性在现实世界的图中很常见，可以显著节省内存和计算资源。

scipy.sparse.csgraph 模块被开发用于支持各种算法，包括机器学习和数据分析任务中使用的算法，例如：

• Shortest path finding: 用于路由、网络分析（例如 Isomap）。
• Minimum spanning tree: 用于网络设计、聚类（例如 Hierarchical clustering）。
• Connected components: 识别相互连接的节点组（连通分量）。
• Graph traversals: 探索图结构（例如 Breadth-First Search 广度优先搜索, Depth-First Search 深度优先搜索）。

考虑表示以下无向图：节点 0 和节点 1 通过权重为 2 的边连接，节点 0 和节点 2 通过权重为 1 的边连接。节点 1 和节点 2 没有直接连接。

我们可以使用密集矩阵（dense matrix）、掩码矩阵（masked matrix）或稀疏矩阵来表示。对于无向图，邻接矩阵是对称的。

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())

G_sparse.data 的输出将显示非零值：

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

如果零是一个有意义的边权重（例如，零成本的连接），密集表示就会变得模糊不清。例如，如果节点 0 和节点 2 通过权重为 0 的边连接。在这种情况下，需要使用掩码数组（其中非边被明确标记）或稀疏表示（仅存储实际存在的边）来避免混淆。

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())

这将输出：

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

示例：使用稀疏图解决单词阶梯问题

单词阶梯（word ladder）是一个谜题，你需要通过每次只改变一个字母，将起始单词转换成目标单词，并且每一步中间词都必须是有效词。例如：APE → APT → OPT → OAT → MAT → MAN。我们希望找到最短的这样的阶梯。

这个问题可以建模为在图（graph）中寻找最短路径。节点是单词，如果两个单词只相差一个字母，则它们之间存在一条边（edge）。

构建单词图并寻找阶梯

首先，我们需要一个有效单词列表。在本教程中，我们将使用一个预定义的小型 3 字母单词列表。

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

现在我们的图已经建立好了，让我们找到从 ‘ape’ 到 ‘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])}")

输出将显示步数和重建的路径：

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

这个例子演示了如何使用稀疏图表示和 scipy.sparse.csgraph 中的算法来解决有趣的问题。该模块还提供了其他算法，如 breadth_first_order（广度优先顺序），depth_first_order（深度优先顺序），connected_components（连通分量）和 minimum_spanning_tree（最小生成树），可用于更复杂的图分析。