我正在实现一个图类,并希望编写一个函数来计算给定路径是否有效。我的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)
不是图的一部分。