RealDev

#recursive check for a path between A and B of length <= 3
import copy

#Get the list of vertices you can go to from a given vertice
#returns blank if we for some arb reason ask for a vertice's list that
# doesnt exist
def findlist(G,V):
G1 = copy.deepcopy(G)
if (G1[0][0] == V):
return G1[0][1]
elif len(G1) > 0:
return findlist(G[1:],V)
else:
return []

#begin the recursive search by getting the places you can go to from the A
# vertice, returns the final result
def search(G, A, B):
L = findlist(G,A)
return gothrough(G, L, B, 2) #the 2 is what we want the maximum length to
# be less 1 (so for l <= 3 we use 2)

#go through each vertex in the list of possible paths, if C == 0 we have
# reached our max depth, so we return a false (prevents infinite loops)
# L is the current vertice list, if the list is empty we return false as there
# was no path. We check if the first item in the list is the B we are looking
# for, if it is check will return True, if it isnt, we run gothrough on the
# tail of the list.
def gothrough(G, L, B, C):
if (C == 0):
return False
elif len(L) > 0:
a = check(G, L[0], C, B)
if (a):
return True
return gothrough(G,L[1:],B,C)
else:
return False

#takes in the current vertice we are checking, the length of our path so far
# and the B we are looking for. If the B is in L we return true as we are
# <= our max length (as gothrough will never call check after the maximum
# length of path). If our B isnt in L we run gothrough with C-1 as our list
# has gotten longer by 1, still looking for original B
def check(G, V, C, B):
L = findlist(G,V)
if (B in L):
return True
else:
return gothrough(G, L, B, C-1)

#sample input 1: same graph as given in COMS1 Lab test graph {P,Q,R,S} but named
# differently, has the same structure. Returns true as there is a path
# between A and C that is length <= 3.
#G = [["A",["B"]],["B",["A","C","D"]],["C",["B","D"]],["D",["C","B"]]]
#A = "A"
#B = "C"
#sample input 2: a graph {A,B,C,D,E} where A leads to B, B to C, etc only
# you cannot go from A to E, and each vertice only goes to the next vertice
# (will work directed and undirected, this is just directed). returns false
# as the length from A to E is 4 so it never gets there.
#G = [["A",["B"]],["B",["C"]],["C",["D"]],["D",["E"]],["E",[]]]
#A = "A"
#B = "E"
#sample input 3: as above but undirected:
G = [["A",["B"]],["B",["A","C"]],["C",["B","D"]],["D",["C","E"]],["E",["D"]]]
A = "A"
B = "E"

print search(G, A, B)