Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

Finished!!

By: loubot on May 2nd, 2013  |  syntax: Python  |  size: 2.43 KB  |  views: 634  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. def bruteForceSearch(graph,start,end,maxTotalDist,maxDistOutdoors,visited = [],dist =0,outDist = 0):
2.     """
3.    Finds the shortest path from start to end using brute-force approach.
4.    The total distance travelled on the path must not exceed maxTotalDist, and
5.    the distance spent outdoor on this path must not exceed maxDisOutdoors.
6.
7.    Parameters:
8.        digraph: instance of class Digraph or its subclass
9.        start, end: start & end building numbers (strings)
10.        maxTotalDist : maximum total distance on a path (integer)
11.        maxDistOutdoors: maximum distance spent outdoors on a path (integer)
12.
13.    Assumes:
14.        start and end are numbers for existing buildings in graph
15.
16.    Returns:
17.        The shortest-path from start to end, represented by
18.        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
19.        where there exists an edge from n_i to n_(i+1) in digraph,
20.        for all 1 <= i < k.
21.
22.        If there exists no path that satisfies maxTotalDist and
23.        maxDistOutdoors constraints, then raises a ValueError.
24.    """
25.     path = [str(start)]
26.     pathDist = [str(dist)]
27.     pathOut = [str(outDist)]
28.     if MITNode(start) == MITNode(end):
29.         return path, dist,outDist
30.     shortest = None
31.     if visited == []:
32.         visited = [str(start)]
33.     for edge in graph.childrenOf(MITNode(start)):
34.         if str(edge.getDestination()) not in visited:
35.             visited = visited + [str(edge.getDestination())]
36.
37.             possPath, possDist,possOutDist = bruteForceSearch(graph,edge.getDestination(),\
38.                   end,maxTotalDist,maxDistOutdoors,visited, edge.getDistance(),edge.getOutDist())
39.
40.
41.             if possPath == None:
42.                 continue
43.             if maxDistOutdoors == 0:
44.                 if possOutDist != 0:
45.                     continue
46.             if shortest == None or possDist < bestDist:
47.                 shortest = possPath
48.                 bestDist = possDist
49.                 bestOutDist = possOutDist
50.     if shortest == None:
51.         path = None
52.         retPathDist = [str(0)]
53.         retOutDist = [str(0)]
54.     elif (dist + bestDist) > maxTotalDist or (outDist + bestOutDist) > maxDistOutdoors:
55.         path = None
56.         retPathDist = [str(0)]
57.         retOutDist = [str(0)]
58.
59.     else:
60.         path = path + shortest
61.         retPathDist = dist + bestDist
62.         retOutDist = outDist + bestOutDist
63.     return path, retPathDist,retOutDist
clone this paste RAW Paste Data
Top