¿Hay un nombre para el patrón de diseño "cosas para manejar"?

Question

Hay un patrón de diseño que uso de vez en cuando, y no sé cómo se llama. Tal vez tiene un nombre y alguien aquí lo sabe?

Es algo que uso cuando quiero atravesar una estructura similar a un árbol y hacer alguna acción en todos sus nodos. Es algo como esto:

nodes_to_handle = [root_node] 
while nodes_to_handle: 
    node = nodes_to_handle.pop() 
    # handle node 
    nodes_to_handle += node.get_neighbors() 

Tenga en cuenta que la estructura no tiene que ser un árbol; por ejemplo, este patrón se puede usar para hacer un relleno de inundación en una matriz.

Entonces, ¿hay un nombre aceptado para este patrón de diseño?

Answer 1

Creo que lo que obtienes es un patrón más general que el recorrido en profundidad: la lista de fronteras. Una lista de frontera es una lista (ordenada o no) de elementos que aún requieren procesamiento; el algoritmo continúa eliminando elementos y procesándolos hasta que la lista esté vacía o se cumplan algunos otros criterios de terminación.

Mi ejemplo favorito de este patrón es el algoritmo de dijkstra. En Dijkstra, la lista de fronteras es una cola o pila de prioridad, y el elemento de menor valor se saca del montón cada iteración.

Answer 2

Esto se parece al algoritmo de profundidad en primer paso. (Puesto que el pop la lista desde el final)

Se puede implementar de forma genérica en algunas maneras diferentes:

• Usando un iterador que atraviesa el árbol (la forma preferida)
• Utilizando una función de recorrido (como el suyo) con una devolución de llamada (para el código #handle node).
  • Fuera de la clase nodo
  • Dentro de la clase nodo
• ...

Editar: No mirar el código correctamente. :)

Answer 3

Esto es depth-first graph traversal. Es un algorithm, no un design pattern. (Del comentario de Jochen Ritzel.)