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 Graph import Graph
import yapgvb

class GraphSearch (object):
        """Implements a graph search"""

        def __init__ (self, full_graph, start_node, goal_nodes):
                """Constructor.
                full_graph: a Graph representing all the knowledge
                start_node: the node to start at (must be in full_graph)
                goal_nodes: a list of nodes to end at"""

                self.__kb = full_graph
                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):

                # Create the result graph
                result = Graph ()
                #result.add_vertex (self.__start_node)
                firsttime = True
                counter = 0

                OPEN = [self.__start_node]
                CLOSED = []

                while OPEN:
                        N = OPEN.pop(0)
                        CLOSED.append (N)

                        # Find all possible next paths
                        M = self.__kb.get_children (N)

                        # Add the current place to the result graph
                        result.add_vertex (N)
                        if not firsttime:
                                v1 = N
                                v2 = 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))

                                self.__kb.set_edge_color (v1, v2, 'red')
                                self.__kb.set_edge_label (v1, v2, str(counter))
                        else:
                                firsttime = False

                        # Check if we've reached the goal
                        if N in self.__goal_nodes:
                                return self.__kb #result

                        #for node in M:
                        #       if (node not in OPEN) and (node not in CLOSED):
                        #               OPEN.append (node)

                        # Sort OPEN appropriately
                        # NOTE: no sort algorithm is BFS
                        #self.__ordering_func (OPEN)

                        # FIXME: maybe take the "for node in M" loop and
                        # FIXME: combine it with the ordering function into
                        # FIXME: it's own function that chooses how to add
                        # FIXME: the nodes from M into OPEN
                        #
                        # FIXME: prototype might be: func (M, OPEN, CLOSED)
                        #add_dfs (M, OPEN, CLOSED)
                        OPEN = add_bfs (M, OPEN, CLOSED)

                        counter += 1

                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

def main ():
        #vertices = [0, 1, 2, 3, 'goal']
        #edges = ( [0,1], [1,2], [2,3], [3,'goal'] )

        #vertices = [0, 1, 2, 3, 'goal']
        #edges = ( [0,1], [0,2], [2,3], [2,'goal'] )

        vertices = [0, 1, 2, 3, 5, 6, 7, 8, 'g1', 'g2']
        edges = ( [0,1], [0,2], [0,8], [2,3], [2,'g2'], [1,5], [1,6], [6,7], [7,'g1'] )

        g = Graph (vertices, edges)
        s = GraphSearch (g, 0, ['g1', 'g2'])
        result = s.search ()

        if result != 'FAILURE':
                DrawGraph ('result', result).render_graph ('res.svg') #result.vertices, result.edges.keys ()).render_graph ('res.svg')


if __name__ == '__main__':
        main ()