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ファイルがある：私はA-> Bであることを交差点の出力であることが予想

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

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

。しかし、その代わりにアウトプット以下は、思い付いた：

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は」どこから来たのか理解ドントさえ厳しいです？）。 しかし、出力グラフでは、CとDが同じ場合、両方のグラフの頂点AとBが同じであるとは考えられません。だから私の質問：グラフの頂点のラベルを考慮して、グラフの交点（および和集合）を決定するにはどうしたらいいですか？

Answer 1

paqmoによってリンクされたPerform union of graphs based on vertex names Python igraphの質問では、メンテナはpython-igraphではこの機能（頂点名による結合または交差）は利用できないと言います。だからあなたはそれを自分で行うための関数を書く必要があります。

ここでは、ユニオンのアプローチの1つです。孤立した頂点を両方のグラフに追加して、両方の頂点の名前が同じになるようにしてから、両方の頂点のセットを同じ順序で並べ替えるようにします。次に、標準の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ありません。例えば、2つの要素 'A'と 'B'を持つセットは、両方とも{'A', 'B'}という名前の2つの頂点を追加します。これはバグのようです。