为什么我的字典实现中会出现Python KeyError？

Question

我不知道为什么，在我实现的这个图中，我无法找到正确的键。我总是遇到一个叫做KeyError的错误，这看起来是因为字典的实现有问题。我已经研究了好几个小时，但还是搞不清楚问题出在哪里。

> KeyError                                  Traceback (most recent call
> last)
> C:\Users\AppData\Local\Enthought\Canopy\App\appdata\canopy-1.4.0.1938.win-x86_64\lib\site-packages\IPython\utils\py3compat.pyc
> in execfile(fname, glob, loc)
>     195             else:
>     196                 filename = fname
> --> 197             exec compile(scripttext, filename, 'exec') in glob, loc
>     198     else:
>     199         def execfile(fname, *where):
> 
> C:\Users\ps5.py in <module>()
>      69     
>      70 
> ---> 71 bigMap = load_map(mapFile)
>      72 
> 
> C:\Users\ps5.py in load_map(mapFilename)
>      51         e1 = WeightedEdge(nx, ny, ex, ey)
>      52         
> ---> 53         g.addEdge(e1)
>      54     return g
>      55     
> 
> C:\Users\graph.py in addEdge(self, edge)
>      74         if not (src.getName() in self.nodes and dest.getName() in self.nodes):
>      75             raise ValueError('Node not in graph')
> ---> 76         self.edges[src].append([dest, (edge.getTotalDistance(), edge.getOutdoorDistance())])
>      77 
>      78     def __str__(self):
> 
> KeyError: <graph.Node object at 0x00000000080B1A90>


class Node(object): 
    def __init__(self, name): 
        self.name = str(name) 
    def getName(self): 
        return self.name
    def __str__(self): 
        return self.name

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 __str__(self): 
        return str(self.src) + '->' + str(self.dest) 

class WeightedEdge(Edge): 
    def __init__(self, src, dest, totalDistance, outdoorDistance): 
        self.src = src
        self.dest = dest 
        self.totalDistance = float(totalDistance) 
        self.outdoorDistance = float(outdoorDistance) 
    def getWeight(self): 
        return self.weight
    def __str__(self): 
        return str(self.src) + '->' + str(self.dest) + ' (' + \
        str(self.totalDistance) + ', ' + str(self.outdoorDistance) + ')'
    def getTotalDistance(self):
        return self.totalDistance 
    def getOutdoorDistance(self): 
        return self.outdoorDistance

class Digraph(object): 
    def __init__(self): 
        self.nodes = set([])
        self.edges = {} 
    def addNode(self, node): 
        if node.getName() in self.nodes: 
            raise ValueError('Duplicate node') 
        else: 
            self.nodes.add(node.getName()) 
            self.edges[node] = [] 
    def addEdge(self, edge): 
        src = edge.getSource() 
        dest = edge.getDestination() 
        if not(src in self.nodes and dest in self.nodes): 
            raise ValueError('Node not in graph') 
        self.edges[src].append(dest) 
    def childrenOf(self, node): 
        return self.edges[node]
    def hasNode(self, node): 
        return str(node) in self.nodes
    def __str__(self): 
        res = ''
        for k in self.edges: 
            for d in self.edges[k]: 
                res = res + str(k) + '->' + str(d) + '\n'
        return res[:-1]

class Graph(Digraph): 
    def addEdge(self, edge): 
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource()) 
        Digraph.addEdge(self, rev)

class WeightedDigraph(Digraph): 

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

    def __str__(self): 
        res = ''
        for k in self.edges: 
            for d in self.edges[k]:
                res = res + str(k) + '->' + str(d[0]) + ' (' + str(float(d[1][0])) + ', ' + str(float(d[1][1])) + ')' + '\n'
        return res[:-1]

    def childrenOf(self, node): 
        children = [] 
        for child in self.edges[node]: 
            children.append(child[0]) 
        return children

def load_map(mapFilename):
    dataFile = open(mapFilename, 'r')
    g = WeightedDigraph() 
    for line in dataFile: 
        nx, ny, ex, ey = line.split() 
        nx = Node(nx) 
        ny = Node(ny) 
        if not g.hasNode(nx): 
            g.addNode(nx) 
        if not g.hasNode(ny): 
            g.addNode(ny)     
        e1 = WeightedEdge(nx, ny, ex, ey)
        g.addEdge(e1) 
   return g

bigMap = load_map(mapFile) 

Answer 1

看起来你的错误出现在 WeightedDigraph.addEdge(self, edge) 这个地方。

你传入了一个边对象，然后通过 src = edge.getSource() 获取了源节点。通过使用调试工具，我查看了字典 self.edges，发现它的键是以 {<节点对象>: <列表>} 这种格式存在的。

实际的调试视图给了我这样的信息：

self.edges = { <__main__.Node object at 0x10f1d4350>: [] }

如果你想在 Python 的字典中使用一个对象作为键，你需要包含两个函数：

def __hash__(self)

还有

def __eq__(self, other)

这是一个关于这个问题的 Stack Overflow 问题： 自定义类型作为字典键

我做了一个快速的标记，似乎解决了你的键错误。

此外，我强烈建议使用调试工具（pydb (http://bashdb.sourceforge.net/pydb/ 是其中一个调试工具，但很多集成开发环境（IDE）里也内置了调试工具），因为这就是我找到你错误的方法。