Porównanie "izomorficzne" obiektów NetworkX Graph zamiast domyślnego porównania "adresu"

Question

Chciałbym użyć obiektów NetworkX Graph jako kluczy w Pythonie dict. Jednak nie chcę domyślnego zachowania dla porównania (tj. Przez adres obiektu). Zamiast tego chciałbym, aby wykresy izomorficzne były kluczami do tych samych elementów w dict.

Czy to zachowanie zostało już gdzieś zaimplementowane? Nie mogłem znaleźć żadnych informacji w tym kierunku.

Jeśli muszę sam je wdrożyć, czy następująca ocena jest realistyczna?

• Zawiń networkx.Graph w klasie.
• Zdefiniuj __eq__ w taki sposób, że wywołuje is_isomorphic.
• W jakiś sposób zdefiniuj __hash__ (sugestie przyjęte).

Myślę, że będę musiał zrobić to owinięty Graph niezmienne, because:

Jeśli klasa definiuje zmienne obiektów i wdraża metodę __eq__(), nie powinien wdrożyć __hash__(), od momentu wdrożenia hashable kolekcje wymagają, aby wartość skrótu klucza była niezmienna (jeśli wartość mieszania obiektu ulegnie zmianie, będzie ona w niewłaściwym buforze mieszającym).

Answer 1

Oto przykład z instacji do NetworkX Graph i dodanie eq i hash funkcję jak opisujesz. Nie jestem pewien, czy to rozwiązuje twój problem, ale powinien być początkiem.

import networkx as nx 

class myGraph(nx.Graph): 
    def __eq__(self, other): 
     return nx.is_isomorphic(self, other) 
    def __hash__(self): 
     return hash(tuple(sorted(self.degree().values()))) 


if __name__ == '__main__': 
    G1 = myGraph([(1,2)]) 
    G2 = myGraph([(2,3)]) 
    G3 = myGraph([(1,2),(2,3)]) 
    print G1.__hash__(), G1.edges() 
    print G2.__hash__(), G2.edges() 
    print G3.__hash__(), G3.edges() 
    print G1 == G2 
    print G1 == G3 
    graphs = {} 
    graphs[G1] = 'G1' 
    graphs[G2] = 'G2' 
    graphs[G3] = 'G3' 
    print graphs.items() 

wyjść coś takiego:

3713081631935493181 [(1, 2)] 
3713081631935493181 [(2, 3)] 
2528504235175490287 [(1, 2), (2, 3)] 
True 
False 
[(<__main__.myGraph object at 0xe47a90>, 'G2'), (<__main__.myGraph object at 0x1643250>, 'G3')] 
[aric@hamerkop tmp]$ python gc.py 
3713081631935493181 [(1, 2)] 
3713081631935493181 [(2, 3)] 
2528504235175490287 [(1, 2), (2, 3)] 
True 
False 
[(<__main__.myGraph object at 0x1fefad0>, 'G2'), (<__main__.myGraph object at 0x27ea290>, 'G3')]