this code is originally from http://greenteapress.com/complexity/Graph.py but modified a little

Graph.py

"""
this code is originally from http://greenteapress.com/complexity/Graph.py
modified original code a bit
original author: Allen B.Downey  
Copyright 2011 Allen B. Downey.
Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
"""
class Vertex(object):
    """A Vertex is a node in a graph."""

    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return 'Vertex(%s)' % repr(self.label)

    __str__ = __repr__
    
    
class Edge(tuple):
    """An Edge is a list of two vertices."""

    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError, 'Edges must connect exactly two vertices.'
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))

    __str__ = __repr__
    
class Graph(dict):
    """A Graph is a dictionary of dictionaries.  
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs=[], es=[]):
        """Creates a new graph.  
        vs: list of vertices;
        es: list of edges.
        """
        for v in vs:
            self.add_vertex(v)
            
        for e in es:
            self.add_edge(e)
    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e
        
    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs
    
    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    
    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited_v)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed
        

def main(script, *args):
    v = Vertex('v')
    w = Vertex('w')
    e = Edge(v, w)
    g = Graph([v,w], [e])
    print g


if __name__ == '__main__':
    import sys
    main(*sys.argv)