Entry 3496

	def graph_search(DigitProblem, fringe):
		"""A graph search algorithm, searching through a graph.
		The fringe is either a FIFO, LIFO, or Priority Queue.
		It stores expanded nodes in a dictionary.

		A graph search algorithm is used as a basic loop detection scheme,
		as it detects if a state has been expanded already.
		"""
		expanded = {}
		fringe.append(Node(DigitProblem.initial)) # Initiate the fringe
		while fringe: # Terminates if fringe is empty i.e. all nodes expanded
			current_node = fringe.pop() # Pop a node off the queue
			if DigitProblem.goal_test(current_node):
				return current_node, expanded
				# If goal test satisfied, output the current node and the expanded dictionary
			if len(expanded) > 1000: # Test if we have expanded too many nodes.
				return "1000 Nodes Expanded"
			if str(current_node.state) not in expanded: # Test if we have already expanded the current node.
				expanded[str(current_node.state)] = current_node # If not, add it to the dictionary
				fringe.extend(current_node.expand(DigitProblem)) # and expand it and add to the fringe.
		return None # If no node satisfies the goal state, and all nodes are expanded, return None

	def breadth_first_graph_search(DigitProblem): 
		"""BFS uses a FIFO Queue as a fringe, so to implement BFS,
		we simply call graph search with a FIFOQueue()"""
		return graph_search(DigitProblem, FIFOQueue())