search

root-11 / graph-theory

A simple graph library
MIT License
82 stars 19 forks source link

`__eq__` (equality) can return false for two identical graphs if an edge was added and removed in one of them #40

Closed Sappique closed 7 months ago

Sappique commented 8 months ago

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.

root-11 commented 8 months ago

A great catch @Sappique. I'm far away from my PC until the 12th of March, so depending on how urgent this issue is to you I see three options:

A) If you are confident to make a pull request, then you can propose a patch and @04t02 and I can review it. B) Perhaps @04t02 can help out in my absence? C) I patch the library promptly after returning from holiday shortly after the the 12th.

Which do you prefer?

Sappique commented 8 months ago

Sorry for the late replay @root-11.
I currently don't feel confident enough to fix the issue myself.

If someone does fix it I will be grateful, but I am currently able to use a workaround.

root-11 commented 7 months ago

New release pending workflow completion...

root-11 commented 7 months ago

Release 2023.6.7 available on pypi as: https://pypi.org/project/graph-theory/2023.7.6/