我一辈子都搞不懂为什么我的代码会抛出一个KeyError。我觉得这些值应该在那里-我在第一个for loop
中添加了它们,并且我添加它们到的列表不是空的(我已经用print语句检查过了)。那么为什么第54行总是无情地抛出一个键错误呢?我肯定我忽略了一些东西,但是在工作了一整天之后,我被困了。在
使用的函数(graph()和shortest_path()等)是here。在
edgeData具有以下结构:
{string value: [list of string values that are groupings of the values in the dictionary's keys]}
tagUsers具有以下结构:
^{pr2}$提前谢谢。在
from collections import defaultdict, deque
import json
class Graph(object):
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
def dijkstra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
try:
weight = current_weight + graph.distances[(min_node, edge)]
except:
continue
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
def shortest_path(graph, origin, destination):
visited, paths = dijkstra(graph, origin)
full_path = deque()
_destination = paths[destination]
while _destination != origin:
full_path.appendleft(_destination)
_destination = paths[_destination]
full_path.appendleft(origin)
full_path.append(destination)
return visited[destination]
if __name__ == '__main__':
edgeData = {'a': ['c', 'd'], 'b': ['d'], 'c': ['d'], 'd': ['a', 'b']}
tagUsers = {'hashtag1': ['a', 'c', 'd'], 'hashtag2': ['b'], 'hashtag3': ['b', 'd']}
shortestpaths = {}
graph = Graph()
users = []
# calls function, builds graph with data in edgeData
for key, value in edgeData.items():
users.append(key)
graph.add_node(key)
for each in value:
graph.add_edge(key, each, 1)
# determines how many users used each hashtag
hashtags = {}
for key, value in tagUsers.items():
tmpTags = key
count = len(value)
hashtags[key] = count
# normally determines which hashtag was used the most
# Here, it's pre-set
topTag = ['hashtag1']
# calculates the shortest path from each user to another user
# that uses the most-used hashtag
count = 0
if count < 1:
for key, value in edgeData.items():
tmpDict = {}
for tag in topTag:
shortest = 10000
for k, v in tagUsers.items():
if k == tag:
for each in v:
flag = False
if key != each
flag = True
tmpShort = shortest_path(graph, key, each)
if tmpShort < shortest:
shortest = tmpShort
if flag:
tmpDict[tag] = shortest
shortestpaths[key] = tmpDict
count += 1
目标是使shortestpaths
中的数据包含每个用户,
与另一个使用顶部标签的用户的最短距离
函数调用引用了这段代码,这是由github上的mdsrosa提供的。在
具体地说,在shortest_path()
中的``u destination=paths[\u destination]处抛出错误
向
shortest_path
添加一些日志记录会显示问题:结果:
^{pr2}$您需要处理原点和终点相同的边缘情况
一种选择是在调用
shortest_path
之前添加检查if key == each
同时将循环变量从
k
、v
、key
、value
、each
更改为描述实际数据的内容相关问题 更多 >
编程相关推荐