root-11/graph-theory

The lru cache on is_connected causes invalid results if new edges are added

Closed this issue · 5 comments

Adding new edges has to clear the cache, otherwise you get:

>>> from graph import Graph
>>> a = Graph()
>>> a.is_connected(1, 2)
False
>>> a.add_edge(1, 2)
>>> a.is_connected(1, 2)
False

Also it's not documented that is_connected has an lru cache on it, so one would never know that the cache needs to be flushed unless examining the internal code.

+1. Shall we remove it? Or declare it?

Probably remove it. If someone wants to cache results, they can always do it externally.

phaselines requires some form of caching to work effectively. Proposal is in branch lru_cache. Please review.

I added some comments on the branch.