獲取網絡中所有斷開連接的節點對

Question

我已經使用igraph（無向）編碼了一個網絡，並且我想獲得網絡中未連接的節點對的列表。

翻閱igraph的文檔（Python），我還沒有找到這樣做的方法。我必須手動執行此操作嗎？

一個相關的問題：給定網絡中的任何節點對，如何使用igraph找到這兩個節點的公共鄰居列表？再次看來，igraph似乎沒有這種方法。

Answer 1

重新對第一個問題（上市斷開連接的節點對）：是的，你必須手動做到這一點，但它是相當容易：

from itertools import product 

all_nodes = set(range(g.vcount()) 
disconnected_pairs = [list(product(cluster, all_nodes.difference(cluster))) \ 
         for cluster in g.clusters()] 

但要注意，這可能是一個相當大的列表，如果你的圖形很大，由很多不連通的組件組成。

再第二個問題（上市常見的鄰居）：同樣，你必須手動做到這一點，但只需要在Python一個交集操作：

set(g.neighbors(v1)).intersection(set(g.neighbors(v2))) 

如果你發現你需要做到這一點對於許多節點對，你應該創建鄰居首先設置：

neighbor_sets = [set(neis) for neis in g.get_adjlist()] 

然後，你可以簡單地寫neighbor_sets[i]而不是set(g.neighbors(i))。