-
Notifications
You must be signed in to change notification settings - Fork 20
Description
If one graph had a edge added and then removed again, comparing it to an identical graph can return false. This occurs it the added and removed edge is outgoing from an node that had no outgoing edges before.
To reproduce
Python 3.10.0 (tags/v3.10.0:b494f59, Oct 4 2021, 19:00:18) [MSC v.1929 64 bit (AMD64)] on win32
>>> from graph import Graph
>>> g1 = Graph(from_list=[(1,2),(2,3)])
>>> g2 = g1.copy()
>>> g1 == g2
True
>>> g1.add_edge(3,1)
>>> g1.del_edge(3,1)
>>> g1 == g2
False
>>> g1.edges() == g2.edges()
True
>>> g1.nodes() == g2.nodes()
True
Cause
As far as I can tell, this bug occurs, because __eq__
compares the two graphs private edge variables _edges
instead of calling the public edge getter edges()
.
When an edge from an node, that did not have any outgoing edges before, is added and removed, that edges name remains as a key in the graph's internal edge variable _edges
. Two dictionaries are unequal if one has a key the other has not, even if all values are equal, thus the two graphs are unequal.
Other examples
Because copy()
uses the public edge getter edges()
this bug can lead to some very confusing behavior:
Python 3.10.0 (tags/v3.10.0:b494f59, Oct 4 2021, 19:00:18) [MSC v.1929 64 bit (AMD64)] on win32
>>> from graph import Graph
>>> g1 = Graph(from_list=[(1,2),(2,3)])
>>> g1.add_edge(3,1)
>>> g1.del_edge(3,1)
>>> g2 = g1.copy()
>>> g1 == g2
False
Additional information
I'm using version 2023.7.5 of graph-theory with Python 3.10 on windows.