Created
March 19, 2018 23:33
-
-
Save Shadid12/f928578ff89fb897b52a8b12c1d59458 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def numStops(self, start, end, maxStops): | |
""" | |
Wrapper function to calculate the number of stops | |
Args: | |
start (str): Starting city | |
end (str): Destination city | |
maxStops (int): number of maximum stops allows | |
Returns: | |
int: calclated number of routes | |
""" | |
return self.findRoutes(start, end, 0, maxStops) | |
def findRoutes(self, start, end, depth, maxStops): | |
""" | |
Recursive function to calculate the number of stops | |
Args: | |
start (str): Starting city | |
end (str): Destination city | |
maxStops (int): number of maximum stops allows | |
depth (int): current depth of recursion | |
Returns: | |
int: calclated number of routes | |
""" | |
visited =[] | |
routes = 0 | |
# Check if start and end nodes exists in route table | |
if start in self.routesTable and end in self.routesTable: | |
depth = depth + 1 | |
if depth > maxStops: # Check if depth level is within limit | |
return 0 | |
visited.append(start) # mark start as visited | |
for adj in self.routesTable[start]: | |
''' | |
If destination matches, we increment route | |
count, then continue to next node at same depth | |
''' | |
if adj == end: | |
routes = routes + 1 | |
''' | |
If destination does not match, and | |
destination node has not yet been visited, | |
we recursively traverse destination node | |
''' | |
if adj not in visited and adj != end: | |
depth = depth - 1 | |
routes += self.findRoutes(adj, end, depth, maxStops) | |
else: | |
return "No Such route" | |
# unmark the start node before leaving recursive func | |
if start in visited: | |
visited.remove(start) | |
return routes |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment