由shortest_distance函数返回的距离图遗漏了某些顶点的条目。

Question

我在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个可到达的节点，使用graph-tool只有328个。结果大致相同（例如最远的节点是相同的，成本完全相同，两个列表中存在的节点有相同的距离），但graph-tool距离图似乎只是错过了某些节点。诡异的是，我找到了一个标有距离的暗道节点（下图第二个），但连接暗道和外界的节点却不见了。这似乎很奇怪，因为如果连接节点无法到达，那么暗道也将无法到达。

我编译了一个MWE。https: /gofile. iodYpgjSw.

下面是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的。

Answer 1

这是一个数值精度问题。你的边缘权重很低（1e-6），再加上非常大的值（1000000），这就会导致差异损失到有限的精度。如果你把所有的值1000000(我认为这意味着无限的重量)替换为 numpy.inf在你的例子中，你实际上得到了一个更稳定的计算，并且没有丢失节点。

一个更好的选择是使用边缘过滤器去除 "无限重 "的边缘。

u = GraphView(G, efilt=wgts.fa < 1000000)

然后计算其距离