class Graph:
    ''' a graph represented using an adjacency list ''' 
    
    def __init__(self, num_vertices, is_directed = False):
        self.num_vertices = num_vertices        
        self.vertices = [[] for i in range(num_vertices)]
        self.is_directed = is_directed
    
    def add_edge(self, v1, v2):
        ''' 
        Add an edge from v1 to v2. Note, vertices are assumed to 
        be integers in the range 0 to num_vertices-1''' 
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)
        
    def get_neighbours(self, v):
        ''' 
        Return a copy of vertices that are adjacent to vertex v. Note, v
        is assumed to be an integer in the range 0 to num_vertices-1.
        ''' 
        return self.vertices[v][:]
    
    def has_edge(self, v1, v2):
        ''' 
        Return True if edge exists between v1 and v2, False otherwise. 
        Note, vertices are assumed to be integers in the range 0 to
        num_vertices-1.
        '''

        # note that the following takes O(d(v1)) steps, where
        # d(v1) is the degree of vertex v1. 
        return v2 in self.vertices[v1]

    
if __name__ == '__main__':
    
    # create a new undirected Graph with 10 vertices
    g = Graph(10)
    g.add_edge(0,1)
    g.add_edge(1,2)
    g.add_edge(0,2)
    
    # list all the edges in the graph
    
    # the following has O(|V|^2 + |V||E|) time complexity
    
    for i in range(g.num_vertices):
        for j in range(g.num_vertices):
            if g.has_edge(i, j):
                print "(",i,",",j,")"
                
    # alternatively:
    
    # the following has O(|V| + |E|) time complexity 
    
    print "------------------------"
    
    for i in range(g.num_vertices):
        adjv = g.get_neighbours(i)
        for j in adjv:
            print "(",i,",",j,")"