2013-12-11 7 views
5

Ich würde gerne NetworkX Graph Objekte als Schlüssel in einem Python dict verwenden. Ich möchte jedoch nicht das Standardverhalten für den Vergleich (d. H. Durch die Adresse des Objekts). Stattdessen möchte ich, dass sich iso- morphe Graphen als Schlüssel für die gleichen Elemente in dict bezeichnen.'Isomorphe' Vergleich der NetworkX Graph-Objekte anstelle der Standard 'Adresse' Vergleich

Ist dieses Verhalten bereits irgendwo implementiert? Ich konnte keine Informationen in dieser Richtung finden.

Wenn ich es selbst implementieren muss, ist die folgende Einschätzung realistisch?

  • Wrap networkx.Graph in einer Klasse.
  • Definieren Sie __eq__ so, dass es is_isomorphic aufruft.
  • Definieren Sie __hash__ irgendwie (Vorschläge willkommen).

Ich denke, dass ich diese gewickelte Graph unveränderlich machen hätte, because:

Wenn eine Klasse veränderbare Objekte definiert und implementiert eine __eq__() Methode, sollte es nicht __hash__() implementieren, da die Umsetzung der hashable Auflistungen erfordern, dass der Hash-Wert eines Schlüssels unveränderlich ist (wenn sich der Hash-Wert des Objekts ändert, befindet er sich im falschen Hash-Bucket). Hier

+1

Verstehe ich richtig, dass Sie isophorphic Graphen wollen den gleichen Hash haben() Wert? Wenn ja, hilft dir das bei der Frage? - http://en.wikipedia.org/wiki/Graph_canonization – Aric

+0

@Aric Wenn ich es selbst implementieren muss, dann ja, ich möchte, dass isomorphe Graphen den gleichen '__hash __()' Wert haben. Die Kanonisierung von Graphen ist jedoch möglicherweise übertrieben. Was ich im Sinn hatte, war, die [geordnete Abschlusssequenz] (http://en.wikipedia.org/wiki/Degree_sequence#Degree_sequence) zu bekommen und sie dann zu hashen. Wenn Sie dies tun, können nicht-isomorphe Graphen den gleichen Hash haben, aber isomorphe Graphen können keinen anderen Hash haben. Aber bevor ich damit anfange, hoffe ich zuerst, dass jemand es irgendwo schon getan hat :) – user1661473

+0

Wenn Sie einen Weg finden können, eine eindeutige ganze Zahl aus der Grad-Sequenz zu machen, könnten Sie diese als hash() -Funktion verwenden. – Aric

Antwort

3

ist ein Beispiel für eine Subklassen NetworkX Graph und das Hinzufügen einer eq und Hash Funktion, wie Sie beschreiben. Ich bin nicht sicher, ob es dein Problem löst, aber sollte ein Anfang sein.

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() 

Ausgänge so etwas wie:

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')] 
[[email protected] 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')] 
+1

Danke. Ich werde wahrscheinlich so etwas tun. Wenn jemand ein ähnliches Problem hat, empfehle ich, 'freeze' auf den' myGraph'-Objekten aufzurufen (also unveränderlich zu machen), bevor Sie sie als Schlüssel verwenden. – user1661473