7

I would like to use NetworkX Graph objects as keys in a Python dict. However, I do not want the default behavior for comparison (i.e., by the address of the object). Instead, I would like isomorphic graphs to refer to be keys to the same elements in the dict.

Is this behavior already implemented somewhere? I could not find any information in this direction.

If I have to implement it myself, is the following assessment realistic?

  • Wrap networkx.Graph in a class.
  • Define __eq__ such that it calls is_isomorphic.
  • Define __hash__ somehow (suggestions welcomed).

I think that I would have to make this wrapped Graph immutable, because:

If a class defines mutable objects and implements an __eq__() method, it should not implement __hash__(), since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

user1661473
  • 185
  • 1
  • 6
  • 1
    Do I understand correctly that you want isophorphic graphs to have the same hash() value? If so does this help you with the question? - http://en.wikipedia.org/wiki/Graph_canonization – Aric Dec 11 '13 at 23:55
  • @Aric If I have to implement it myself, then yes, I do want isomorphic graph to have the same `__hash__()` value. However, graph canonization may be overkill. What I had in mind was to get the [ordered degree sequence](http://en.wikipedia.org/wiki/Degree_sequence#Degree_sequence), then to hash it. Doing so, non-isomorphic graphs could have the same hash, but isomorphic graphs could not have different hash. But before starting to do that, I first hope that someone has already done it somewhere :) – user1661473 Dec 12 '13 at 01:02
  • If you can find a way to make a unique integer out of the degree sequence you could use that as a hash() function. – Aric Dec 12 '13 at 03:32
  • @Aric As I understand it, the integer needs not be unique. In fact, as mentioned [here](http://stackoverflow.com/a/4005412/1661473), it could just `return 0` (but this would give poor performances). What I had in mind was to, say, put the ordered degree sequence in a tuple, then call the `__hash()__` function of that tuple. But again, my most important question is: "Are these capabilities already implemented somewhere?" – user1661473 Dec 12 '13 at 17:13
  • It's a pretty specific use case so maybe nobody has done exactly that. I suggested an answer with a code example below. – Aric Dec 13 '13 at 00:35

1 Answers1

3

Here is an example of subclassing a networkx Graph and adding a eq and hash function as you describe. I'm not sure if it solves your problem but should be a start. 

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

Outputs something like:

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')]
Aric
  • 24,511
  • 5
  • 78
  • 77
  • 1
    Thanks. I will probably end up doing something like that. If someone has a similar problem, I recommend to call `freeze` on your `myGraph` objects (hence making them immutable) before using them as keys. – user1661473 Dec 13 '13 at 17:53
  • 1
    @user1661473 did you manage to find an hash function such that it gives the same hash if two graph are isomorphic? I'm having a similar problem. – dome May 08 '19 at 15:28