使用字典對圖類進行迭代

Question

我想用python 2.7構建一個可迭代的圖類。我想能夠遍歷包含頂點的字典。

從https://github.com/joeyajames切割和粘貼到目前爲止，但現在我很困惑如何使這項工作，以便我可以測試頂點字典的存在的頂點，如果不存在添加。這部分可能不需要。 「if（a not in gra）：」因爲驗證是在Graph類本身完成的。

期望的輸出是一個以頂點爲關鍵字的字典。實際上我甚至不確定列表是不是更好的對象使用。

class Vertex(object): 
    def __init__(self, n): 
     self.name = n 
     self.neighbors = list() 

     self.discovery = 0 
     self.finish = 0 
     self.color = 'black' 

    def add_neighbor(self, v): 
     if v not in self.neighbors: 
      self.neighbors.append(v) 
      self.neighbors.sort() 


class Graph(object): 
    def __init__(self,size): 
     self.vertices = {} 
     self.hops = 0 
     self.count = 0 
     self.limit = size 

    def __iter__(self): 
     return self 

    def next(self): 
     self.count += 1 
     if self.count > self.limit: 
      raise StopIteration 


    def add_vertex(self,vertex): 
     if isinstance(vertex, Vertex) and vertex.name not in self.vertices: 
      self.vertices[vertex.name] = vertex 
      return True 
     else: 
      return False 

    def add_edge(u,v): 
     if u in self.vertices and v in self.vertices: 
      for key, value in self.vertices.items(): 
       if key == u: 
        value.add_neighbor(v) 
       if key == v: 
        value.add_neighbor(u) 
        return True 
       else: 
        return False 



    def _dfs(self, vertex): 
      global hops 
      vertex.color = 'red' 
      vertex.discovery = hops 
      hops += 1 
      for v in vertex.neighbors: 
       if self.vertices[v].color == 'black': 
        self._dfs(self.vertices[v]) 
      vertex.color = 'blue' 
      vertex.finish = hops 
      time += 1 






input = ((5,3),(4 ,2),(0,1),(2 3),(0 4)) 

N,l = input[0] 
print "N is " + str(N) 
print "l is " + str(l) 

gra = Graph(N) 

for i in xrange(1,l): 
    a,b = input[i] 
    # Store a and b as vertices in graph object 
    print "a is " + str(a) + " b is " + str(b) 
    if (a not in gra): 
     print "adding a" 
     gra.add_vertex(Vertex(chr(a))) 
    if (b not in gra): 
     print "adding b" 
     gra.add_vertex(Vertex(chr(b))) 

Answer 1

您嘗試使用not in，測試對於遏制;實施__contains__ hook方便一點：

def __contains__(self, vertex): 
    return vertex.name in self.vertices 

我假設你想測試頂點，因此測試的遏制之前創建一個：

a = Vertex(chr(a)) 
if a not in gra: 
    print "adding a" 
    gra.add_vertex(a) 

對於迭代，我不會讓自己Graph迭代器;這限制了您只需重複。您的next()方法也缺少return聲明，因此您所做的只是產生一個None對象序列。

改爲而不是每次調用__iter__時都返回一個新的迭代器對象。您可以最簡單地通過使__iter__一個generator實現這一目標：

def __iter__(self): 
    for vertex in self.vertices.itervalues(): 
     yield vertex 

注意yield。我假設你想迭代頂點。