A simple graph data structure

graph.py

#!/usr/bin/env python
import itertools

class Graph(dict):
    def __init__(self, vs=[], es=[]):
        """create a new graph. (vs) is a list of vertices;
        (es) is a 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 (v) to the graph"""
        self[v]={}
        
    def add_edge(self, e):
        """add (e) to the graph by adding an entry in both directions.
        
        If there is already an edge connecting these Vertices,
        the new edge replaces it.
        """
        v, w = e
        self[v][w] = e
        self[w][v] = e
        
    def get_edge(self, v1, v2):
        """ takes two vertices and returns the edge between them.
        If not exists, return None"""
        try:
            return self[v1][v2]
        except:
            return None
        
    def remove_edge(self, e):
        """ remove all references to the edge from the graph """
        v, w = e
        self[v].pop(w)
        self[w].pop(v)
        
    def vertices(self):
        """ returns a list of the vertices """
        return self.keys()
    
    def edges(self):
        """ returns a list of edges in a graph.
        For undirected graph, there are two references to each node.
        """
        edges = []
        for v1 in self.iterkeys():
            for v2 in self[v1].keys():
                edges.append(self[v1][v2])
        
        return edges
    
    def out_vertices(self, v):
        """ takes a Vertex and returns a list of the adjacent
        vertices """
        return self[v].keys()
    
    def out_edges(self, v):
        """ takes a Vertex and returns a list of connected edges """
        out_edges=[]
        for vertex in self[v].keys():
            [out_edges.append(edge) for edge in self[vertex].values()]
            
        return out_edges
    
    def add_all_edges(self):
        """ takes an edgeless Graph and makes a complete graph
        by adding edges between all pairs of vertices """
        vertices = self.vertices() # get the list of vertices
        # make all possible tuple pairs of vertices
        for v1v2 in itertools.permutations(vertices, 2):
            self.add_edge(Edge(v1v2[0], v1v2[1]))
    
    def add_regular_edges(self):
        """ create regular graph with a given degree.
        The necessary and sufficient conditions for a k regular graph of order n
        to exist are that n >= k+1 and that nk is even.
        """
        # check existence
        n = len(self.vertices())
        if(n < degree+1 or n*k%2 == 1):
            print("Invalid regular graph existence condition")

class Vertex(object):
    def __init__(self, label=''):
        self.label = label
        
    def __repr__(self):
        return 'Vertex(%s)' % repr(self.label)
    
    __str__ = __repr__
    
class Edge(tuple):
    def __new__(cls, e1, e2):
        return tuple.__new__(cls, (e1, e2))
    
    def __repr__(self):
        return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))
    
    __str__ = __repr__

graphTest.py

from graph import Graph, Vertex, Edge

if __name__=="__main__":
    v = Vertex('v')
    w = Vertex('w')
    e = Edge(v,w)
    g = Graph([v,w],[e])