#!/usr/bin/env python3
# Sample code from http://www.redblobgames.com/pathfinding/tower-defense/implementation.html
# This uses an internal reset
# Here's a sample graph node class:
class Node:
def __init__(self, name):
self.visited = False
self.name = name
self._neighbors = []
def neighbors(self):
return self._neighbors
def __repr__(self):
return "%s" % self.name
# and a sample graph:
A = Node("A")
B = Node("B")
C = Node("C")
D = Node("D")
E = Node("E")
A._neighbors = [B]
B._neighbors = [A, C]
C._neighbors = [D]
D._neighbors = [E]
E._neighbors = []
# Here's Breadth First Search from the article,
# modified to reset the "visited" field
from queue import Queue
def search_from(start, callback):
open = Queue()
open.put(start)
start.visited = True
visited_nodes = [start]
while not open.empty():
current = open.get()
callback(current)
for next in current.neighbors():
if not next.visited:
next.visited = True
visited_nodes.append(next)
open.put(next)
# Reset "visited" for the next time we want to run search
for node in visited_nodes:
node.visited = False
results = []
search_from(A, results.append)
print("First search from A: ", results)
results = []
search_from(A, results.append)
print("Second search from A: ", results) # succeeds, unlike sample-1.py