Example 18-18. PP4E\Dstruct\Classics\gsearch2.py
"graph search, using paths stack instead of recursion"
def search(start, goal, graph):
solns = generate(([start], []), goal, graph)
solns.sort(key=lambda x: len(x))
return solns
def generate(paths, goal, graph): # returns solns list
solns = [] # use a tuple-stack
while paths:
front, paths = paths # pop the top path
state = front[-1]
if state == goal:
solns.append(front) # goal on this path
else:
for arc in graph[state]: # add all extensions
if arc not in front:
paths = (front + [arc]), paths
return solns
if name == 'main':
import gtestfunc
gtestfunc.tests(search)
To avoid cycles, both searchers keep track of nodes visited along a path. If an extension
is already on the current path, it is a loop. The resulting solutions list is sorted by
increasing lengths using the list sort method and its optional key value transform ar-
gument. To test the searcher modules, simply run them; their self-test code calls the
canned search test in the gtestfunc module:
C:\...\PP4E\Dstruct\Classics> python gsearch1.py
[['E', 'C', 'D'], ['E', 'G', 'A', 'B', 'C', 'D']]
AG [['A', 'G'], ['A', 'E', 'G'], ['A', 'B', 'C', 'E', 'G']]
GF [['G', 'A', 'E', 'F'], ['G', 'A', 'B', 'C', 'D', 'F'],
['G', 'A', 'B', 'C', 'E', 'F'], ['G', 'A', 'E', 'C', 'D', 'F']]
BA [['B', 'C', 'E', 'G', 'A']]
DA []C:\...\PP4E\Dstruct\Classics> python gsearch2.py
[['E', 'C', 'D'], ['E', 'G', 'A', 'B', 'C', 'D']]
AG [['A', 'G'], ['A', 'E', 'G'], ['A', 'B', 'C', 'E', 'G']]
GF [['G', 'A', 'E', 'F'], ['G', 'A', 'E', 'C', 'D', 'F'],
['G', 'A', 'B', 'C', 'E', 'F'], ['G', 'A', 'B', 'C', 'D', 'F']]
BA [['B', 'C', 'E', 'G', 'A']]
DA []This output shows lists of possible paths through the test graph; I added two line breaks
to make it more readable (Python pprint pretty-printer module might help with read-
ability here as well). Notice that both searchers find the same paths in all tests, but the
order in which they find those solutions may differ. The gsearch2 order depends on
1392 | Chapter 18: Data Structures