Python实现图结构添加边时遇‘节点不在图中’问题求助

Let's figure out why you're getting that "Node not in graph" error when adding edges, and fix it step by step.

The core issue here is how your node class is compared and how you're trying to create edges:

1. Default object equality checks: Python compares objects by memory address by default, not their content. So a new node instance with the same position/value as one already in the graph is seen as a different object, making the graph unable to recognize it.
2. No way to retrieve existing nodes: Your Diagraph class didn't have a method to fetch nodes already added, so you might have been creating new unrecognized nodes when building edges.

Step 1: Fix the node class to support proper equality #

Add __eq__ and __hash__ methods so nodes with identical position and value are treated as the same:

class node(object):
    def __init__(self, position, value):
        self.value = value
        self.position = position

    def getPosition(self):
        return self.position

    def getvalue(self):
        return self.value

    def __str__(self):
        return f'P:{self.position} V:{self.value}'

    # Add these to enable proper equality checks
    def __eq__(self, other):
        if isinstance(other, node):
            return self.position == other.position and self.value == other.value
        return False

    def __hash__(self):
        return hash((self.position, self.value))

Step 2: Add a node retrieval method to Diagraph #

Modify the graph class to let you fetch nodes by their position, so you can use existing nodes when building edges:

class Diagraph(object):
    def __init__(self):
        self.edges = {}

    def addNode(self, node):
        if node in self.edges:
            raise ValueError('Duplicate node')
        else:
            self.edges[node] = []

    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)

    def getChildrenof(self, node):
        return self.edges[node]

    def hasNode(self, node):
        return node in self.edges

    # New method to fetch nodes by position
    def getNodeByPosition(self, position):
        for node in self.edges:
            if node.getPosition() == position:
                return node
        raise ValueError(f'Node not found for position: {position}')

Step 3: Fix the edge class's string representation (optional but helpful) #

Your original __str__ method would throw an error when concatenating tuples and strings. Update it to a readable format:

class edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest

    def getWeight(self):
        return self.dest.getvalue()

    def __str__(self):
        return f"{self.src.getPosition()} -> {self.dest.getPosition()}"

Step 4: Correctly add edges using existing nodes #

Now you can safely connect nodes by fetching the ones already in the graph, matching the structure of Project Euler Problem 18:

# Your existing setup code
mytesttring='''3
7 4
2 4 6
8 5 9 3'''

testlist2=[ list(map(int,elements.split())) for elements in mytesttring.strip().split("\n")]

y=Diagraph()
# Clean up node adding loop to match row/column structure
for row_idx in range(len(testlist2)):
    for col_idx in range(len(testlist2[row_idx])):
        y.addNode(node((row_idx, col_idx), testlist2[row_idx][col_idx]))

# Add edges correctly
for row in range(len(testlist2) - 1):
    # Connect each node to the two nodes directly below it
    for col in range(len(testlist2[row])):
        src_node = y.getNodeByPosition((row, col))
        dest_left = y.getNodeByPosition((row+1, col))
        dest_right = y.getNodeByPosition((row+1, col+1))
        
        y.addEdge(edge(src_node, dest_left))
        y.addEdge(edge(src_node, dest_right))

# Verify the graph
for node in y.edges:
    print(f"{node} has children: {[str(child) for child in y.getChildrenof(node)]}")

Key Fixes Explained #

• The __eq__ and __hash__ methods ensure the graph recognizes identical nodes, even if they're created separately.
• The getNodeByPosition method lets you reuse nodes already in the graph, avoiding the "Node not in graph" error.
• The edge-adding loop follows the triangle structure of Problem 18, connecting each node to its two possible child nodes below it.

内容的提问来源于stack exchange，提问作者rainu