Ctrl+K

壓縮稀疏圖常式 (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's 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])

傳回排列陣列，該陣列以反向 Cuthill-McKee 順序排列稀疏 CSR 或 CSC 矩陣。

maximum_flow(csgraph, source, sink)

最大化圖中兩個頂點之間的流量。

maximum_bipartite_matching(graph[, perm_type])

傳回二分圖的匹配，其基數至少為圖的任何給定匹配的基數。

min_weight_full_bipartite_matching(biadjacency)

傳回二分圖的最小權重完整匹配。

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_array
>>> G_sparse = csr_array(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_array(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 條目表示。

在本頁面上