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