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'}-这看起来像一个错误。