class Node(object):
    def __init__(self, name):
        self.name = str(name)
    def getName(self):
        return self.name
    def __str__(self):
        return self.name

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)

class WeightedEdge(Edge):
    def __init__(self, src, dest, dist,out):
        self.src = src
        self.dest = dest
        self.dist = dist
        self.out = out
    def getTotalDistance(self):
        return self.dist
    def getOutdoorDistance(self):
        return self.out
    def __str__(self):
        return str(self.src) + '->'+str(self.dest) + '('+str(self.dist)+\
               ', '+str(self.out)+ ')'            

class Digraph(object):
    def __init__(self):
        self.nodes = set([])
        self.edges = {}
    def addNode(self, node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.add(node)
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not(src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.nodes
    def __str__(self):
        res = ''
        for k in self.edges:
            for d in self.edges[k]:
                res = res + str(k) + '->' + str(d) + '\n'
        return res[:-1]

class Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

class WeightedDigraph(Digraph):
    def addEdge(self,edge):
        src = edge.getSource()
        dest = edge.getDestination()
        dist = edge.getTotalDistance()
        out = edge.getOutdoorDistance()
        if not( src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[src].append( (dest,dist,out) ) #a triple tuple

    def childrenOf(self,node):
        children = []
        for child in self.edges[node]:
            children.append(child[0])
        return children
    
    def __str__(self):
        res = ''
        for k in self.edges:
            for d in self.edges[k]:
                res = res+str(k)+'->'+str(d[0])+' ('+str(float(d[1]))+', '+str(float(d[2]))+')'+'\n'
        return res[:-1]

def printPath(path):
    # a path is a list of nodes
    result = ''
    for i in range(len(path)):
        if i == len(path) - 1:
            result = result + str(path[i])
        else:
            result = result + str(path[i]) + '->'
    return result
