python igraph, intersection de graphes/union basée sur les noms de vertex/labels

Question

Je suis assez nouveau pour Python et surtout pour igraph. Pour ma thèse de bachelier, je dois comparer les graphiques et donc déterminer l'intersection et l'union du graphique. J'ai essayé les éléments suivants:

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) 

Si mon fichier JSON est comme suit:

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

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

Je devrait être la sortie de l'intersection être A> B. Mais au lieu de ce qui suit eteint est venu:

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 

Les premiers deux graphiques imprimés montrent que les deux graphiques d'entrée fonctionnent comme prévu (même je ne pas comprendre difficile où le « attr » est venu?). Mais le graphique de sortie ne considère pas que les sommets A et B de mes deux graphiques sont identiques alors que C et D le sont. Donc ma question: Comment puis-je déterminer l'intersection (et l'analogie de l'union) du graphe, en considérant mes étiquettes pour les sommets.

Answer 1

Dans la question Perform union of graphs based on vertex names Python igraph liée par paqmo, le mainteneur dit que cette fonctionnalité (unions ou intersections par nom de sommet) n'est pas disponible dans python-igraph. Donc, vous devrez écrire des fonctions pour le faire vous-même.

Voici une approche pour l'union. Ajoutez des sommets isolés aux deux graphes, afin qu'ils aient tous les deux le même ensemble de noms de sommets, puis permutez leurs deux ensembles de sommets afin que les noms soient dans le même ordre. Ensuite, la méthode standard union (de manière équivalente, l'opérateur |) fera le bon choix. Malheureusement, la méthode union ne gère pas les attributs, vous devez donc rajouter les noms et tous les autres attributs dont vous avez besoin.

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 

Nous pouvons faire quelque chose de similaire pour les intersections, à l'exception que l'on supprime les sommets de chaque graphique qui ne sont pas dans l'autre, puis permute les autres sommets à venir dans le même ordre dans les deux graphiques, avant d'utiliser la norme intersection (ou opérateur &).

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 

Anecdote: delete_vertices fait la bonne chose quand un ensemble donné, mais add_vertices n'a pas, à moins que nous nous tournons l'ensemble dans une première liste. Un ensemble avec, disons, deux éléments 'A' et 'B' entraîne l'ajout de deux sommets, tous deux nommés {'A', 'B'} - cela semble être un bug.