jiahuiding jiahuiding - 19 days ago 6
Python Question

How to fix the __iter__ function

{'a': [{'c','d'}, {'d'} ],
'b': [{'c','d'}, set() ],
'c': [set(), {'a','b','d'}],
'd': [{'a','c'}, {'a','b'} ],
'e': [set(), set() ]}

class Graph:
def __init__(self,*args):
self.edges = {}

def degree(self,n):
count = 0
if n not in self.edges.keys():
raise GraphError
for key,value in self.edges.items():
if key == n:
for c in value:
for x in c:
count += 1
return count

def __iter__(self):
l=[]
for key,value in self.edges.items():
for item in value[0]:
l.append((key,item))
return sorted(l, key = degree(l[0]))


Define an iter method so that each call to next produces a value that is a 2-tuple repesenting an edge in the Graph: an origin node followed by one of its destination nodes. The origin nodes are produced in increasing order of their degree (how many edges, both incoming and outgoing, they have). And, if two nodes have the same degree, they should be produced in alphabetical order. The destination nodes for each origin node should appear in alphabetical order.
For example, iterating over the original Graph above produces 6 values in the following order: ('b', 'c'), ('b', 'd'), ('a', 'c'), ('a', 'd'), ('d', 'a'), and ('d', 'c'). This is the ordering, because node b has degree 2, so it and its two destination nodes, appearing alphabetically, are first; node a has degree 3, so it and its two destination nodes, appearing alphabetically, are next; and finally node d has degree 4, so it and its two destination nodes, appearing alphabetically, are last.

node

I am working in the iter function, when it calls

g = Graph()
g.edges = {'a': [{'c','d'},{'d'}], 'b': [{'c','d'}, set()], 'c': [set(),{'a','b','d'}], 'd': [{'a','c'},{'a','b'}], 'e': [set(),set()]}


it should return

[t for t in g]-->[('b', 'c'), ('b', 'd'), ('a', 'c'), ('a', 'd'), ('d', 'a'), ('d', 'c')]


but when I call me iter function, it produces the following error:

96 *Error: [t for t in g] raised exception TypeError: iter() returned non-iterator of type 'list'
99 *Error: [t for t in g] raised exception TypeError: iter() returned non-iterator of type 'list'
102 *Error: [t for t in g] raised exception TypeError: iter() returned non-iterator of type 'list'


can someone help me to fix my iter function?

Answer

You can use generator to implement __iter__ for Graph. Then you just need to sort the vertices with tuple key (degree, name), iterate over them and yield the edges in alphabetical order:

EDGES =  {
    'a': [{'c','d'},  {'d'}        ],
    'b': [{'c','d'},  set()        ],
    'c': [set(),      {'a','b','d'}],
    'd': [{'a','c'},  {'a','b'}    ],
    'e': [set(),      set()        ]
}

class Graph:
    def __init__(self, edges):
        self.edges = edges

    def degree(self,n):
        if n not in self.edges:
            raise GraphError
        return sum(len(s) for s in self.edges[n])

    def __iter__(self):
        # Iterate over vertices, primary key is degree and 
        # secondary is name 
        for v in sorted(self.edges, key=lambda x: (self.degree(x), x)):
            # Iterate over outgoing edges in alphabetical order
            for other in sorted(self.edges[v][0]):
                yield v, other

g = Graph(EDGES)
print(list(iter(g)))

Output:

[('b', 'c'), ('b', 'd'), ('a', 'c'), ('a', 'd'), ('d', 'a'), ('d', 'c')]
Comments