压缩稀疏图例程（scipy.sparse.csgraph)#

基于稀疏矩阵表示的快速图算法。

内容#

connected_components(csgraph[, directed, ...])

分析稀疏图的连通分量

laplacian(csgraph[, normed, return_diag, ...])

返回有向图的拉普拉斯矩阵。

shortest_path(csgraph[, method, directed, ...])

在正向有向或无向图上执行最短路径图搜索。

dijkstra(csgraph[, directed, indices, ...])

使用斐波那契堆的 Dijkstra 算法

floyd_warshall(csgraph[, directed, ...])

使用 Floyd-Warshall 算法计算最短路径长度

bellman_ford(csgraph[, directed, indices, ...])

使用 Bellman-Ford 算法计算最短路径长度。

johnson(csgraph[, directed, indices, ...])

使用 Johnson 算法计算最短路径长度。

yen(csgraph, source, sink, K, *[, directed, ...])

在有向或无向图上应用 Yen 的 K 最短路径算法。

breadth_first_order(csgraph, i_start[, ...])

返回从指定节点开始的广度优先排序。

depth_first_order(csgraph, i_start[, ...])

返回从指定节点开始的深度优先排序。

breadth_first_tree(csgraph, i_start[, directed])

返回由广度优先搜索生成的树

depth_first_tree(csgraph, i_start[, directed])

返回由深度优先搜索生成的树。

minimum_spanning_tree(csgraph[, overwrite])

返回无向图的最小生成树

reverse_cuthill_mckee(graph[, symmetric_mode])

返回将稀疏 CSR 或 CSC 矩阵以反向 Cuthill McKee 排序排列的排列数组。

maximum_flow(csgraph, source, sink)

最大化图中两个顶点之间的流量。

maximum_bipartite_matching(graph[, perm_type])

返回二部图的匹配，其基数至少与图的任何给定匹配的基数相同。

min_weight_full_bipartite_matching(...[, ...])

返回二部图的最小权重完全匹配。

structural_rank(graph)

计算具有给定稀疏模式的图（矩阵）的结构秩。

NegativeCycleError([message])

construct_dist_matrix(graph, predecessors[, ...])

从前驱矩阵构建距离矩阵

csgraph_from_dense(graph[, null_value, ...])

从密集矩阵构建 CSR 格式的稀疏图。

csgraph_from_masked(graph)

从掩码数组构建 CSR 格式的图。

csgraph_masked_from_dense(graph[, ...])

从密集矩阵构建掩码数组图表示。

csgraph_to_dense(csgraph[, null_value])

将稀疏图表示转换为密集表示

csgraph_to_masked(csgraph)

将稀疏图表示转换为掩码数组表示

reconstruct_path(csgraph, predecessors[, ...])

从图和前驱列表构建树。

图表示#

此模块使用以矩阵格式存储的图。具有 N 个节点的图可以用 (N x N) 邻接矩阵 G 表示。如果从节点 i 到节点 j 有连接，则 G[i, j] = w，其中 w 是连接的权重。对于未连接的节点 i 和 j，其值取决于表示

  • 对于密集数组表示，非边缘用 G[i, j] = 0、无穷大或 NaN 表示。

  • 对于密集掩码表示（类型为 np.ma.MaskedArray），非边缘用掩码值表示。当需要具有零权重边缘的图时，这可能很有用。

  • 对于稀疏数组表示，非边缘用矩阵中的非条目表示。这种稀疏表示也允许权重为零的边缘。

作为一个具体的例子，假设您想表示以下无向图

      G

     (0)
    /   \
   1     2
  /       \
(2)       (1)

此图有三个节点，节点 0 和 1 由权重为 2 的边连接，节点 0 和 2 由权重为 1 的边连接。我们可以构建密集、掩码和稀疏表示，记住无向图由对称矩阵表示

>>> import numpy as np
>>> G_dense = np.array([[0, 2, 1],
...                     [2, 0, 0],
...                     [1, 0, 0]])
>>> G_masked = np.ma.masked_values(G_dense, 0)
>>> from scipy.sparse import csr_matrix
>>> G_sparse = csr_matrix(G_dense)

当零边缘很重要时，这变得更加困难。例如，考虑当我们稍微修改上面的图时的情况

     G2

     (0)
    /   \
   0     2
  /       \
(2)       (1)

这与前面的图相同，只是节点 0 和 2 由权重为零的边连接。在这种情况下，上面的密集表示会导致歧义：如果零是有意义的值，如何表示非边缘？在这种情况下，必须使用掩码或稀疏表示来消除歧义

>>> import numpy as np
>>> G2_data = np.array([[np.inf, 2,      0     ],
...                     [2,      np.inf, np.inf],
...                     [0,      np.inf, np.inf]])
>>> G2_masked = np.ma.masked_invalid(G2_data)
>>> from scipy.sparse.csgraph import csgraph_from_dense
>>> # G2_sparse = csr_matrix(G2_data) would give the wrong result
>>> G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
>>> G2_sparse.data
array([ 2.,  0.,  2.,  0.])

这里我们使用了 csgraph 子模块中的一个实用例程，以便将密集表示转换为稀疏表示，该表示可以被子模块中的算法理解。通过查看数据数组，我们可以看到零值在图中被明确编码。

有向与无向#

矩阵可以表示有向图或无向图。这在整个 csgraph 模块中由一个布尔关键字指定。默认情况下，假设图是有向的。在有向图中，可以通过边缘 G[i, j] 从节点 i 到节点 j 进行遍历，但不能通过边缘 G[j, i] 进行遍历。考虑以下密集图

>>> import numpy as np
>>> G_dense = np.array([[0, 1, 0],
...                     [2, 0, 3],
...                     [0, 4, 0]])

当 directed=True 时，我们得到图

  ---1--> ---3-->
(0)     (1)     (2)
  <--2--- <--4---

在无向图中，可以通过 G[i, j] 或 G[j, i] 从节点 i 到节点 j 进行遍历。如果两个边缘都不是空，并且两个边缘的权重不相等，则使用较小的权重。

因此，对于同一个图，当 directed=False 时，我们得到图

(0)--1--(1)--3--(2)

请注意，无论“directed”关键字设置为 True 还是 False，对称矩阵都将表示无向图。在这种情况下，使用 directed=True 通常会导致更有效的计算。

此模块中的例程接受 scipy.sparse 表示（csr、csc 或 lil 格式）、掩码表示或密集表示作为输入，其中非边缘用零、无穷大和 NaN 条目表示。

本页内容