我有一個 2D numpy 數組，其中每行包含 2 個整數。我想找到屬于共享公共元素的行的所有元素組（也稱為邊列表數組中圖形的連接組件）。例如，對于數組：[[ 0 4] [ 0 7] [ 1 2] [ 1 13] [ 2 1] [ 2 9] [ 3 14] [ 3 16] [ 4 0] [ 4 5] [ 5 4] [ 5 6] [ 6 5] [ 6 7] [ 7 0] [ 7 6]]將包含組[[ 0 4 5 6 7] [ 1 2 13 9] [ 3 14 16]]
3 回答
不負相思意
TA貢獻1777條經驗 獲得超10個贊
如果您可以使用庫，假設您的數組是a（請注意，您不能將組件作為 numpy 數組，因為它們可以是 numpy 中不存在的非矩形數組，因此這會將它們作為集合輸出）：
import networkx as nx
G=nx.Graph()
G.add_edges_from(a)
print(sorted(nx.connected_components(G), key = len, reverse=True))
#[{0, 4, 5, 6, 7}, {1, 2, 13, 9}, {16, 3, 14}]
小怪獸愛吃肉
TA貢獻1852條經驗 獲得超1個贊
就圖論而言，您需要從邊數組創建一個圖，然后找到該圖的連通分量。純粹的基于解決方案對我來說似乎太難了，但你仍然可以使用用 C 編寫的（與純 Python 不同）numpy使其成為 C 級別。您需要先安裝。igraphnetworkxpython-igraph
小事例
igraph.Graph.clusters()方法返回一個特殊的igraph.clustering.VertexClustering類實例，可以轉換為list：
import igraph
arr = np.array([[0, 4], [0, 7], [1, 2], [1, 9], [2, 1], [2, 8], [3, 10],
[3, 11], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = ig.Graph()
g.add_vertices(12)
g.add_edges(arr)
i = g.clusters()
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]
igraph還支持像在中完成的那樣繪制這些連接的組件networkx，但您可能需要pycairo從非官方二進制文件下載并安裝它才能解鎖igraph.plot選項：
pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors
color = pal.get_many(i.membership) # a list of color codes for each vertex
ig.plot(g, bbox = (200, 100), vertex_label=g.vs.indices,
vertex_color = color, vertex_size = 12, vertex_label_size = 8)
一般情況
請注意，如果使用初始數組而不是簡單的數組，igraph則會拋出一個異常。InternalError這是因為每個頂點都應該在添加邊之前聲明，并且所有頂點都不允許有缺失的數字（事實上，這是允許的，但重新索引是靜默完成的，并且可以使用“name”屬性訪問舊名稱）。這個問題可以通過編寫一個自定義函數來解決，該函數從重新標記的邊創建圖形：
def create_from_edges(edgelist):
g = ig.Graph()
u, inv = np.unique(edgelist, return_inverse=True)
e = inv.reshape(edgelist.shape)
g.add_vertices(u) #add vertices, not reindexed
g.add_edges(e) #add edges, reindexed
return g
arr = np.array([[0, 4], [0, 7], [1, 2], [1, 13], [2, 1], [2, 9], [3, 14],
[3, 16], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = create_from_edges(arr)
i = g.clusters()
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]
輸出中使用了新標簽（從而使其不正確），但仍然可以訪問舊標簽，如下所示：
print('new_names:', g.vs.indices)
print('old_names:', g.vs['name'])
>>> new_names: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> old_names: [0, 1, 2, 3, 4, 5, 6, 7, 9, 13, 14, 16]
它們可用于預覽原始圖表（vertex_label現在不同）：
pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors
color = pal.get_many(i.membership) ##a list of color codes for each vertex
ig.plot(g, bbox = (200, 100), vertex_label=g.vs['name'],
vertex_color = color, vertex_size = 12, vertex_label_size = 8)
最后，您需要使用舊的頂點名稱來修復輸出?？梢赃@樣做：
output = list(i)
old_names = np.array(g.vs['name'])
fixed_output = [old_names[n].tolist() for n in output]
#new output: [[0, 4, 5, 6, 7], [1, 2, 9, 13], [3, 14, 16]]
喵喔喔
TA貢獻1735條經驗 獲得超5個贊
我確信有更快的方法，而且我不研究圖論，但你可以從這個開始；
x = [[ 0, 4],
[ 0, 7],
[ 1, 2],
[ 1, 13],
[ 2, 1],
[ 2, 9],
[ 3, 14],
[ 3, 16],
[ 4, 0],
[ 4, 5],
[ 5, 4],
[ 5, 6],
[ 6, 5],
[ 6, 7],
[ 7, 0],
[ 7, 6]]
nodes = list(set([item for sublist in x for item in sublist]))
grps = {n: g for n, g in zip(nodes, range(len(nodes)))}
for v in x:
t = grps[v[0]]
f = grps[v[1]]
if t != f:
for n in grps:
if grps[n] == f:
grps[n] = t
ret = [[k for k, v in grps.items() if v==g] for g in set(grps.values())]
print(ret)
添加回答
舉報
0/150
提交
取消