Subversion Repositories programming

Rev

Rev 383 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 383 Rev 387
Line 15... Line 15...
15 
# 6) Generate M from the children of N
 15 
# 6) Generate M from the children of N
16 
# 7) Add anything not in M not in (CLOSED union OPEN) to OPEN
 16 
# 7) Add anything not in M not in (CLOSED union OPEN) to OPEN
17 
# 8) Reorder OPEN appropriately
 17 
# 8) Reorder OPEN appropriately
18 
# 9) goto LOOP
 18 
# 9) goto LOOP
19 
 
 19 
 
- 
 
 20 
from PuzzlePiece import PuzzlePiece
20 
from Graph import Graph
 21 
from Graph import Graph
21 
import yapgvb
 22 
import yapgvb
22 
 
 23 
 
23 
class GraphSearch (object):
 24 
class PuzzleSearch (object):
24 
	"""Implements a graph search"""
 25 
	"""Implements a graph search"""
25 
 
 26 
 
26 
	def __init__ (self, full_graph, start_node, goal_nodes):
 27 
	def __init__ (self, start_node, goal_nodes):
27 
		"""Constructor.
 28 
		"""Constructor.
28 
		full_graph: a Graph representing all the knowledge
 - 
 
29 
		start_node: the node to start at (must be in full_graph)
 29 
		start_node: the node to start at (must have a get_children() function)
30 
		goal_nodes: a list of nodes to end at"""
 30 
		goal_nodes: a list of nodes to end at"""
31 
 
 31 
 
32 
		self.__kb = full_graph
 - 
 
33 
		self.__start_node = start_node
 32 
		self.__start_node = start_node
34 
		self.__goal_nodes = goal_nodes
 33 
		self.__goal_nodes = goal_nodes
35 
		self.__ordering_func = list.sort
 34 
		self.__ordering_func = list.sort
36 
 
 35 
 
37 
	def set_ordering_func (self, func):
 36 
	def set_ordering_func (self, func):
Line 50... Line 49...
50 
 
 49 
 
51 
	def search (self):
 50 
	def search (self):
52 
 
 51 
 
53 
		# Create the result graph
 52 
		# Create the result graph
54 
		result = Graph ()
 53 
		result = Graph ()
55 
		#result.add_vertex (self.__start_node)
 - 
 
56 
		firsttime = True
 54 
		firsttime = True
57 
		counter = 0
 55 
		counter = 0
58 
 
 56 
 
59 
		OPEN = [self.__start_node]
 57 
		OPEN = [self.__start_node]
60 
		CLOSED = []
 58 
		CLOSED = []
Line 62... Line 60...
62 
		while OPEN:
 60 
		while OPEN:
63 
			N = OPEN.pop(0)
 61 
			N = OPEN.pop(0)
64 
			CLOSED.append (N)
 62 
			CLOSED.append (N)
65 
 
 63 
 
66 
			# Find all possible next paths
 64 
			# Find all possible next paths
67 
			M = self.__kb.get_children (N)
 65 
			M = N.get_children()
68 
 
 66 
 
- 
 
 67 
			###############################################################
69 
			# Add the current place to the result graph
 68 
			# Add the current place to the result graph
70 
			result.add_vertex (N)
 69 
			result.add_vertex (str(N))
71 
			if not firsttime:
 70 
			if not firsttime:
72 
				v1 = N
 71 
				v1 = str(N)
73 
				v2 = self.__find_nearest_child (M, CLOSED)
 72 
				v2 = str(self.__find_nearest_child (M, CLOSED))
74 
 
 73 
 
75 
				result.add_edge (v1, v2)
 74 
				result.add_edge (v1, v2)
76 
				result.set_edge_color (v1, v2, yapgvb.colors.red)
 75 
				result.set_edge_color (v1, v2, yapgvb.colors.red)
77 
				result.set_edge_label (v1, v2, str(counter))
 76 
				result.set_edge_label (v1, v2, str(counter))
78 
 
 77 
 
79 
				self.__kb.set_edge_color (v1, v2, 'red')
 - 
 
80 
				self.__kb.set_edge_label (v1, v2, str(counter))
 - 
 
81 
			else:
 78 
			else:
82 
				firsttime = False
 79 
				firsttime = False
- 
 
 80 
			###############################################################
83 
 
 81 
 
84 
			# Check if we've reached the goal
 82 
			# Check if we've reached the goal
85 
			if N in self.__goal_nodes:
 83 
			if N in self.__goal_nodes:
86 
				return self.__kb #result
 84 
				return result
87 
 
 85 
 
88 
			#for node in M:
 - 
 
89 
			#	if (node not in OPEN) and (node not in CLOSED):
 - 
 
90 
			#		OPEN.append (node)
 - 
 
91 
 
 - 
 
92 
			# Sort OPEN appropriately
 - 
 
93 
			# NOTE: no sort algorithm is BFS
 - 
 
94 
			#self.__ordering_func (OPEN)
 - 
 
95 
 
 - 
 
96 
			# FIXME: maybe take the "for node in M" loop and
 - 
 
97 
			# FIXME: combine it with the ordering function into
 - 
 
98 
			# FIXME: it's own function that chooses how to add
 - 
 
99 
			# FIXME: the nodes from M into OPEN
 - 
 
100 
			#
 86 
			# FIXME
101 
			# FIXME: prototype might be: func (M, OPEN, CLOSED)
 - 
 
102 
			#add_dfs (M, OPEN, CLOSED)
 - 
 
103 
			OPEN = add_bfs (M, OPEN, CLOSED)
 87 
			OPEN = add_bfs (M, OPEN, CLOSED)
104 
 
 88 
 
105 
			counter += 1
 89 
			counter += 1
106 
 
 90 
 
107 
		return 'FAILURE'
 91 
		return 'FAILURE'
Line 121... Line 105...
121 
	return OPEN
 105 
	return OPEN
122 
 
 106 
 
123 
 
 107 
 
124 
from Graph import Graph
 108 
from Graph import Graph
125 
from DrawGraph import DrawGraph
 109 
from DrawGraph import DrawGraph
- 
 
 110 
import random
126 
 
 111 
 
- 
 
 112 
def get_nth_child (start, n):
127 
def main ():
 113 
	child = start
128 
	#vertices = [0, 1, 2, 3, 'goal']
 114 
	for i in xrange(n):
129 
	#edges = ( [0,1], [1,2], [2,3], [3,'goal'] )
 115 
		child = random.choice(child.get_children())
- 
 
 116 
 
- 
 
 117 
	return child
130 
 
 118 
 
131 
	#vertices = [0, 1, 2, 3, 'goal']
 119 
def main ():
132 
	#edges = ( [0,1], [0,2], [2,3], [2,'goal'] )
 120 
	initial = [1, 2, 3, 4, 'E', 5, 6, 7, 8]
133 
 
 121 
 
134 
	vertices = [0, 1, 2, 3, 5, 6, 7, 8, 'g1', 'g2']
 122 
	start = PuzzlePiece (initial)
135 
	edges = ( [0,1], [0,2], [0,8], [2,3], [2,'g2'], [1,5], [1,6], [6,7], [7,'g1'] )
 123 
	goal = get_nth_child (start, 2)
136 
 
 124 
 
137 
	g = Graph (vertices, edges)
 - 
 
138 
	s = GraphSearch (g, 0, ['g1', 'g2'])
 125 
	s = PuzzleSearch (start, (goal, ))
139 
	result = s.search ()
 126 
	result = s.search ()
140 
 
 127 
 
141 
	if result != 'FAILURE':
 128 
	if result != 'FAILURE':
142 
		DrawGraph ('result', result).render_graph ('res.svg') #result.vertices, result.edges.keys ()).render_graph ('res.svg')
 129 
		DrawGraph ('result', result).render_graph ('res.svg', yapgvb.engines.dot)
143 
 
 130 
 
144 
 
 131 
 
145 
if __name__ == '__main__':
 132 
if __name__ == '__main__':
146 
	main ()
 133 
	main ()