graph.py

# 6.00 Problem Set 11
#
# graph.py
#
# A set of data structures to represent graphs
#

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 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 Rode(Edge):
   def __init__(self, src, dest, dist, outsideDist):
      Edge.__init__(self, src, dest)
      self.dist = dist
      self.outsideDist = outsideDist
   def getDist(self):
      return self.dist
   def getOutsideDist(self):
      return self.outsideDist
   def __str__(self):
      return str(self.src) + '->' + str(self.dest) +'     distance: '+str(self.dist) + '  outside distance: '+str(self.outsideDist)

class Digraph(object):
   """
   A directed graph
   """
   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):
       print 'hasNode() in Digraph called.'
       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 campusMap(Digraph):
   def __init__(self):
      Digraph.__init__(self)
   def addNode(self,node):
      print 'addNode() in campusMap called.'
      if node in self.nodes:
           raise ValueError('Duplicate node')
      else:
         self.nodes.add(node)
         print "Node ", node, " added."
         self.edges[node] = {}
   def addEdge(self,rode):
      src = rode.getSource()
      dest = rode.getDestination()
      dist = rode.getDist()
      outsideDist= rode.getOutsideDist()
      if not(src in self.nodes and dest in self.nodes):
         raise ValueError('Node not in graph')
      self.edges[src][dest] = (dist, outsideDist)
      print "Rode ", rode, " added"

   def childrenOf(self, node):
      return self.edges[node]