Список объектов, влияющих на список других объектов

Question

Я пытаюсь построить граф, где вершина имеет строковый идентификатор и связана с другой вершиной, если строковые идентификаторы из двух вершин отличаются только одним символом. Например, «собака» и «точка» могут быть соединены ребром. Я поддерживаю график со списком смежности. Однако после того, как я подтвердил, что могут быть подключены две вершины, я добавляю объект to_vertex в список объекта from_vertex и наоборот. Но это приводит к тому, что списки содержат повторяющиеся объекты. Ниже приводится код (он довольно плотный):

class vertex(): 
    def __init__(self, distance = -1, edges = [], name = ''): 
     self.name = name 
     self.distance = distance 
     self.edges = edges 

def create_graph(word_dict): 
    graph = [] 

    num_words = len(word_dict) 

    v = [vertex(name = word_dict[x]) for x in range(num_words)] 

    for i in range(num_words): 
     for j in range(i + 1, num_words): 
      count = 0 
      if len(word_dict[i]) == len(word_dict[j]): 
       print word_dict[i], word_dict[j] 
       k = 0 
       is_valid = True 
       while k < len(word_dict[i]): 
        print word_dict[i][k], word_dict[j][k] 
        if word_dict[i][k] != word_dict[j][k]: 
         if count == 1: 
          is_valid = False 
          break 
         else: 
          count += 1 
          k += 1 
        else: 
         k += 1 

       if is_valid == True: 
        v[i].edges.append(v[j]) 
        v[j].edges.append(v[i]) 

    graph = [v[i] for i in range(num_words)] 

    return graph 

if __name__ == '__main__': 
    graph = create_graph(['bat', 'cot', 'dog', 'dag', 'dot', 'cat']) 

    for v in graph: 
     print 'Vertex name ' + v.name 
     for edge in v.edges: 
      print edge.name 
     print '-----------------------------' 

Ниже приводится выход для цикла в основном:

Vertex name bat 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name cot 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dog 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dag 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dot 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name cat 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 

Через некоторое отладки, я обнаружил, что

if is_valid == True: 
    v[i].edges.append(v[j]) 
    v[j].edges.append(v[i]) 

вызывает проблему, но я просто не могу обвести вокруг нее голову. Это не похоже на то, что я изменяю поле ребер to_vertex в первом заявлении append, но первый оператор append также влияет на него.

Answer 1

Я не совсем уверен, но я думаю, что проблема заключается в использовании значения по умолчанию [] для edges, который (я думаю) создает уникальный объект [], а затем инициализирует по умолчанию этот уникальный объект. Таким образом, все ваши ребра будут по существу тем же самым объектом, и когда вы присоединитесь к одному из них, вы добавите все остальные. Имеет ли это смысл?

Чтобы избежать этой проблемы, не используйте init по умолчанию, а force self.edges = [].

Или, если вы действительно хотите, чтобы иметь возможность инициализировать произвольные края, попробовать что-то вроде:

def __init__(self, distance = -1, edges = None, name = ''): 
    self.name = name 
    self.distance = distance 
    if edges is None: 
     edges = [] 
    self.edges = edges 

(дайте мне знать, если это работает, так как я не уверен в этом ...)