Find incident edges of given vertex in a directed graph using Python iterator

Question

I am writing a class to find the incident edges of a given vertex in a directed graph. The class uses an iterator to traverse the adjacency lists in the graph. However, I am having trouble returning the result in a correct format. Currently, I use a list found to determine if a given edge is an incident edge to the vertex under consideration. This approach gives the correct result, but I would like to avoid having the next method returning a list and instead return self.ptr.data (currently commented out).

class IncidentDirectedEdgeIterator(IncidentEdgeIterator):

"""
The interface of an incident directed edge iterator data structure.
"""

def __init__( self, graph, index ):
    """
    Constructs an incident edge iterator for the specified graph.

    @param graph: The graph including the incident edges.
    @type: L{Graph}
    @param index: The index specifying the vertex of the incident edges.
    @type: C{int}
    """
    super(IncidentDirectedEdgeIterator, self).__init__( graph, index )
    self.ptr = None
    self.graph = graph

def next( self ):
    """
    Returns the next incident edge in the graph. If there are no
    further edges, the StopIteration exception is raised.

    @raises: StopIteration if all incident edges have been enumerated.
    @type: C{StopIteration}
    @return: The next incident edge in the graph.
    @rtype: C{object}
    """
    found = []
    if self.ptr is None:
        i = 0
        while i >= 0 and i < self.graph.getNumberOfVertices():
            ptr = self.container.adjacencyList[i].head
            while ptr is not None:
                if self.index == ptr.data.getV1().getVertexNumber():
                    if ptr not in found:
                        found.append( ptr )
                    self.ptr = ptr
                ptr = ptr.next
            i += 1
    else:
        self.ptr = self.ptr.next
    if self.ptr is None:
        raise StopIteration
    if len( found ) == 0:
        raise StopIteration
    #return self.ptr.data
    return found

Using the found list is rather ugly and I would like to avoid it completely. Suggestions is much appreciated.

Using a generator function instead of the iterator class:

def generatorTest( self, index ):
    i = 0
    while i >= 0 and i < self.getNumberOfVertices():
        ptr = self.adjacencyList[i].head
        while ptr is not None:
            if index == ptr.data.getV1().getVertexNumber():
                yield ptr
            ptr = ptr.next
        i += 1

Answer 1

The thing you are missing is "yield", look up generators in the Python documentation. With that, you can return the edges one by one without having to create temporary lists.

Also, your code is not very Pythonic but rather seems to be C code. The first "smell" is that the vertices are stored in an array and referenced via their index. In Python, you would rather store references to the actual vertices instead. Also, your "class" shouldn't be a class but a plain function that yields the edges incident to the given vertex, see http://www.youtube.com/watch?v=o9pEzgHorH0.