0
我正在使用一個連接矩陣來表示圖形數據結構。 NxM矩陣對應於具有M個頂點的N條邊（它可能具有比頂點更多的邊，這就是爲什麼我使用scipy的csr_matrix）。邊緣的「開始」點由「-1」表示，終點在連通性矩陣中由「1」表示。所有其他值都是0，所以每行只有2個非零值。在scipy中更新稀疏連接矩陣
我需要整合一個「細分」方法，它將有效地更新連接矩陣。目前我正在將連通性矩陣轉換爲稠密矩陣，以便我可以添加新的行/列並更新舊的行。我轉換爲一個密集矩陣，因爲我還沒有找到解決方案來找到更新舊邊連接的列索引（沒有等效的scipy.where），並且csr表示不允許我通過索引來更新值。
from numpy import where, array, zeros, hstack, vstack
from scipy.sparse import coo_matrix, csr_matrix
def connectivity_matrix(edges):
m = len(edges)
data = array([-1] * m + [1] * m)
rows = array(list(range(m)) + list(range(m)))
cols = array([edge[0] for edge in edges] + [edge[1] for edge in edges])
C = coo_matrix((data, (rows, cols))).asfptype()
return C.tocsr()
def subdivide_edges(C, edge_indices):
C = C.todense()
num_e = C.shape[0] # number of edges
num_v = C.shape[1] # number of vertices
for edge in edge_indices:
num_e += 1 # increment row (edge count)
num_v += 1 # increment column (vertex count)
_, start = where(C[edge] == -1.0)
_, end = where(C[edge] == 1.0)
si = start[0]
ei = end[0]
# add row
r, c = C.shape
new_r = zeros((1, c))
C = vstack([C, new_r])
# add column
r, c = C.shape
new_c = zeros((r, 1))
C = hstack([C, new_c])
# edit edge start/end points
C[edge, ei] = 0.0
C[edge, num_v - 1] = 1.0
# add new edge start/end points
C[num_e - 1, ei] = 1.0
C[num_e - 1, num_v - 1] = -1.0
return csr_matrix(C)
edges = [(0, 1), (1, 2)] # edge connectivity
C = connectivity_matrix(edges)
C = subdivide_edges(C, [0, 1])
# new edge connectivity: [(0, 3), (1, 4), (3, 1), (4, 2)]