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 PyCompat import * # fixes for school computers

from PuzzlePiece import PuzzlePiece
from Graph import Graph

if have_yapgvb():
        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

        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), str(counter), raw_obj=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:
                if have_yapgvb():
                        DrawGraph ('result', result.result_graph).render_graphviz ('res.svg', yapgvb.engines.dot)

                DrawGraph ('result', result.result_graph).render_stupid ('generated_by')
        else:
                print 'Failed to render graph'


if __name__ == '__main__':
        main ()