压缩稀疏图形例程 (scipy.sparse.csgraph )

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

目录

connected_components \(csgraph[, directed, ...] )	分析稀疏图的连通分量
laplacian \(csgraph[, normed, return_diag, ...] )	返回有向图的拉普拉斯矩阵。
shortest_path \(csgraph[, method, directed, ...] )	在正向或无向图上执行最短路径图搜索。
dijkstra \(csgraph[, directed, indices, ...] )	基于Fibonacci堆的Dijkstra算法
floyd_warshall \(csgraph[, directed, ...] )	使用弗洛伊德-沃肖尔算法计算最短路径长度
bellman_ford \(csgraph[, directed, indices, ...] )	使用Bellman-Ford算法计算最短路径长度。
johnson \(csgraph[, directed, indices, ...] )	使用Johnson算法计算最短路径长度。
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 \(图表[, symmetric_mode] )	返回按反向Cuthill McKee顺序对稀疏CSR或CSC矩阵排序的置换数组。
maximum_flow \(csgraph，源，宿)	最大化图形中两个顶点之间的流量。
maximum_bipartite_matching \(图表[, perm_type] )	返回一个二部图的匹配，该二部图的基数与该图的任何给定匹配的基数一样小。
min_weight_full_bipartite_matching \(.[, ...] )	返回二部图的最小权重完全匹配。
structural_rank \(图表)	计算具有给定稀疏模式的图(矩阵)的结构秩。
NegativeCycleError \([message] )

construct_dist_matrix \(图表，前置任务[, ...] )	从前置矩阵构造距离矩阵
csgraph_from_dense \(图表[, null_value, ...] )	从稠密矩阵构造CSR格式的稀疏图。
csgraph_from_masked \(图表)	从掩码数组构造CSR格式的图形。
csgraph_masked_from_dense \(图表[, ...] )	从稠密矩阵构造掩码数组图表示。
csgraph_to_dense \(csgraph[, null_value] )	将稀疏图形表示转换为密集表示
csgraph_to_masked \(csgraph)	将稀疏图形表示转换为掩码数组表示
reconstruct_path \(csgraph，前置任务[, ...] )	从图表和前置任务列表构建一棵树。

图形表示法

本模块使用以矩阵格式存储的图表。一个有N个结点的图可以用一个(N×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的边连接。我们可以按如下方式构建密集、掩码和稀疏表示，请记住无向图由对称矩阵表示：

>>> 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由一条零权重的边连接。在这种情况下，上面的密集表示会导致歧义：如果零是有意义的值，如何表示非边？在这种情况下，必须使用掩码或稀疏表示来消除歧义：：

>>> 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模块中由一个布尔关键字指定。默认情况下，假定图形是有向的。在有向图中，从节点i到节点j的遍历可以在边G上完成 [i, j] ，但不是边G [j, i] 。请考虑以下密集图表：

>>> 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.parse表示(CSR、CSC或LIL格式)、掩码表示或具有由零、无穷大和NaN条目指示的非边的密集表示作为输入。

上一页

scipy.sparse.linalg.ArpackError

下一页

scipy.sparse.csgraph.connected_components