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)]