Хранение объектов в словарях экземпляра класса имеет неожиданные результаты

Question

Извините заранее за длинный пост и спасибо всем, у кого есть время, чтобы взглянуть. Полный рабочий пример в конце сообщения.

Я хотел бы, чтобы некоторые из них помогли понять поведение моего кода. Я написал два простых класса, ориентированных на граф, один для узлов и один для самого графа. График имеет словарь для отслеживания экземпляра узла в соответствии с его index, self.nodes, и узел ведет список соседей, self.neighbors (эти self's для Graph и Node соответственно).

Что странно, что я всегда могу получить полный список соседей узла, а пройдя через Graph экземпляр nodes словаря, но если я пытаюсь получить сосед соседей путем доступа к узлу через neighbors список другого узла, я часто получаю узел без соседей, отображающий неверную информацию. Например, когда я прочитал в и обрабатывать граф, я могу распечатать каждый узел и его соседей отлично, путем вызова Graph экземпляров игровая listNodes(), что дает мне это на одном примере график:

(i = 1, neighbors: 5 2 4 3) 
(i = 2, neighbors: 1) 
(i = 3, neighbors: 1 8 9) 
(i = 4, neighbors: 1 9 6) 
(i = 5, neighbors: 1) 
(i = 6, neighbors: 4 7) 
(i = 7, neighbors: 6) 
(i = 8, neighbors: 3) 
(i = 9, neighbors: 4 3) 

Так что я могу получить доступ к соседи узла, когда я обращаюсь к нему непосредственно из словаря self.nodes в экземпляре графа. Однако я не могу получить доступ к соседям соседей узла через список соседей узла. Например, когда я бегу printNeighborsNeighbors(3), реализована следующим образом:

def printNeighborsNeighbors(self, start_num): 
    node = self.nodes[start_num] 
    print(node.neighbors) 

здесь выход:

[(i = 1, neighbors:), (i = 8, neighbors: 3), (i = 9, neighbors:)] 

Это указывает на то, что узел 1 и 9 имеют нулевые соседей, но это совершенно неправильно. График выглядит следующим образом:

Вот упорядоченность для ввода соседей:

5 1 
1 2 
1 4 
1 3 
3 8 
4 9 
3 9 
4 6 
6 7 

Вот являются реализация класса:

class Node: 
    def __init__(self, i): 
     self.index = i 
     self.neighbors = [] 

    def createNeighbor(self, neighbor): 
     self.neighbors.append(neighbor) 

    def __str__(self): 
     neighbors = [str(n.index) for n in self.neighbors] 
     return "(i = %d, neighbors: %s)"%(self.index, " ".join(neighbors)) 

    def __repr__(self): 
     return str(self) 

и

class Graph: 
    def __init__(self): 
     self.nodes = defaultdict(lambda: False) 

    def neighborNodes(self, node, neighbor): 
     if not self.nodes[node.index]: 
      self.nodes[node.index] = node 

     if not self.nodes[neighbor.index]: 
      self.nodes[neighbor.index] = neighbor 

     self.nodes[node.index].createNeighbor(neighbor) 
     self.nodes[neighbor.index].createNeighbor(node) 

    def printNeighborsNeighbors(self, start_num): 
     node = self.nodes[start_num] 
     print(node.neighbors) 
     for n in node.neighbors: 
      print(n.neighbors) 

    def listNodes(self): 
     for node in self.nodes.values(): 
      print(node) 

Вот что я имею в виду:

• Это не только относится к входного текстового файла влево-вправо упорядоченности на каждой линии, потому что 3 имеет два «плохих» соседей (где информация теряется) и один был вход в 1 3, а другой вход, как 3 9
• Это не только относится к входу текстового файла, насколько линия упорядочения идет, потому что good сосед 3 был вход, прежде чем один bad сосед из 3, но после того, как другие bad сосед.
• Когда я запустил printNeighborsNeighbors(4), 9 и 6, их соседи правильно указаны, но 1 ничего не указана. Таким образом, это кажется ошибкой «все или ничего». Либо у вас есть все истинные соседи, либо у вас просто нет списка соседей. Эта часть наиболее запутанна.Это не вопрос перезаписи объекта, это больше похоже на какой-то кусок объекта стиля C++.

Я могу легко обойти эту проблему, всегда просматривая словарь графиков, но я хотел бы знать, что здесь происходит. Похоже, я недопонимаю что-то важное о том, как Python обрабатывает эти объекты.

Спасибо за любые исправления или предложения о том, что попробовать.

---

следующее предложение MK здесь это рабочий пример:

input.txt

1 
9 9 
5 1 
1 2 
1 4 
1 3 
3 8 
4 9 
3 9 
4 6 
6 7 
8 

и я просто запустил эту .py поэтому он должен работать:

import copy 
from collections import defaultdict 


class Node: 
    def __init__(self, i): 
     self.index = i 
     self.neighbors = [] 
     self.currentPath = [] 

    def createNeighbor(self, neighbor): 
     self.neighbors.append(neighbor) 

    def __str__(self): 
     neighbors = [str(n.index) for n in self.neighbors] 
     return "(i = %d, neighbors: %s)"%(self.index, " ".join(neighbors)) 

    def __repr__(self): 
     return str(self) 

class Graph: 
    def __init__(self): 
     self.nodes = defaultdict(lambda: False) 

    def neighborNodes(self, node, neighbor): 
     if not self.nodes[node.index]: 
      self.nodes[node.index] = node 

     if not self.nodes[neighbor.index]: 
      self.nodes[neighbor.index] = neighbor 

     self.nodes[node.index].createNeighbor(neighbor) 
     self.nodes[neighbor.index].createNeighbor(node) 

    def printNeighborsNeighbors(self, start_num): 
     node = self.nodes[start_num] 
     print(node.neighbors) 
     #for n in node.neighbors: 
     # print(n.neighbors) 

    def listNodes(self): 
     for node in self.nodes.values(): 
      print(node) 


f = open('input.txt', 'r') 
t = int(f.readline()) 


for _ in range(t): 

    graph = Graph() 
    n, m = f.readline().split() 
    n = int(n) 
    m = int(m) 
    for _ in range(m): 
     x, y = f.readline().split() 
     x = int(x) 
     y = int(y) 
     nodeX = Node(x) 
     nodeY = Node(y) 
     graph.neighborNodes(nodeX, nodeY) 
    s = int(f.readline()) 

    print("running graph.listNodes") 
    graph.listNodes() 
    print("running print neighbors neighbors") 
    graph.printNeighborsNeighbors(4) 

Answer 1

Проблема заключается в том, что вы применяете уникальность объектов узла по индексу. Когда вызывается метод nodeNodes(), он получает вновь созданный экземпляр Node, который вы добавляете только к self.nodes(), если это необходимо, что является «правильным»: он будет записывать только один экземпляр узла для индекса. Но вы все еще создаете новый экземпляр узла, который вы выбросите, за исключением того, что вы сначала передаете его методу Node.createNeighbor(), и экземпляр выброса будет записан как соседний узел. В результате регистрируется только одно направление отношения соседства.

Вот один из возможных решений:

if not self.nodes[node.index]: 
    self.nodes[node.index] = node 
else: 
    node = self.nodes[node.index] 

if not self.nodes[neighbor.index]: 
    self.nodes[neighbor.index] = neighbor 
else: 
    neighbor = self.nodes[neighbor.index] 

Но мне не нравится это. На самом деле вам нужно изменить его, чтобы прекратить создавать экземпляры отбрасывания, это не хорошо для памяти, производительности, удобочитаемости и правильности. Вы можете добавить метод, называемый getNode (n) в Graph, который вернет объект узла, если он уже существует, или создать (и зарегистрировать) новый, если он еще не существует. Затем вы создадите частные конструкторы узлов (вероятно, не сможете сделать это на Python), чтобы никто другой, кроме Graph, не мог их создать.