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