#!/usr/bin/env python3
# Sample code from http://www.redblobgames.com/pathfinding/tower-defense/implementation.html
# 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 = []
ALL_NODES = [A, B, C, D, E]
# Here's Breadth First Search from the article:
# modified to reset "visited" before running
from queue import Queue
def search_from(start, callback):
open = Queue()
open.put(start)
for node in ALL_NODES:
node.visited = False
start.visited = True
while not open.empty():
current = open.get()
callback(current)
for next in current.neighbors():
if not next.visited:
next.visited = True
open.put(next)
results = []
search_from(A, results.append)
print("First search from A: ", results)
results = []
search_from(A, results.append)
print("Second search from A: ", results)