Repository: projectmesa/mesa

Issue:
Dynamic Discrete Spaces
Currently, all DiscreteSpace subclasses rely on `@cache` and `@cached_property` for neighborhood-related functionality. This is critical for performance. However, if you want to represent a dynamically changing discrete space (e.g., a dynamic network), this is currently not possible. 

It seems that `functools` offers a `clear_cache` function that can be called on anything decorated with a caching decorator. This means that it is possible to retain the performance benefits of caching while also being able to clear it on specific parts of the DiscreteSpace. 

Something like the following is roughly what would be needed. Note that this is not tested and just quickly put together based on some docs.

```python

class DynamicNetwork(Network):
	
	def add_cell(cell:Cell):
		self.G.add_node(cell.coordinate)
		self._cells[cell.coordinate] = cell.coordinate

	def add_edge(cell1:Cell, cell2:Cell):
		self.G.add_edge(cell1.coordinate, cell2.coordinate)

		for cell in [cell1, cell2]:
			cell.get_neighborhood.cache_clear()
			cell.neigbhoorhood.cache_clear()
			cell._neighborhood.cache_clear()
			self._connect_single_cell(cell)

	def remove_cell(cell:Cell):
		neigbors = cell.neighborhood

		self.G.remove_node(cell.coordinate)
		
		# iterate over all neighbors
		for cell in neighbors:
			cell.get_neighborhood.cache_clear()
			cell.neigbhoorhood.cache_clear()
			cell._neighborhood.cache_clear()
			self._connect_single_cell(cell)


	def remove_edge(cell1:Cell, cell2:Cell):
		self.G.remove_edge(cell1.coordinate, cell2.coordinate)

		for cell in [cell1, cell2]:
			cell.get_neighborhood.cache_clear()
			cell.neigbhoorhood.cache_clear()
			cell._neighborhood.cache_clear()
			self._connect_single_cell(cell)
```

Hints from issue comments:
@Sahil-Chhoker: Can I ask how does caching prevent the dynamic nature of these spaces?@quaquel: The neighborhood of a given cell is cached. If you next change the neigborhood by either removing or adding a cell to it, you have invalidated the cache.@Sahil-Chhoker: Does the cache not update with the new neighborhood?@quaquel: no caching takes whatever was the return of the first ever time the function was called.@Sahil-Chhoker: Would it be beneficial in any way that we build our own caching function that automatically updates according to the necessary neighbor or is it too time consuming (performance wise)?@quaquel: Why implement something ourselves that is well covered by an existing library? Also, how would any cache know it needs to be updated? The `cache_clear` function is provided explicitly to cover our use case. 


Separately, thinking about the issue a bit more, my hunch is to implement the add_cell, remove_cell, add_edge and remove_edge (probably these need to be renamed to something a bit more generic) at the level of DiscreteSpace. In this way, all subclasses are automatically dynamic.

For example, a while ago someone wanted to add walls to a space. With a `remove_edge` method this becomes trivial to do. @Sahil-Chhoker: Thanks for this discussion, I think I kind of get it now!@quaquel: I opened a PR: #2755 so let's move further discussion to there. 

Solution patch:
diff --git a/mesa/discrete_space/cell.py b/mesa/discrete_space/cell.py
index 2b1a42d004d..f8621ead808 100644
--- a/mesa/discrete_space/cell.py
+++ b/mesa/discrete_space/cell.py
@@ -84,6 +84,7 @@ def connect(self, other: Cell, key: Coordinate | None = None) -> None:
         """
         if key is None:
             key = other.coordinate
+        self._clear_cache()
         self.connections[key] = other
 
     def disconnect(self, other: Cell) -> None:
@@ -96,6 +97,7 @@ def disconnect(self, other: Cell) -> None:
         keys_to_remove = [k for k, v in self.connections.items() if v == other]
         for key in keys_to_remove:
             del self.connections[key]
+        self._clear_cache()
 
     def add_agent(self, agent: CellAgent) -> None:
         """Adds an agent to the cell.
@@ -210,3 +212,15 @@ def __getstate__(self):
             "connections"
         ] = {}  # replace this with empty connections to avoid infinite recursion error in pickle/deepcopy
         return state
+
+    def _clear_cache(self):
+        """Helper function to clear local cache."""
+        try:
+            self.__dict__.pop(
+                "neighborhood"
+            )  # cached properties are stored in __dict__, see functools.cached_property docs
+        except KeyError:
+            pass  # cache is not set
+        else:
+            self.get_neighborhood.cache_clear()
+            self._neighborhood.cache_clear()
diff --git a/mesa/discrete_space/discrete_space.py b/mesa/discrete_space/discrete_space.py
index 4a71673cd31..f480ff15fbe 100644
--- a/mesa/discrete_space/discrete_space.py
+++ b/mesa/discrete_space/discrete_space.py
@@ -85,6 +85,68 @@ def agents(self) -> AgentSet:
     def _connect_cells(self): ...
     def _connect_single_cell(self, cell: T): ...
 
+    def add_cell(self, cell: T):
+        """Add a cell to the space.
+
+        Args:
+            cell: cell to add
+
+        Note:
+            Discrete spaces rely on caching neighborhood relations for speedups. Adding or removing cells and
+            connections at runtime is possible. However, only the caches of cells directly affected will be cleared. So
+            if you rely on getting neighborhoods of cells with a radius higher than 1, these might not be cleared
+            correctly if you are adding or removing cells and connections at runtime.
+
+        """
+        self.__dict__.pop("all_cells", None)
+        self._cells[cell.coordinate] = cell
+
+    def remove_cell(self, cell: T):
+        """Remove a cell from the space.
+
+        Note:
+            Discrete spaces rely on caching neighborhood relations for speedups. Adding or removing cells and
+            connections at runtime is possible. However, only the caches of cells directly affected will be cleared. So
+            if you rely on getting neighborhoods of cells with a radius higher than 1, these might not be cleared
+            correctly if you are adding or removing cells and connections at runtime.
+
+
+        """
+        neighbors = cell.neighborhood
+        self._cells.pop(cell.coordinate)
+        self.__dict__.pop("all_cells", None)
+
+        # iterate over all neighbors
+        for neighbor in neighbors.cells:
+            neighbor.disconnect(cell)
+            cell.disconnect(neighbor)
+
+    def add_connection(self, cell1: T, cell2: T):
+        """Add a connection between the two cells.
+
+        Note:
+            Discrete spaces rely on caching neighborhood relations for speedups. Adding or removing cells and
+            connections at runtime is possible. However, only the caches of cells directly affected will be cleared. So
+            if you rely on getting neighborhoods of cells with a radius higher than 1, these might not be cleared
+            correctly if you are adding or removing cells and connections at runtime.
+
+        """
+        cell1.connect(cell2)
+        cell2.connect(cell1)
+
+    def remove_connection(self, cell1: T, cell2: T):
+        """Remove a connection between the two cells.
+
+        Note:
+            Discrete spaces rely on caching neighborhood relations for speedups. Adding or removing cells and
+            connections at runtime is possible. However, only the caches of cells directly affected will be cleared. So
+            if you rely on getting neighborhoods of cells with a radius higher than 1, these might not be cleared
+            correctly if you are adding or removing cells and connections at runtime.
+
+        """
+        cell1.disconnect(cell2)
+        cell2.disconnect(cell1)
+
     @cached_property
     def all_cells(self):
         """Return all cells in space."""
diff --git a/mesa/discrete_space/network.py b/mesa/discrete_space/network.py
index 7f692cd2eaf..3fc0bc2ff14 100644
--- a/mesa/discrete_space/network.py
+++ b/mesa/discrete_space/network.py
@@ -55,3 +55,23 @@ def _connect_cells(self) -> None:
     def _connect_single_cell(self, cell: Cell):
         for node_id in self.G.neighbors(cell.coordinate):
             cell.connect(self._cells[node_id], node_id)
+
+    def add_cell(self, cell: Cell):
+        """Add a cell to the space."""
+        super().add_cell(cell)
+        self.G.add_node(cell.coordinate)
+
+    def remove_cell(self, cell: Cell):
+        """Remove a cell from the space."""
+        super().remove_cell(cell)
+        self.G.remove_node(cell.coordinate)
+
+    def add_connection(self, cell1: Cell, cell2: Cell):
+        """Add a connection between the two cells."""
+        super().add_connection(cell1, cell2)
+        self.G.add_edge(cell1.coordinate, cell2.coordinate)
+
+    def remove_connection(self, cell1: Cell, cell2: Cell):
+        """Remove a connection between the two cells."""
+        super().remove_connection(cell1, cell2)
+        self.G.remove_edge(cell1.coordinate, cell2.coordinate)


Test patch:
diff --git a/tests/test_discrete_space.py b/tests/test_discrete_space.py
index 42e61d14780..28919dcc333 100644
--- a/tests/test_discrete_space.py
+++ b/tests/test_discrete_space.py
@@ -315,6 +315,42 @@ def test_orthogonal_grid_moore_1d():
         assert connection.coordinate in {(1,), (9,)}
 
 
+def test_dynamic_modifications_to_space():
+    """Test dynamic modifications to DiscreteSpace."""
+    grid = OrthogonalMooreGrid(
+        (5, 5), torus=False, capacity=1, random=random.Random(42)
+    )
+
+    cells = grid._cells
+
+    # test remove_connection
+    cell1 = cells[(2, 0)]
+    cell2 = cells[(3, 0)]
+    grid.remove_connection(cell1, cell2)
+
+    assert cell2 not in cell1.neighborhood
+    assert cell1 not in cell2.neighborhood
+
+    # test add connection
+    grid.add_connection(cell1, cell2)
+    assert cell1 in cell2.neighborhood
+    assert cell2 in cell1.neighborhood
+
+    # test remove cell
+    neighbors = cell1.neighborhood
+    grid.remove_cell(cell1)
+    for neighbor in neighbors:
+        assert cell1 not in neighbor.neighborhood
+
+    # test add_cells
+    grid.add_cell(cell1)
+    for neighbor in neighbors:
+        grid.add_connection(cell1, neighbor)
+
+    for neighbor in neighbors:
+        assert cell1 in neighbor.neighborhood
+
+
 def test_cell_neighborhood():
     """Test neighborhood method of cell in different GridSpaces."""
     # orthogonal grid
@@ -451,6 +487,23 @@ def test_networkgrid():
 
     pickle.loads(pickle.dumps(grid))  # noqa: S301
 
+    cell = Cell(10)  # n = 10, so 10 + 1
+    grid.add_cell(cell)
+    grid.add_connection(cell, grid._cells[0])
+    assert cell in grid._cells[0].neighborhood
+    assert grid._cells[0] in cell.neighborhood
+
+    grid.remove_connection(cell, grid._cells[0])
+    assert cell not in grid._cells[0].neighborhood
+    assert grid._cells[0] not in cell.neighborhood
+
+    cell = Cell(10)  # n = 10, so 10 + 1
+    grid.add_cell(cell)
+    grid.add_connection(cell, grid._cells[0])
+    grid.remove_cell(cell)  # this also removes all connections
+    assert cell not in grid._cells[0].neighborhood
+    assert grid._cells[0] not in cell.neighborhood
+
 
 def test_voronoigrid():
     """Test VoronoiGrid."""