# Simple graph creation, search, and display.
# 9/7/2007-9/9/2007
# Done by students in AE498MPA, Fall 2007.
# See http://www.ae.uiuc.edu/~tbretl/ for a class list.

# IMPORT MODULES
from __future__ import generators
import appuifw
import audio


# GROUP WITH PHONE SMITH: create the graph
def enum(it): # since 2.2 doesn't have the enumerate function
	n = 0
	for i in it:
		yield (n, i)
		n += 1
	raise StopIteration()

def create_graph():
	nodelist=[]
	adjlist=[]

	n = appuifw.query(u'Enter Node Name',"text")
	
	while n:
		nodelist.append(n)
		n = appuifw.query(u'Enter Node Name',"text")
	
	for node in nodelist:
		choose = [n for n in nodelist if n != node]
		index = [i for i, n in enum(nodelist) if n != node]
		appuifw.app.title = u"Enter adjacencies for %s" % (node, )
		t = appuifw.multi_selection_list(choices=choose)
		t = [index[k] for k in t]
		adjlist.append(t)
	
	# down here isn't completely necessary, I just thought it might
	# also be useful to cram these two lists into a single dictionary
	# so you can look up adjacancies by node name
	
	adjByName = dict([(name, adjlist[i]) for i, name in enum(nodelist)])
	
	return (nodelist,adjlist)


# GROUP WITH PHONE ALBRECHT (1): search the graph
def find_path1(v,adj,istart,iend):
	# BFS
	final_path = []
	if(istart == iend):
		return []
	if(istart > (len(v)-1)):
		return []
	if(iend > (len(v)-1)):
		return []
	
	visited = []
	queue = []
	pre = []
	base = []
	temp = []
	queue.append(istart)
	pre.append(istart)
	
	while(len(queue) > 0):
		pop_node = queue.pop(0)
		base.append(pre[0])      
		visited.append(pop_node)
		children = adj[pop_node]
		for child in children:
			if(visited.count(child) == 0):
				if(queue.count(child) == 0):
					if(child == iend):
						base.append(child)
						return flatten(base)
	
					queue.append(child)
					base.append(child)
					temp = base[:]
					pre.append(temp)
					base.pop()
		base.pop(0)
		pre.pop(0)
		
	return []

def flatten(start_list):
	final_list = []
	for element in start_list:
		if hasattr(element, "__iter__") and not isinstance(element, basestring):
			final_list.extend(flatten(element))
		else:
			final_list.append(element)
	return final_list


# GROUP WITH PHONE ATINC: search the graph
def find_path2(v,adj,start,goal):
#   Bread First Search
#   finds the shortest path from the start node to the goal node for unweighted graphs
#   v: list of nodes
#   adj: list of indexes of adjacent nodes
#   start: the index of the start node
#   goal: the index of the goal node
#   returns None if there is no path from the start node to the goal node
#           otherwise, returns the shortest path in a list containing
#           the indexes of the nodes in the path.
	n = len(v)
	queue = [start]
	visited = [0]*n
	visited[start] = 1
	pre = [-1]*n
	while len(queue)>0:
		node = queue.pop(0);
		if node == goal:
			# found the goal, return the path
			temp = goal
			path = [temp]
			while pre[temp] != -1:
				path.insert(0,pre[temp])
				temp = pre[temp]
			return path
		# for each adjacent node
		for ad in adj[node]:
			# if not visited, not put to the que before
			if visited[ad] == 0:
				queue.append(ad)
				visited[ad] = 1
				pre[ad] = node
	return None

# GROUP WITH PHONE ALBRECHT (2): search the graph
# Breadth first search algorithm implementation, david albrecht
# for ae498mpa.
# Inputs:
#   v       Vertex list
#   adj     List of numeric adjacency lists, parallel to vertex list
#   istart  Numeric index of starting node
#   iend    Numeric index of ending node
# Returns: a list containing the (textual) vertex-by-virtex path to take, or
#   "None" if no such path exists.
def find_path3(v, adj, istart, iend):
	Q               = []                # BFS visitation queue
	been_queued     = [False]*len(v)    # Has vertex i ever been queued?
	pre             = [None]*len(v)     # How did we get here?
	
	Q.append(istart)                    # Push initial vertex into queue
	been_queued[istart] = True          # Mark to avoid double-back
	
	while(len(Q) > 0):                  # Loop until we find a path, or empty
										# the queue, indicating no path exists
		visiting = Q.pop(0)             # BFS -> consume head of queue
		if(visiting == iend):
			break                       # Reached end of path, done
		else:
			for neighbor in adj[visiting]:
				if(not been_queued[neighbor]):
					Q.append(neighbor)
					been_queued[neighbor] = True
					pre[neighbor] = visiting
	else:                               # Only get here if no path exists
		return None
	
	# Path found, reconstruct from pre into a list and return the list.
	# A stack would be slightly more efficient here but this works
	path = []
	at_vertex = iend
	path.append(iend)
	
	while(at_vertex != istart):
		at_vertex = pre[at_vertex]
		path.append(at_vertex)
	
	path.reverse()                      # Put in correct order
	return path

# GROUP WITH PHONES TIRA/CHIN: display the path
def follow_path(path):
	yesno=None
	for i in range (0, (len(path)-1)):
		while yesno == None:
			audio.say(unicode("Go from " + v[path[i]] + " to " + v[path[i+1]]))
			appuifw.note(unicode("Go from " + v[path[i]] + " to " + v[path[i+1]]))
			audio.say(unicode("Are you at " + v[path[i+1]] + " yet?"))
			yesno = appuifw.query(unicode("Are you at " + v[path[i+1]] + " yet?"),"query")
		yesno = None
	audio.say(unicode("Congratulations, you made it"))


# APPLICATION FLOW
# Create the graph.
(v,adj)=create_graph()
print u'v =',v
print u'adj =',adj
# Set the start and goal here, since we forgot to allow the user to specify them.
start=0
goal=1
# Search the graph. (Switch comments to try different algorithms.)
path=find_path1(v,adj,start,goal)
#path=find_path2(v,adj,start,goal)
#path=find_path3(v,adj,start,goal)
# Follow the path.
print u'path =',path
follow_path(path)