python - 检查图形路径是否有效时出现 KeyError
问题描述
我正在实现一个图形类,并想编写一个计算给定路径是否有效的函数。我的 is_path_valid 函数出现关键错误。
我的图表示为 {a:{b:c}} 其中 a 和 b 是相互连接的顶点,c 是边的权重
鉴于:
{0: {1: 5.0, 2: 10.0}, 1: {3: 3.0, 4: 6.0}, 3: {2: 2.0, 4: 2.0, 5: 2.0}, 4: {6: 6.0}, 5: {6: 2.0}, 7: {9: 1.0}, 8: {7: 2.0, 9: 4.0}}
顶点 2 到 3 是有效路径。
我的图表类:
class Graph:
def __init__(self, n):
"""
Constructor
:param n: Number of vertices
"""
self.order = n
self.size = 0
self.vertex = {}
def insert_edge(self, u, v, w): #works fine
if u in self.vertex and v < self.order:
if not v in self.vertex[u]:
self.vertex[u][v] = w
self.size += 1
elif u not in self.vertex and u < self.order and v < self.order:
self.vertex[u] = {}
self.vertex[u][v] = w
self.size += 1
else:
raise IndexError
def is_path_valid(self, path):
while True:
try:
s = path.pop(0)
except IndexError:
break
if path:
d = path.pop(0)
if s not in self.vertex and d not in self.vertex[s]: #ERROR
return False
s = d
return True
我的主要功能:
def main():
g = Graph(10)
g.insert_edge(0,1,5.0)
g.insert_edge(0,2,10.0)
g.insert_edge(1,3,3.0)
g.insert_edge(1,4,6.0)
g.insert_edge(3,2,2.0)
g.insert_edge(3,4,2.0)
g.insert_edge(3,5,2.0)
g.insert_edge(4,6,6.0)
g.insert_edge(5,6,2.0)
g.insert_edge(7,9,1.0)
g.insert_edge(8,7,2.0)
g.insert_edge(8,9,4.0)
True(g.is_path_valid([0, 2]))
True(g.is_path_valid([2, 3]))
True(g.is_path_valid([0, 2, 3]))
False(g.is_path_valid([0, 1, 8]))
False(g.is_path_valid([0, 4, 3]))
print(g.vertex) #to see the graph
print(g.is_path_valid([2,3]))
if __name__ == '__main__':
main()
我的错误:
if s not in self.vertex and d not in self.vertex[s]:
KeyError: 2
解决方案
您只是将弧线和边缘混合在一起,这会导致一些意想不到的事情发生,您必须在两者之间进行选择。
另一方面,您可以有一个有向图,并且仍然有一个添加“边”的函数,因为它将添加弧(u,v)和(v,u)。我在引号中有边,因为它们不是真正的边(术语边仅在无向图中有意义)。
from collections import defaultdict
class Graph:
def __init__(self):
self._arcs = defaultdict(dict)
def insert_arc(self, u, v, w):
self._arcs[u][v] = w
def is_arc(self, u, v):
return u in self._arcs and v in self._arcs[u]
def is_path_valid(self, path):
for u, v in zip(path, path[1:]):
if not self.is_arc(u, v):
return False
return True
# We add the notion of "edges" with the following methods:
def insert_edge(self, u, v, w):
self.insert_arc(u, v, w)
self.insert_arc(v, u, w)
@property
def edges(self):
return {((u, v), w) for u, Nu in self._arcs.items() for v, w in Nu.items() if self.is_edge(u, v)}
def is_edge(self, u, v):
is_symetric = self.is_arc(u, v) and self.is_arc(v, u)
if not is_symetric:
return False
return self._arcs[u][v] == self._arcs[v][u]
您现在可以向图形添加边或弧:
g = Graph()
# This is an arc:
g.insert_arc(1, 8, 1.)
# Weight is not symmetric but this still look like an edge:
g.insert_arc(1, 0, 3.)
g.insert_arc(0, 1, 2.)
# These are all symmetric (ie. "edges")
g.insert_edge(1, 2, 7.)
g.insert_edge(2, 3, 5.)
g.insert_edge(0, 3, 13.)
# we added an arc (1, 8):
print(g.is_path_valid([1, 8])) # True
print(g.is_path_valid([8, 1])) # False
# All true:
print(g.is_path_valid([0, 3]))
print(g.is_path_valid([2, 3]))
print(g.is_path_valid([0, 1, 2, 3, 0]))
# Adding one step make this false since (0, 2) doesn't exist:
print(g.is_path_valid([0, 1, 2, 3, 0, 2]))
我们可以使用该edges
属性找到所有“边”(在两个方向上具有相同权重的对称弧):
>>> print(g.edges)
{((3, 0), 13.0), ((3, 2), 5.0), ((2, 1), 7.0), ((1, 2), 7.0), ((2, 3), 5.0), ((0, 3), 13.0)}
请注意如何(0, 1)
不是边集的一部分,这是因为链接存在于两个方向但权重不同。弧(1, 8)
显然不在这里,因为(8, 1)
它不是图表的一部分。
推荐阅读
- javascript - vue.js mapbox 地图未显示
- ios - 如何知道一个 URL 是否有效并检查它是否会在 swift 中打开
- android - 无法在 firebase 数据库中插入数据
- ios - 在 SwiftUI 中将文本和图像添加到按钮
- python - DBAPI 错误;SSL SYSCALL 错误:运行 docker 映像时检测到 EOF
- node.js - 在 node.js 服务器中的 url 中搜索查询
- java - 使用这个想法,我应该如何将 tool.jar 与 jdk 13 一起使用
- c++ - QtQuick2 视频渲染质量和嵌入 QVideoWidget 到 Qml
- material-ui - Material-ui网格对齐,不垂直居中
- php - 确定说话声音的基频