how and when extensions are added to its path’s stack; try tracing through the outputs
and code to see how.
Moving Graphs to Classes
Using dictionaries to represent graphs is efficient: connected nodes are located by a fast
hashing operation. But depending on the application, other representations might
make more sense. For instance, classes can be used to model nodes in a network, too,
much like the binary tree example earlier. As classes, nodes may contain content useful
for more sophisticated searches. They may also participate in inheritance hierarchies,
to acquire additional behaviors. To illustrate the basic idea, Example 18-19 shows an
alternative coding for our graph searcher; its algorithm is closest to gsearch1.
Example 18-19. PP4E\Dstruct\Classics\graph.py
"build graph with objects that know how to search"
class Graph:
def init(self, label, extra=None):
self.name = label # nodes=inst objects
self.data = extra # graph=linked objs
self.arcs = []
def repr(self):
return self.name
def search(self, goal):
Graph.solns = []
self.generate([self], goal)
Graph.solns.sort(key=lambda x: len(x))
return Graph.solns
def generate(self, path, goal):
if self == goal: # class == tests addr
Graph.solns.append(path) # or self.solns: same
else:
for arc in self.arcs:
if arc not in path:
arc.generate(path + [arc], goal)
In this version, graphs are represented as a network of embedded class instance objects.
Each node in the graph contains a list of the node objects it leads to (arcs), which it
knows how to search. The generate method walks through the objects in the graph.
But this time, links are directly available on each node’s arcs list; there is no need to
index (or pass) a dictionary to find linked objects. The search is effectively spread across
the graph’s linked objects.
To test, the module in Example 18-20 builds the test graph again, this time using linked
instances of the Graph class. Notice the use of exec in this code: it executes dynamically
Graph Searching| 1393