Modify iterable while iteration

[polarkernel]

It is well known that modifying an iterable during iteration can lead to errors. For some structures, such as dictionaries, Python can even throw a RuntimeError: dictionary changed size during iteration exception when this case is detected.

During my development of StreetGenerator I found several cases where this kind of problem occurs. The iterable in my case is the waymap, a graph. Note that in principle it does not matter whether waymap is implemented as a graph or not, its basic logical structure is a graph, a network of intersections and streets.

I would like to describe the problem using an example case. It is not primarily important to solve this exact single case. Rather, I like to find a basic solution on how computer science solves such a problem, because there are several issues of the same kind in my development.

waymap stores streets in its edges and intersections in its nodes as data objects. Nodes and edges are containers for these objects. It is possible to modify them without altering the structure of the underlying graph. In my example, the polygon area of an intersection is constructed from the streets that leave the intersection node. The attribute area of the intersection object, stored in the node at location, is modified in an iteration over all nodes:

        for location, intersection in self.waymap.iterNodes():
            inStreets, outStreets = self.waymap.getInOutSections(location)  # streets leaving the node at location
            intersection.update(inStreets, outStreets)  # intersection is the data object stored in the node

            shortWays = intersection.cleanShortWays()   # some way are too short to build an intersection
            if shortWays:
                # remove them from self.waymap  <--- Problem!!

            intersection.createArea()

The Intersection class has a method cleanShortWays() that is able to identify ways that are too short to form an intersection. Let us not discuss here what this means exactly, and just consider them as "bad ways". Currently, they are set as invalid, but in the end they should be removed from the graph.

However, streets have two ends, and it is unknown whether the intersection area at the other end of the bad way has already been processed or not. If so, it will contain a bad section and a dangling connector leading to nowhere. Then the intersection must be processed again without the bad way. This can lead to a situation where a previously bad way of this intersection is no longer bad, has to be inserted again, and another intersection has to be modified. The problem may spread across the graph.

Removing this bad way is modifying the iterable waymap during iteration. How does one solve that?

[vvoovv]

Removing this bad way is modifying the iterable waymap during iteration. How does one solve that?

How about this pattern

itemsToChange = []

for location, intersection in self.waymap.iterNodes():
    ...
    itemsToChange.append(item)
    ...

for item in itemsToChange:
    self.waymap.change(item)