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 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))

				result.set_vertex_value (str(N), result.get_vertex_value(v2)+1)

			else:

				# Set start node shape to be a double circle

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

				result.set_vertex_value (str(N), 0) # set depth

				firsttime = False

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

			# Check if we've reached the goal

			if N in self.__goal_nodes:

				print '%s nodes created' % (len(OPEN) + len(CLOSED))

				print 'searched to depth: %s' % result.get_vertex_value (str(N))

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

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

				return 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:

				return 'FAILURE'

		return 'FAILURE'

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

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)

	goal = get_nth_child (start, 10)

	s = PuzzleSearch (start, (goal, ))

	result = s.search (add_bfs, 1000)

	if result != 'FAILURE':

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

	else:

		print result

if __name__ == '__main__':

	main ()