Error in python implementation of topological sort

I just wrote some code to do topological sorting in Python given an undirected graph.

G = {
    7: [11, 8],
    5: [11],
    3: [8, 10],
    11: [2, 9],
    8: [9],
    2: [],
    9: [],
    10: []
}

class GraphException(Exception):
    def __init__(self, str):
        pass

def has_incoming_edges(g, a_node):
    """
    Return True if it has incoming edges,
    False otherwise.
    """
    for each_node in g:
        if a_node in g[each_node]:
            return True
    return False

def remove_edge(g, start, end):
    """
    Removes the edge start->end in g.
    """
    edges = g[start]
    edges.pop(edges.index(end))

def edges_exist(g):
    for each_node in g:
        if g[each_node]: return True
    return False

def do_topsort(g):
    S = [] # list of all nodes that have no incoming nodes
    L = [] # topordering

    for each_node in G:
        if not has_incoming_edges(g, each_node):
            S.append(each_node)

    while S:
        a_node = S.pop(0)
        print "Popping", a_node
        L.append(a_node)
        x = g[a_node]
        #TODO NEVER ITERATE ON A LIST AND REMOVE FROM IT AT
        # THE SAME TIME
        backup = g[a_node]
        for each_connected in backup:
            print ">>>", backup

            print "Removing edge", a_node, each_connected
            # Remove the edge from a_node to each_connected
            remove_edge(g, a_node, each_connected)

            print g

            if not has_incoming_edges(g, each_connected):
                print "Adding", each_connected
                S.append(each_connected)

    if edges_exist(g):
        print g
        print L
        raise GraphException("Graph has cycles")
    return L

def main():
    global G
    topsort = do_topsort(G)
    print topsort

if __name__ == '__main__':
    main()

      

        
        
        
      

    

The output I get from this code is as follows: -

Popping 3
>>> [8, 10]
Removing edge 3 8
{2: [], 3: [10], 5: [11], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 5
>>> [11]
Removing edge 5 11
{2: [], 3: [10], 5: [], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 7
>>> [11, 8]
Removing edge 7 11
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Adding 11
Popping 11
>>> [2, 9]
Removing edge 11 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
Adding 2
Popping 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
[3, 5, 7, 11, 2]
Traceback (most recent call last):
  File "topsort.py", line 80, in <module>
    main()
  File "topsort.py", line 76, in main
    topsort = do_topsort(G)
  File "topsort.py", line 71, in do_topsort
    raise GraphException("Graph has cycles")
__main__.GraphException

      

        
        
        
      

    

Note that there is a line in the output Popping 7

. It indicates that 7

this is the node being processed in the for loop for each_connected in backup:

. We see that 7 is due both to 11

and from 8

. However, the loop only seems to run once and remove the edge 7-11

. node 8

doesn't seem to be processed. What am I doing wrong?