Как получить доступ к спискам смежности внутри объекта Vertex?

Question

Я построил график в Python на основе классов вершин и графов, но в методе isCycleUtil(), когда я пытаюсь получить доступ к объекту Vertex, выполнив for i in self.vert_dict[v], я получаю объект TypeError: Vertex, который не является итерируемым.

Можете ли вы помочь мне исправить это и иметь функциональный метод isCycleUtil?

class Vertex: 
def __init__(self, node): 
    self.id = node 
    self.adjacent = {} 

def __str__(self): 
    return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent]) 

def add_neighbor(self, neighbor, weight=0): 
    self.adjacent[neighbor] = weight 

def get_connections(self): 
    return self.adjacent.keys() 

def get_id(self): 
    return self.id 

def get_weight(self, neighbor): 
    return self.adjacent[neighbor] 

def set_weight(self, neighbor, newvalue): 
    self.adjacent[neighbor] = newvalue 

и класс графа:

class Graph: 
def __init__(self): 
    self.vert_dict = {} 
    self.num_vertices = 0 

def __iter__(self): 
    return iter(self.vert_dict.values()) 

def add_vertex(self, node): 
    self.num_vertices += 1 
    new_vertex = Vertex(node) 
    self.vert_dict[node] = new_vertex 
    return new_vertex 

def get_vertex(self, n): 
    if n in self.vert_dict: 
     return self.vert_dict[n] 
    else: 
     return None 

def add_edge(self, frm, to, cost = 0): 
    if frm not in self.vert_dict: 
     self.add_vertex(frm) 
    if to not in self.vert_dict: 
     self.add_vertex(to) 

    self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost) 

def get_vertices(self): 
    return self.vert_dict.keys() 

def isCyclicUtil(self,v,visited,parent): 

    #Mark the current node as visited 
    if not visited[v]: 
     visited[v]= True 
     parent[v] = True 
     #Recur for all the vertices adjacent to this vertex 
     for i in self.vert_dict[v]: 
      # If the node is not visited then recurse on it 
      if (not visited[i] and self.isCyclicUtil(i,visited,parent)): 
       return True 
      elif (not parent[i]): 
       return True 
    parent[v] = False 
    return False 


#Returns true if the graph contains a cycle, else false. 
def isCyclic(self): 
    # Mark all the vertices as not visited 
    visited = {} 
    parent = {} 
    for i in self.vert_dict: 
     visited[i] = False 
     parent[i] = False 
    # Call the recursive helper function to detect cycle in different 
    #DFS trees 
    for i in self.vert_dict: 
     if(self.isCyclicUtil(i,visited,parent)): 
      return True 
    return False 

Answer 1

Чтобы избежать этой ошибки, вам нужно заменить:

for i in self.vert_dict[v] 

с

for i in self.vert_dict[v].get_connections() 

и использования:

visited[v.get_id()] 

вместо

visited[v] 

избежать исключение KeyError

Ваш график направлен так, правильно Algoritm является descibed в этой теме:

How to detect if a directed graph is cyclic?

Вам необходимо изменить реализацию isCyclicuntil метод:

def isCyclicUtil(self, v, visited, parent): 

    # Mark the current node as visited 
    if not visited[v]: 
     visited[v] = True 
     # Recur for all the vertices adjacent to this vertex 
     for i in self.vert_dict[v].get_connections(): 
      # If the node is not visited then recurse on it 
      if visited[i.get_id()]: 
       return True 
      elif self.isCyclicUtil(i.get_id(), visited, parent): 
       return True 
    return False