压缩稀疏图例程 (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矩阵按Reverse-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 子模块中的一个实用程序例程，以便将密集表示转换为稀疏表示，该表示可以被子模块中的算法理解。通过查看数据数组，我们可以看到零值在图中被显式编码。

有向 vs. 无向

矩阵可以表示有向图或无向图。这在csgraph模块中通过一个布尔关键字指定。默认情况下，图被假定为有向的。在有向图中，从节点i到节点j的遍历可以通过边G[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---

在无向图中，从节点 i 到节点 j 的遍历可以通过 G[i, j] 或 G[j, i] 完成。如果两条边都不为空，并且它们的权重不相等，则使用较小的那条边。

因此，对于相同的图，当 directed=False 时，我们得到图:

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

请注意，无论 ‘directed’ 关键字设置为 True 还是 False，对称矩阵都将表示一个无向图。在这种情况下，使用 directed=True 通常会带来更高效的计算。

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