'Isomorphic' comparison of NetworkX Graph objects instead of the default 'address' comparison

Question

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

Answer 1

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')]