python - 从 shortest_distance 函数返回的距离图缺少某些顶点的条目
问题描述
我在 postgres 数据库中有一个网络,我可以在其中使用 pgrouting 扩展进行路由。我已将其读入 mem,现在想计算距特定起始节点 0.1 小时内所有节点的距离:
dm = G.new_vp("double", np.inf)
gt.shortest_distance(G, source=nd[102481678], weights=wgts, dist_map = dm, max_dist=0.1)
其中 wgts 是包含每条边权重的 EdgePropertyMap,nd 是从外部 id 获取顶点索引的反向映射。
在 pgRouting 中,这提供了 349 个可达节点,仅使用图形工具 328。结果或多或少相同(例如,最远的节点相同且成本完全相同,两个列表中存在的节点具有相同的距离),但图-工具距离图似乎错过了某些节点。奇怪的是,我找到了一个标有距离的死胡同节点(从下方第二个),但连接死胡同与外界的节点却不见了。看起来很奇怪,因为如果无法到达连接节点,那么死胡同也将无法到达。
我已经编译了一个 MWE:https ://gofile.io/d/YpgjSw
下面是python代码:
import graph_tool.all as gt
import numpy as np
import time
# construct list of source, target, edge-id (edge-id not really used in this example)
l = []
with open('nw.txt') as f:
rows = f.readlines()
for row in rows:
id = int(row.split('\t')[0])
source = int(row.split('\t')[1])
target = int(row.split('\t')[2])
l.append([source, target, id])
l.append([target, source, id])
print len(l)
# construct graph
G = gt.Graph(directed=True)
G.ep["edge_id"] = G.new_edge_property("int")
n = G.add_edge_list(l, hashed=True, eprops=G.ep["edge_id"])
# construct a dict for mapping outside node-id's to internal id's (node indexes)
nd = {}
i = 0
for x in n:
nd[x] = i
i = i + 1
# construct a dict for mapping (source, target) combis to a cost and reverse cost
db_wgts = {}
with open('costs.txt') as f:
rows = f.readlines()
for row in rows:
source = int(row.split('\t')[0])
target = int(row.split('\t')[1])
cost = float(row.split('\t')[2])
reverse_cost = float(row.split('\t')[3])
db_wgts[(source, target)] = cost
db_wgts[(target, source)] = reverse_cost
# construct an edge property and fill it according to previous dict
wgts = G.new_edge_property("double")
i = 0
for e in G.edges():
i = i + 1
print i
print e
s = n[int(e.source())]
t = n[int(e.target())]
try:
wgts[e] = db_wgts[(s, t)]
except KeyError:
# this was necessary
wgts[e] = 1000000
# calculate shortest distance to all nodes within 0.1 total cost from source-node with outside-id of 102481678
dm = G.new_vp("double", np.inf)
gt.shortest_distance(G, source=nd[102481678], weights=wgts, dist_map = dm, max_dist=0.1)
# some mumbo-jumbo for getting the result in a nice node-id: cost format
ar = dm.get_array()
idxs = np.where(dm.get_array() < 0.1)
vals = ar[ar < 0.1]
final_res = [(i, v) for (i,v) in zip(list(idxs[0]), list(vals))]
final_res.sort(key=lambda tup: tup[1])
for x in final_res:
print n[x[0]], x[1]
# output saved in result_missing_nodes.txt
# 328 records, should be 349
为了说明(其中一个)缺失节点:
>>> dm[nd[63447311]]
0.0696234786274957
>>> dm[nd[106448775]]
0.06165528930577409
>>> dm[nd[127601733]]
inf
>>> dm[nd[100428293]]
0.0819900275163846
>>>
这似乎不可能,因为这是网络的本地布局,标签是上面引用的 id:
解决方案
这是一个数值精度问题。您的边缘权重 (1e-6) 非常低,而值非常大 (1000000),这会导致差异丢失到有限精度。如果将所有值 1000000 (我假设它的意思是无限权重)替换为numpy.inf
,您实际上会得到更稳定的计算,并且在您的示例中不会丢失节点。
一个更好的选择是使用边缘过滤器实际删除“无限权重”边缘:
u = GraphView(G, efilt=wgts.fa < 1000000)
并计算距离。
推荐阅读
- java - 如何在 Intelij IDEA 上使用 Swing UI 连接 SQL 表
- javascript - Firebase 函数 snapshot.docs.maps 不是函数
- javascript - 是否可以避免 Flow 上较长的相对导入路径?
- javascript - 语音识别:recognition.onresult() 不触发
- mysql - 为什么 MySQL8.0 在这种情况下使用文件排序?
- python - 有没有办法匹配正则表达式中的()括号
- python - 如何为 pygame 分离一个图块集?
- javascript - 如何让下一个和上一个按钮在我的 javascript 代码上工作
- python-3.x - 输入是否有 end= 等效项?
- c# - 在桌面/Web 聊天视图中,对会议组的 Bot 提及为空白