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 

Первые печатные и графики показывают, что оба входных графиков работы, как и ожидалось (даже жесткие я не понимаю, где «атр» пришел?). Но выходной граф не считает, что вершины A и B в обоих моих графах идентичны, а C и D. Итак, мой вопрос: как определить пересечение (и аналог объединения) графа, учитывая мои метки для вершин.

Answer 1

В вопросе Perform union of graphs based on vertex names Python igraph, связанным с paqmo, сопровождающий говорит, что эта функция (объединения или пересечения по имени вершин) недоступна в 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'} - это похоже на ошибку.