{"action":"created","issue":{"url":"https://api.github.com/repos/networkx/networkx/issues/3133","repository_url":"https://api.github.com/repos/networkx/networkx","labels_url":"https://api.github.com/repos/networkx/networkx/issues/3133/labels{/name}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/3133/comments","events_url":"https://api.github.com/repos/networkx/networkx/issues/3133/events","html_url":"https://github.com/networkx/networkx/issues/3133","id":353818329,"node_id":"MDU6SXNzdWUzNTM4MTgzMjk=","number":3133,"title":"Hashable graphs?","user":{"login":"ryanpeach","id":14838729,"node_id":"MDQ6VXNlcjE0ODM4NzI5","avatar_url":"https://avatars1.githubusercontent.com/u/14838729?v=4","gravatar_id":"","url":"https://api.github.com/users/ryanpeach","html_url":"https://github.com/ryanpeach","followers_url":"https://api.github.com/users/ryanpeach/followers","following_url":"https://api.github.com/users/ryanpeach/following{/other_user}","gists_url":"https://api.github.com/users/ryanpeach/gists{/gist_id}","starred_url":"https://api.github.com/users/ryanpeach/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ryanpeach/subscriptions","organizations_url":"https://api.github.com/users/ryanpeach/orgs","repos_url":"https://api.github.com/users/ryanpeach/repos","events_url":"https://api.github.com/users/ryanpeach/events{/privacy}","received_events_url":"https://api.github.com/users/ryanpeach/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2018-08-24T14:58:22Z","updated_at":"2018-09-05T03:54:11Z","closed_at":null,"author_association":"NONE","body":"The behavior of hashing a graph is not ideal.\r\n\r\nFor reference, this is how hashing a graph currently works:\r\n\r\n```python\r\nIn[10]: G = nx.balanced_tree(4,2)\r\nIn [11]: hash(G)\r\nOut[11]: 275084920\r\nIn [12]: G.add_node(100)\r\nIn [13]: hash(G)\r\nOut[13]: 275084920\r\n```\r\n\r\nFurther:\r\n\r\n```python\r\nIn [14]: G.nodes()\r\nOut[14]: NodeView((0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 100))\r\nIn [15]: G = nx.balanced_tree(4,2)\r\nIn [16]: hash(G)\r\nOut[16]: -9223372036579765409\r\nIn [17]: G.nodes()\r\nOut[17]: NodeView((0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20))\r\n```\r\n\r\nSo basically, the way it works now is that graphs are assigned a hash upon creation, and it does not change if they change. It is also not the case that two graphs which are exactly similar have the same hash.\r\n\r\nFurther, the following:\r\n\r\n```python\r\nIn [18]: nx.balanced_tree(4,2) == nx.balanced_tree(4,2)\r\nOut[18]: False\r\n```\r\n\r\nThis is not ideal if you want to memoize a function that has a graph as a parameter (my specific use case), or compare graphs.\r\n\r\nMy proposed solution would be to create a hashing function something akin to the following:\r\n\r\n```python\r\ndef __hash__(self):\r\n    return hash(set(self.nodes()) | set(self.edges()))\r\n```\r\n\r\nSince nodes and edges are already inherently hashable.\r\n\r\nThis would ignore changes to node attributes, but given that node attributes need not be hashable, this is to be expected. Users can create their own custom hash functions in these cases, and perhaps a user warning could be raised as well."},"comment":{"url":"https://api.github.com/repos/networkx/networkx/issues/comments/418591366","html_url":"https://github.com/networkx/networkx/issues/3133#issuecomment-418591366","issue_url":"https://api.github.com/repos/networkx/networkx/issues/3133","id":418591366,"node_id":"MDEyOklzc3VlQ29tbWVudDQxODU5MTM2Ng==","user":{"login":"ryanpeach","id":14838729,"node_id":"MDQ6VXNlcjE0ODM4NzI5","avatar_url":"https://avatars1.githubusercontent.com/u/14838729?v=4","gravatar_id":"","url":"https://api.github.com/users/ryanpeach","html_url":"https://github.com/ryanpeach","followers_url":"https://api.github.com/users/ryanpeach/followers","following_url":"https://api.github.com/users/ryanpeach/following{/other_user}","gists_url":"https://api.github.com/users/ryanpeach/gists{/gist_id}","starred_url":"https://api.github.com/users/ryanpeach/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ryanpeach/subscriptions","organizations_url":"https://api.github.com/users/ryanpeach/orgs","repos_url":"https://api.github.com/users/ryanpeach/repos","events_url":"https://api.github.com/users/ryanpeach/events{/privacy}","received_events_url":"https://api.github.com/users/ryanpeach/received_events","type":"User","site_admin":false},"created_at":"2018-09-05T03:54:11Z","updated_at":"2018-09-05T03:54:11Z","author_association":"NONE","body":"I didnt know that, thanks for your answer, and I agree with it. I wonder if there is a way we can add something like my hashing function to maybe a recipes doc. It's very easy to subclass like you said, or even just to do a function injection."}}
{"actor":{"display_login":"ryanpeach"}}