Subversion Repositories programming

#!/usr/bin/env python

__author__    = "Ira W. Snyder (devel@irasnyder.com)"

__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"

__license__   = "GNU GPL v2 (or, at your option, any later version)"

# 1) Put the start node N0 on OPEN. Create G with just this node

# 2) Create the list CLOSED which is empty

#

# LOOP:

#

# 3) If OPEN is empty, exit with FAILURE

# 4) Select the first node from OPEN, put it on CLOSED. Call this N

# 5) If N is a goal node, exit successfully with the solution in G

# 6) Generate M from the children of N

# 7) Add anything not in M not in (CLOSED union OPEN) to OPEN

# 8) Reorder OPEN appropriately

# 9) goto LOOP

from PuzzlePiece import PuzzlePiece

from Graph import Graph

import yapgvb

class SearchResult (object):

	"""Class to store a search result"""

	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):

		self.completed = completed

		self.status = status

		self.depth_reached = depth_reached

		self.nodes_created = nodes_created

		self.result_graph = result_graph

		self.search_name = None

	def __repr__ (self):

		"""Turn myself into a string"""

		answer =  '%s -- Reached Depth: %s -- Nodes Created: %s' % \

			(self.status, self.depth_reached, self.nodes_created)

		if self.search_name:

			answer = self.search_name + '\n' + answer

		return answer

	def set_search_name (self, name):

		self.search_name = name

class PuzzleSearch (object):

	"""Implements a graph search"""

	def __init__ (self, start_node, goal_nodes):

		"""Constructor.

		start_node: the node to start at (must have a get_children() function)

		goal_nodes: a list of nodes to end at"""

		self.__start_node = start_node

		self.__goal_nodes = goal_nodes

		self.__ordering_func = list.sort

	def set_ordering_func (self, func):

		"""Set the ordering function to use."""

		self.__ordering_func = func

	def __find_nearest_child (self, children, already_visited):

		"""Find the child that we came from. This necessitates that

		the list already_visited be sorted in the order of nodes visited"""

		for n in reversed(already_visited):

			if n in children:

				return n

		# This should never happen

		raise ValueError

	def search (self, add_function, MAX_NODES_CREATED=100):

		# Create the result graph

		result = Graph ()

		firsttime = True

		counter = 0

		OPEN = [self.__start_node]

		CLOSED = []

		while OPEN:

			N = OPEN.pop(0)

			CLOSED.append (N)

			# Find all possible next paths

			M = N.get_children()

			###############################################################

			# Add the current place to the result graph

			result.add_vertex (str(N))

			if not firsttime:

				v1 = str(N)

				v2 = str(self.__find_nearest_child (M, CLOSED))

				result.add_edge (v1, v2)

				result.set_edge_color (v1, v2, yapgvb.colors.red)

				result.set_edge_label (v1, v2, str(counter))

			else:

				# Set start node shape to be a double circle

				result.set_vertex_shape (str(N), yapgvb.shapes.doublecircle)

				firsttime = False

			###############################################################

			# Check if we've reached the goal

			if N in self.__goal_nodes:

				# Set the goal node's shape to be a diamond

				result.set_vertex_shape (str(N), yapgvb.shapes.diamond)

				# Create the return result

				search_result = SearchResult (completed=True,

							status='Success',

							depth_reached=N.depth,

							nodes_created=len(OPEN)+len(CLOSED),

							result_graph=result)

				return search_result

			# Add the children of N (aka M) to OPEN

			OPEN = add_function (M, OPEN, CLOSED)

			counter += 1

			# Check to make sure we don't loop for too long

			if (len(OPEN) + len(CLOSED)) > MAX_NODES_CREATED:

				search_result = SearchResult (completed=False,

							status='FAILURE -- Max nodes exceeded',

							depth_reached=N.depth,

							nodes_created=len(OPEN)+len(CLOSED),

							result_graph=None)

				return search_result

		search_result = SearchResult (completed=False,

					status='FAILURE -- goal not found',

					depth_reached=N.depth,

					nodes_created=len(OPEN)+len(CLOSED),

					result_graph=None)

		return search_result

################################################################################

### Specific Search Algorithms

################################################################################

def add_bfs (M, OPEN, CLOSED):

	for node in M:

		if (node not in OPEN) and (node not in CLOSED):

			OPEN.append (node)

	return OPEN

def add_dfs (M, OPEN, CLOSED):

	for node in M:

		if (node not in OPEN) and (node not in CLOSED):

			OPEN.insert (0, node) # insert node at beginning

	return OPEN

def best_first_generic (M, OPEN, CLOSED, heuristic_func):

	newopen = []

	for node in M:

		if (node not in OPEN) and (node not in CLOSED):

			OPEN.append (node)

	for node in OPEN:

		heuristic = heuristic_func (node)

		newopen.append ((heuristic, node))

	newopen.sort ()

	return [n[1] for n in newopen]

def bfs_oop (M, OPEN, CLOSED):

	return best_first_generic (M, OPEN, CLOSED, lambda x: x.num_out_of_place ())

def bfs_dfc (M, OPEN, CLOSED):

	return best_first_generic (M, OPEN, CLOSED, lambda x: x.total_distance_from_correct ())

def astar_bfs (M, OPEN, CLOSED):

	return best_first_generic (M, OPEN, CLOSED, lambda x: x.depth)

def astar_oop (M, OPEN, CLOSED):

	return best_first_generic (M, OPEN, CLOSED,

			lambda x: x.depth + x.num_out_of_place ())

def astar_dfc (M, OPEN, CLOSED):

	return best_first_generic (M, OPEN, CLOSED,

			lambda x: x.depth + x.total_distance_from_correct ())

from Graph import Graph

from DrawGraph import DrawGraph

import random

def get_nth_child (start, n):

	child = start

	for i in xrange(n):

		child = random.choice(child.get_children())

	return child

def main ():

	initial = [1, 2, 3, 4, 'E', 5, 6, 7, 8]

	start = PuzzlePiece (initial) # temporary use!

	goal = get_nth_child (start, 20)

	start = PuzzlePiece (initial, 0, goal)

	s = PuzzleSearch (start, (goal, ))

	# Run some tests

	result = s.search (add_dfs, 1000)

	result.set_search_name ('Depth First Search')

	print result

	print

	result = s.search (add_bfs, 1000)

	result.set_search_name ('Breadth First Search: normal')

	print result

	print

	result = s.search (bfs_oop, 1000)

	result.set_search_name ('Best First Search: Out-of-place')

	print result

	print

	result = s.search (astar_bfs, 1000)

	result.set_search_name ('A*-search: Breadth-first-search')

	print result

	print

	result = s.search (astar_oop, 1000)

	result.set_search_name ('A*-search: Out-of-place')

	print result

	print

	result = s.search (astar_dfc, 1000)

	result.set_search_name ('A*-search: Distance-from-correct')

	print result

	print

	if result.result_graph != None:

		DrawGraph ('result', result.result_graph).render_graph ('res.svg', yapgvb.engines.dot)

	else:

		print 'Failed to render graph'

if __name__ == '__main__':

	main ()