긴 게시물에 대해 미리 사과하고 시간을 할애 해 주신 모든 분들께 감사드립니다. 포스트 끝에 완전한 작업 예제.
내 코드의 동작을 이해하는 데 도움이 필요합니다. 저는 두 개의 간단한 그래프 지향 클래스를 작성했습니다. 하나는 노드 용이고 다른 하나는 그래프 자체 용입니다. 그래프에있어서의 노드의 인스턴스를 추적하는 사전을 가지고 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 의 이웃이 3 의 이웃보다 먼저 입력 bad
되었지만 다른 bad
이웃 이후 에 입력 되었기 때문에 이것은 줄 순서가 진행되는 한 텍스트 파일 입력과 만 관련이 없습니다 .printNeighborsNeighbors(4)
, 9
그리고 6
그들의 이웃이 올바르게 나열하지만이 1
나와는 아무 상관이 없습니다. 그래서 그것은 전부 아니면 전무 오류 인 것 같습니다. 진정한 이웃을 모두 가지고 있거나 이웃 목록이 전혀 없습니다. 이 부분은 가장 혼란 스럽습니다. 객체를 덮어 쓰는 문제가 아닙니다. 이것은 일종의 C ++ 스타일 객체 슬라이싱처럼 느껴집니다.항상 그래프 사전을 살펴보면이 문제를 쉽게 해결할 수 있지만 여기서 무슨 일이 일어나고 있는지 알고 싶습니다. 파이썬이 이러한 객체를 처리하는 방법에 대해 중요한 것을 오해하고있는 것 같습니다.
시도 할 사항에 대한 수정이나 제안에 감사드립니다.
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)
문제는 인덱스별로 노드 개체의 고유성을 적용하고 있다는 것입니다. neighbourNodes () 메서드가 호출되면 필요한 경우에만 self.nodes ()에 추가하는 새로 생성 된 Node 인스턴스를 가져옵니다. 이는 "올바른"것입니다. 인덱스 당 하나의 Node 인스턴스 만 기록합니다. 그러나 먼저 Node.createNeighbor () 메서드에 전달하고 해당 폐기 인스턴스가 노드의 이웃으로 기록된다는 점을 제외하고는 여전히 버릴 Node의 새 인스턴스를 만들고 있습니다. 결과적으로 이웃 관계의 한 방향 만 기록됩니다.
가능한 수정 사항은 다음과 같습니다.
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에 추가 할 수 있습니다.이 메서드는 노드 객체가 이미 존재하는 경우 반환하거나 아직 존재하지 않는 경우 새 객체를 생성 (등록)합니다. 그런 다음 Node 생성자를 비공개 (아마도 Python에서는 그렇게 할 방법이 없음)하여 Graph 외에는 아무도 만들 수 없도록합니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다