###################################################################
##      Dennis Tracy Ivy, Jr.
##      04/2/2014
##      self study of MIT 6.00
##      ps11 - optimization, dynamic programming, graphs, etc
###################################################################
import string                                                      
#class for node objects    
class Node(object):                     
   def __init__(self, name):            
       self.name = str(name)
   def getName(self):                   
       return self.name
   def __str__(self):                   
       return self.name
   def __repr__(self):                  
      return self.name
   def __eq__(self, other):             
      return self.name == other.name                                    
   def __ne__(self, other):
      return not self.__eq__(other)     
#class for edges
class Edge(object):                     
   def __init__(self, src, dest):       
       self.src = src
       self.dest = dest
   def getSource(self):                 
       return self.src
   def getDestination(self):            
       return self.dest
   def __str__(self):                   
       return str(self.src) + '->' + str(self.dest)
#weighted edges(extends edge)
class WEdge(Edge):                                          
    def __init__(self, src, dest, distance, outdoor):
        
        self.src  = src                                     
        self.dest = dest
        self.distance = int(distance)
        self.outdoor  = int(outdoor)
    def getSource(self):                                    
        return self.src
    def getDestination(self):                               
        return self.dest    
    def getDistance(self):                                  
        return int(self.distance)
    def getOutdoorDistance(self):                           
        return int(self.outdoor)
    def __str__(self):                                      
        return str(self.src.getName().rjust(2) ) + '->' + \
                str(self.dest.getName().ljust(2) ) + \
                ' distance=' + str(self.distance).rjust(3) + \
                ' outdoor=' + str(self.outdoor).rjust(3)
#digraph
class Digraph(object):
   def __init__(self):                                        
       self.nodes = []
       self.edges = {}
   #add a node to the graph
   def addNode(self, node):                                   
       
       if node in self.nodes:                                 
           #print("Duplicate Node!")
           raise ValueError('Duplicate node')                 
       else:
           if type(node) != Node:                             
                raise TypeError                               
           self.nodes.append(node)                            
           self.edges[str(node)] = []
   #add an edge to the graph
   def addEdge(self, edge):                                   
       src = edge.getSource()                                 
       dest = edge.getDestination()                           
       if not(src in self.nodes and dest in self.nodes):      
           #print ("Node not in graph!")                      
           raise ValueError('Node not in graph')                                        
       self.edges[str(src)].append(edge)
   #get this nodes children
   def childrenOf(self, node):                                
       return self.edges[ str(node) ]
   #check if node exists in graph
   def hasNode(self, node):                                   
       if node in self.nodes:                                 
           return True                                        
       else: return False
   #calc the path length
   def calcPathLength(self, path, toPrint=False):             
        distances=[]                                          
        outdoors=[]
        for i in range (0,len(path)-1):                       
            d,o = self.distanceFromParentToChild(Node(path[i]),Node(path[i+1]))        
            distances.append(d)                                                        
            outdoors.append(o)
        if toPrint==True:                                                              
            print (str(sum(distances)).rjust(3), "/", str(sum(outdoors)).ljust(3))
        return ( sum(distances), sum(outdoors) )
   #distance from parent node to child node
   def distanceFromParentToChild(self, src, dest):                                     
        for i in self.edges[str(src)]:                                                 
            if i.getDestination() == dest:                                             
                return (i.getDistance(), i.getOutdoorDistance())                       
   #pretty print
   def __str__(self):                                                                  
       res = ''                                                                        
       for k in sorted(self.edges):                                                    
           for d in self.edges[k]:                                                     
               res = res + str(d) + '\n'                                               
       return res[:-1]                                                                 
#read the map and create a digraph
def load_map(mapFilename):
    print ("Loading map from file...")
    g=Digraph()
    if type(mapFilename) != str:
        raise FileNotFoundError("Trouble opening" + mapFilename)
    with open(mapFilename, 'r') as f:                           
        for line in f:                                          
            try:                                                
                src,dest,dist,outdoor = line.split()            
            except:                                             
                raise Exception("Trouble reading from file" + mapFilename)
            src_node  = Node(src)                                         
            dest_node = Node(dest)                                                      
            if not g.hasNode(src_node) : g.addNode(src_node)              
            if not g.hasNode(dest_node) : g.addNode(dest_node)            
            edge=WEdge(src_node,dest_node,dist,outdoor)                   
            g.addEdge(edge)                                               
        
    #with open("graph.txt", 'w') as out:                                          
    #    out.write(str(g))                                                        
    #print(g)                                                                     
    return g                                                                      
###################################################################
#recursive function to find the shortest path thru the graph using 
#brute force exhaustive depth first search
###################################################################
def bruteForceSearch(digraph, start, end, maxTotalDist, maxDistOutdoors, visited=None, counter=0): 
    if visited == None : visited = []                              
    try:
        start = Node(start)                                        
        end = Node(end)
    except:
        raise ChildProcessError('Unable to create nodes')
    if not ( digraph.hasNode(start) and digraph.hasNode(end) ):    
        raise ValueError("Start or End does not exist")
    path = [str(start)]                                            
    if start == end : return path                                  
    shortest = None                                                
    bestPath = None                                                
 
    for node in digraph.childrenOf(start):                         
        destination = node.getDestination()                        
        if ( str(destination) not in visited ):                    
            visited = visited + [str(destination)]                 
            newPath = bruteForceSearch(digraph,                    
                                       destination,                
                                       end,                        
                                       maxTotalDist,               
                                       maxDistOutdoors,            
                                       visited,
                                       counter=counter+1)          
            if newPath == None :                                   
                continue                                           
                                                                                        
            currentPath,outdoor=digraph.calcPathLength(path + newPath)   
            if outdoor > maxDistOutdoors or currentPath > maxTotalDist:  
                visited.remove(str(destination))                         
                continue                                                 
            currentPath, outdoor=digraph.calcPathLength(newPath)         
            if bestPath == None or (currentPath < bestPath):             
                shortest = newPath                                       
                bestPath,outdoor = digraph.calcPathLength(shortest)      
                
    if shortest != None:                                                 
        return path + shortest                                           
    else :                                                               
        if counter==0: raise ValueError                                  
        return None               
                                           
###################################################################
#recursive function to find the shortest path thru the graph using 
#directed depth first search w/memoization/dynamic programming
###################################################################
def directedDFS(digraph, start, end, maxTotalDist, maxDistOutdoors,visited = None, memo = None, counter=0):
    if visited == None : visited = []                                   
    if memo == None : memo = {}                                         
    start = Node(start)                                                 
    end = Node(end)
    if not (digraph.hasNode(start) and digraph.hasNode(end)):           
        raise ValueError("Start or End does not exist")
    path = [str(start)]                                                 
    if start == end : return path                                       
    shortest = None                                                     
    bestPath = None                                                     
  
    for node in digraph.childrenOf(start):                              
        destination = node.getDestination()                             
        if ( str(destination) not in visited ):                         
            visited = visited + [str(destination)]                      
            try:
                newPath = memo[str(destination),str(end)]
            except:
                newPath = directedDFS (digraph,                         
                                       destination,                     
                                       end,                             
                                       maxTotalDist,                    
                                       maxDistOutdoors,                 
                                       visited,                         
                                       memo,                            
                                       counter=counter+1)               
            if newPath == None :                                        
                continue                                                
            
            currentPath,outdoor=digraph.calcPathLength(path + newPath)  
            if outdoor > maxDistOutdoors or currentPath > maxTotalDist: 
                visited.remove(str(destination))                        
                try:                                                    
                    del(memo[str(destination),str(end)])                
                except:                                                 
                    pass                                                
                continue                                                
            currentPath, outdoor=digraph.calcPathLength(newPath)        
            if bestPath == None or (currentPath < bestPath):            
                shortest = newPath                                      
                bestPath,outdoor = digraph.calcPathLength(shortest)     
                memo[str(destination), str(end)] = newPath            
                
    if shortest != None:                                                    
        return path + shortest                                              
    else :                                                                  
        if counter==0: raise ValueError                                     
        return None
###################################################################
#### The following unit tests are part of this assignment, 
###################################################################
if __name__ == '__main__':
    LARGE_DIST = 1000000
    digraph = load_map("mit_map.txt")
    # Test case 1
    print ("---------------")
    print ("Test case 1:")
    print ("Find the shortest-path from Building 32 to 56")
    expectedPath1 = ['32', '56']
    print ("Expected:    ", expectedPath1)
    brutePath1 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
    print ("Brute-force: ", brutePath1)
    dfsPath1 = directedDFS(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
    print ("DFS:         ", dfsPath1)
    # Test case 2
    print ("---------------")
    print ("Test case 2:")
    print ("Find the shortest-path from Building 32 to 56 without going outdoors")
    expectedPath2 = ['32', '36', '26', '16', '56']
    print ("Expected:    ", expectedPath2)
    brutePath2 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, 0)
    print ("Brute-force: ", brutePath2)
    dfsPath2 = directedDFS(digraph, '32', '56', LARGE_DIST, 0)
    print ("DFS:         ", dfsPath2)
    # Test case 3
    print ("---------------")
    print ("Test case 3:")
    print ("Find the shortest-path from Building 2 to 9")
    expectedPath3 = ['2', '3', '7', '9']
    print ("Expected:    ", expectedPath3)
    brutePath3 = bruteForceSearch(digraph, '2', '9', LARGE_DIST, LARGE_DIST)
    print ("Brute-force: ", brutePath3)
    dfsPath3 = directedDFS(digraph, '2', '9', LARGE_DIST, LARGE_DIST)
    print ("DFS:         ", dfsPath3)
    # Test case 4
    print ("---------------")
    print ("Test case 4:")
    print ("Find the shortest-path from Building 2 to 9 without going outdoors")
    expectedPath4 = ['2', '4', '10', '13', '9']
    print ("Expected:    ", expectedPath4)
    brutePath4 = bruteForceSearch(digraph, '2', '9', LARGE_DIST, 0)
    print ("Brute-force: ", brutePath4)
    dfsPath4 = directedDFS(digraph, '2', '9', LARGE_DIST, 0)
    print ("DFS:         ", dfsPath4)
    # Test case 5
    print ("---------------")
    print ("Test case 5:")
    print ("Find the shortest-path from Building 1 to 32")
    expectedPath5 = ['1', '4', '12', '32']
    print ("Expected:    ", expectedPath5)
    brutePath5 = bruteForceSearch(digraph, '1', '32', LARGE_DIST, LARGE_DIST)
    print ("Brute-force: ", brutePath5)
    dfsPath5 = directedDFS(digraph, '1', '32', LARGE_DIST, LARGE_DIST)
    print ("DFS:         ", dfsPath5)
    # Test case 6
    print ("---------------")
    print ("Test case 6:")
    print ("Find the shortest-path from Building 1 to 32 without going outdoors")
    expectedPath6 = ['1', '3', '10', '4', '12', '24', '34', '36', '32']
    print ("Expected:    ", expectedPath6)
    brutePath6 = bruteForceSearch(digraph, '1', '32', LARGE_DIST, 0)
    print ("Brute-force: ", brutePath6)
    dfsPath6 = directedDFS(digraph, '1', '32', LARGE_DIST, 0)
    print ("DFS:         ", dfsPath6)
    # Test case 7
    print ("---------------")
    print ("Test case 7:")
    print ("Find the shortest-path from Building 8 to 50 without going outdoors")
    bruteRaisedErr = 'No'
    dfsRaisedErr = 'No'
    try:
        bruteForceSearch(digraph, '8', '50', LARGE_DIST, 0)
    except ValueError:
        bruteRaisedErr = 'Yes'
    
    try:
        directedDFS(digraph, '8', '50', LARGE_DIST, 0)
    except ValueError:
        dfsRaisedErr = 'Yes'
    
    print ("Expected: No such path! Should throw a value error.")
    print ("Did brute force search raise an error?", bruteRaisedErr)
    print ("Did DFS search raise an error?", dfsRaisedErr)
    # Test case 8
    print ("---------------")
    print ("Test case 8:")
    print ("Find the shortest-path from Building 10 to 32 without walking")
    print ("more than 100 meters in total")
    bruteRaisedErr = 'No'
    dfsRaisedErr = 'No'
    try:
        x=bruteForceSearch(digraph, '10', '32', 100, LARGE_DIST)  
    except ValueError:
        bruteRaisedErr = 'Yes'    
    try:
        y=directedDFS(digraph, '10', '32', 100, LARGE_DIST)         
    except ValueError:
        dfsRaisedErr = 'Yes'
    
    print ("Expected: No such path! Should throw a value error.")
    print ("Did brute force search raise an error?", bruteRaisedErr)
    print ("Did DFS search raise an error?", dfsRaisedErr)