Moving from java to python.

[Tim Chase]

 >   def __init__(self, connections = None, uid = None):
 >     """
 >     Args:
 >       [connections - a list of (connected node, weight) tuples.  ]
 >       [uid - an identifier for comparisons.]
 >     """
 >     self._connected = []
 >     self._weights = []
 >
 >     if connections:
 >       for i in connections:
 >         self.connected.append(i[0])
 >         self.weights.append(i[1])

I'd likely write this something like

   if connections:
     self.connected, self.weights = zip(*connections)

You also shift here between "_connected" and "connected" (same 
with weights).  This might bite you.

 >     if not uid:
 >       self.id = id(self)
 >     else:
 >       self.id = uid

A common way of writing this would be

   self.id = uid or id(self)

However, the need for anything other than the id() is suspect. 
Imaginable, but suspect.

 >   def getConnected(self):
 >     return self._connected
 >
 >   def getWeights(self):
 >     return self._weights
 >   connected = property(getConnected, None)
 >   weights = property (getWeights, None)

No need for properties at this time...they can be added 
transparently later, if you need to do something programatic on 
access.

 >   def getConnections(self):
 >     connections = []
 >     for i in range(len(connected)):
 >       connections.append((self._connected[i],self._weight[i]))
 >     return connections
 >
 >   connections = property(getConnections, None)

And in an inverse of the __init__ method, I'd use something like

   def getConnections(self):
     return zip(self.connected, self.weights)

Just my first-pass thoughts...

-tkc