python igraph，基於頂點名稱/標籤的圖交集/聯合

Question

我特別喜歡Python和igraph。對於我的學士論文，我必須比較圖表並確定圖表交點和聯合。我試過如下：

from igraph import * 
import json 

with open('test_graphs.json') as data_file: 
    data = json.load(data_file) 

test1 = data['test1'] 
test2 = data['test2'] 

t1 = Graph(directed=True) 
for v in test1: 
    t1.add_vertex(v) 
for v in test1: 
    for o in test1[v]: 
     t1.add_edge(v, o) 
print(t1) 

t2 = Graph(directed=True) 
for v in test2: 
    t2.add_vertex(v) 
for v in test2: 
    for o in test2[v]: 
     t2.add_edge(v, o) 

print(t2) 

gr = t1.intersection(t2) 
print(gr) 

凡我JSON文件如下：

{ 
    "test1" : { 
     "A": ["B","C"], 
     "B": [], 
     "C": [] 
    }, 

    "test2" : { 
     "A": ["B","D"], 
     "B": [], 
     "D": [] 
    } 
} 

我預計的路口輸出爲A-> B。而是下面放了上來：

IGRAPH DN-- 3 2 -- 
+ attr: name (v) 
+ edges (vertex names): 
A->B, A->C 
IGRAPH DN-- 3 2 -- 
+ attr: name (v) 
+ edges (vertex names): 
A->B, A->D 
IGRAPH D--- 3 2 -- 
+ edges: 
2->0 2->1 

第一印雙方圖表表明，這兩個輸入圖形按預期工作（即使艱難我不明白的地方的「ATTR」是從哪裏來的？）。 但是輸出圖並不認爲我的圖中的頂點A和B是相同的，而C和D是相同的。所以我的問題：我怎樣才能確定圖的交集（並模擬聯合），考慮我的頂點標籤。

Answer 1

在由paqmo鏈接的Perform union of graphs based on vertex names Python igraph問題中，維護者說這個功能（按頂點名稱的聯合或交叉點）在python-igraph中不可用。所以你將不得不編寫函數來自己做。

這是工會的一種方法。將兩個獨立的頂點添加到兩個圖中，以使它們都具有相同的一組頂點名稱，然後對它們的兩組頂點進行置換，以便名稱以相同順序排列。然後標準的union方法（相當於|運營商）將做正確的事情。遺憾的是，union方法不保留屬性，所以您必須添加名稱以及您需要的任何其他屬性。

def named_union(graph1, graph2): 
    A = graph1.copy() 
    B = graph2.copy() # so added vertices don't affect original graphs 
    Anams = set(A.vs['name']) 
    Bnams = set(B.vs['name']) 
    A.add_vertices(list(Bnams - Anams)) 
    B.add_vertices(list(Anams - Bnams)) 
    nams = sorted(Anams | Bnams) 
    Aind = [nams.index(nm) for nm in A.vs['name']] 
    Bind = [nams.index(nm) for nm in B.vs['name']] 
    A = A.permute_vertices(Aind) # permute vertices to come in same order as in nams 
    B = B.permute_vertices(Bind) # ditto 
    Z = A | B 
    Z.vs['name'] = nams 
    return Z 

我們可以做交叉類似，不同之處在於我們要從每個圖這是不是在其他頂點，然後置換剩餘的頂點進來兩圖相同的順序，使用標準的前intersection方法（或&運營商）。

def named_intersect(graph1, graph2): 
    A = graph1.copy() 
    B = graph2.copy() # so removed vertices don't affect original graphs 
    Anams = set(A.vs['name']) 
    Bnams = set(B.vs['name']) 
    A.delete_vertices(Anams - Bnams) 
    B.delete_vertices(Bnams - Anams) 
    nams = sorted(Anams & Bnams) 
    Aind = [nams.index(nm) for nm in A.vs['name']] 
    Bind = [nams.index(nm) for nm in B.vs['name']] 
    A = A.permute_vertices(Aind) 
    B = B.permute_vertices(Bind) 
    Z = A & B 
    Z.vs['name'] = nams 
    return Z 

花絮：delete_vertices做正確的事給定一組的時候，但add_vertices沒有，除非我們把集合到一個列表第一。一個包含兩個元素'A'和'B'的集合導致添加兩個頂點，這兩個頂點都被命名爲{'A', 'B'}-這看起來像一個錯誤。