p11.py

# 6.00 Problem Set 11
#
# ps11.py
#
# Graph optimization
# Finding shortest paths through MIT buildings
#

import string
from graph import Digraph, Edge, Node, Rode,campusMap

#
# Problem 2: Building up the Campus Map
#
# Write a couple of sentences describing how you will model the
# problem as a graph)
#
def load_map(mapFilename):
    """
    Parses the map file and constructs a directed graph

    Parameters:
        mapFilename : name of the map file

    Assumes:
        Each entry in the map file consists of the following four positive
        integers, separated by a blank space:
            From To TotalDistance DistanceOutdoors
        e.g.
            32 76 54 23
        This entry would become an edge from 32 to 76.

    Returns:
        a directed graph representing the map
    """
    #TODO
"""
The IDLE gives the following error:
Loading map from file...
---------------
Test case 1:
Find the shortest-path from Building 32 to 56

Traceback (most recent call last):
  File "D:\asign1\11\ps11.py", line 170, in <module>
    brutePath1 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
  File "D:\asign1\11\ps11.py", line 96, in bruteForceSearch
    raise ValueError("Start or end not in graph.")
ValueError: Start or end not in graph.
"""
## So I am thinking there's something wrong with my code for this fcn.
## Yet when i add print statement to print the whole graph built by this fcn, I see the node '32' and ##'56' (32->56)...I'm confused now.If 32 and 56 already in the graph, how could this error be given???
## There are probably some other bugs in my code,for now I only want to fix this one so that i can move ##on.So take a look at this if got time...Thanks in advance.
##
##Details added on 3:05 PM UTC/GMT +8 hours Wednesday, October 10, 2012
"""
I add some print fcn in grapy.py(in my second code post) and found the following info in idle:
Loading map from file...
hasNode() in Digraph called.
addNode() in campusMap called.
Node  32  added.
hasNode() in Digraph called.
addNode() in campusMap called.
Node  36  added.
Rode  32->36     distance: 70  outside distance: 0  added
hasNode() in Digraph called.
addNode() in campusMap called.
Node  36  added.
hasNode() in Digraph called.
addNode() in campusMap called.
Node  32  added.
Rode  36->32     distance: 70  outside distance: 0  added
...
So node 32 and node 36 are added more than once, it seems
if not g.hasNode(nPair0):
   g.addNode(nPair0)
and
if not g.hasNode(nPair1):
   g.addNode(nPair1)
did not prevent this,"hasNode() in Digraph called." proves that Digraph.hasNode() has been called but duplicate node still walk into nodes set without ValueError('Duplicate node') being raised!??? And the error mentioned above this addtional description still is annoying me.So could any one take at a look at this?
"""
##    nodes = []
    print "Loading map from file..."
    g = campusMap()
    dataFile = open(mapFilename, 'r')
    for line in dataFile:
        if len(line) == 0:
            continue
        dataLine = string.split(line)
        nPair0 = Node(str(dataLine[0]))
        nPair1 = Node(str(dataLine[1]))
        if not g.hasNode(nPair0):
            g.addNode(nPair0)
        if not g.hasNode(nPair1):
            g.addNode(nPair1)
        rode = Rode(nPair0, nPair1, int(dataLine[2]), int(dataLine[3]))
##        print rode
        g.addEdge(rode)
    return g

##digraph = load_map("mit_map.txt")
#
# Problem 3: Finding the Shortest Path using Brute Force Search
#
# State the optimization problem as a function to minimize
# and the constraints
#

def bruteForceSearch(digraph, start, end, maxTotalDist, maxDistOutdoors, visited = [], dist = [], outdoorDist = [], toPrint = True):
    """
    Finds the shortest path from start to end using brute-force approach.
    The total distance travelled on the path must not exceed maxTotalDist, and
    the distance spent outdoor on this path must not exceed maxDisOutdoors.

    Parameters:
        digraph: instance of class Digraph or its subclass
        start, end: start & end building numbers (strings)
        maxTotalDist : maximum total distance on a path (integer)
        maxDistOutdoors: maximum distance spent outdoors on a path (integer)

    Assumes:
        start and end are numbers for existing buildings in graph

    Returns:
        The shortest-path from start to end, represented by
        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
        where there exists an edge from n_i to n_(i+1) in digraph,
        for all 1 <= i < k.

        If there exists no path that satisfies maxTotalDist and
        maxDistOutdoors constraints, then raises a ValueError.
    """
    #bruteForceSearch(digraph, start, end, maxTotalDist, maxDistOutdoors,
    #/ visited = [], dist = [], outdoorDist = [], toPrint = False)
    #TODO
    global numCalls
    numCalls += 1
##    print numCalls
    if not (digraph.hasNode(start) and digraph.hasNode(end)):
        print 'start: ', start, 'end: ',end
        #print digraph
        raise ValueError("Start or end not in graph.", start, end, digraph.__str__)
    if toPrint:
        print "    "*numCalls, "Finding path from ",start," to ",end
    path = [str(start)]
    if start == end:
        if toPrint: print "    "*numCalls, "Not looking at path from ", start, " to itself."
        numCalls -=1
        return path
    shortest = None
    for node in digraph.childrenOf(start):
        if (str(node) not in visited):
            visited = visited + [str(node)]
            dist.append(digraph.edges[start][node][0])
            outdoorDist.append(digraph.edges[start][node][1])
            prveCost = sum(outdoorDist)
            newPath = bruteForceSearch(digraph, node, end, maxTotalDist, maxDistOutdoors, visited, dist, outdoorDist, toPrint)
            if sum(maxTotalDist) >= maxTotalDist or sum(outdoorDist) >= maxDistOutdoors:
                newPath = None
                dist = []
                outdoorDist = []
            if newPath == None:
                continue
            if (shortes == None or prveCost > sum(outdoorDist)):
                shortest = newPath
        if shortes != None:
            path = path + shortest
        else:
            path = None
        if toPrint: print "    "*numCalls, "Path from node ",start, " to ",end, " was: ",path
        return path


#
# Problem 4: Finding the Shorest Path using Optimized Search Method
#
def directedDFS(digraph, start, end, maxTotalDist, maxDistOutdoors):
    """
    Finds the shortest path from start to end using directed depth-first.
    search approach. The total distance travelled on the path must not
    exceed maxTotalDist, and the distance spent outdoor on this path must
    not exceed maxDisOutdoors.

    Parameters:
        digraph: instance of class Digraph or its subclass
        start, end: start & end building numbers (strings)
        maxTotalDist : maximum total distance on a path (integer)
        maxDistOutdoors: maximum distance spent outdoors on a path (integer)

    Assumes:
        start and end are numbers for existing buildings in graph

    Returns:
        The shortest-path from start to end, represented by
        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
        where there exists an edge from n_i to n_(i+1) in digraph,
        for all 1 <= i < k.

        If there exists no path that satisfies maxTotalDist and
        maxDistOutdoors constraints, then raises a ValueError.
    """
    #TODO
    pass

# Uncomment below when ready to test
if __name__ == '__main__':
    # Test cases
    digraph = load_map("mit_map.txt")

    LARGE_DIST = 1000000

    # Test case 1
    print "---------------"
    print "Test case 1:"
    print "Find the shortest-path from Building 32 to 56"
    expectedPath1 = ['32', '56']
    numCalls = -1
    brutePath1 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
##    dfsPath1 = directedDFS(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
    print "Expected: ", expectedPath1
    print "Brute-force: ", brutePath1