Python-Grafik, Graph-Schnittpunkt/Vereinigung basierend auf Vertex-Namen/Labels

Question

Ich bin ziemlich neu in Python und besonders in iigraph. Für meine Bachelorarbeit muss ich Graphen vergleichen und die Schnittmenge und Vereinigung der Graphen bestimmen. Ich habe versucht, die folgenden:

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) 

Wo meine JSON-Datei ist wie folgt:

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

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

ich erwartet hatte der Ausgang der Kreuzung sein A-> B. Aber anstatt die folgenden heraus gesetzt kam:

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 

Die ersten beiden gedruckten Diagramme zeigen, dass die beiden Eingänge grafischen Darstellungen wie erwartet (auch hart ich verstehe nicht, wo die ‚attr‘ kam?). Aber der Ausgabe-Graph berücksichtigt nicht, dass die Eckpunkte A und B in meinen beiden Graphen identisch sind, während C und D sind. Also meine Frage: Wie kann ich die Schnittmenge (und analog die Vereinigung) des Graphen bestimmen, wenn ich meine Beschriftungen für die Eckpunkte betrachte.

Answer 1

In der Frage Perform union of graphs based on vertex names Python igraph, die durch paqmo verbunden ist, sagt der Betreuer, dass diese Funktionalität (Vereinigungen oder Kreuzungen nach Vertexnamen) in Python-igraph nicht verfügbar ist. Sie müssen also Funktionen schreiben, um es selbst zu tun.

Hier ist ein Ansatz für die Union. Fügen Sie den beiden Graphen isolierte Scheitelpunkte hinzu, so dass beide denselben Scheitelpunktnamen haben, und vertauschen Sie dann beide Scheitelpunktsätze, so dass die Namen in der gleichen Reihenfolge erscheinen. Dann wird die Standardmethode union (äquivalent, der Operator |) das Richtige tun. Leider enthält die Methode union keine Attribute, daher müssen Sie die Namen und alle anderen benötigten Attribute hinzufügen.

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 

Wir können für Kreuzungen etwas ähnliches tun, mit der Ausnahme, dass wir Eckpunkte von jedem Diagramm zu entfernen, die nicht in den andere sind, dann vertauschen die restlichen Ecken in derselben Reihenfolge in beiden Graphen kommen, bevor mit dem Standard intersection Methode (oder & Operator).

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 

Trivia: delete_vertices das Richtige tut, wenn eine Menge gegeben, aber add_vertices nicht, es sei denn, wir die Menge in eine Liste zuerst drehen. Eine Menge mit, sagen wir, zwei Elementen 'A' und 'B' ergibt zwei Eckpunkte, beide mit dem Namen {'A', 'B'} - dies scheint ein Fehler zu sein.