GraphGists

道路、节点和汽车

或“卫星导航如何使用图数据库”

我关于这个要点的演讲可在SkillsMatter在线观看 https://bit.ly/neo4jrna

灵感 顶部

导航与我的日常工作无关，但我经常使用卫星导航。这个要点受到Waze（一个允许用户编辑地图的卫星导航系统）的启发。地图结构很容易看出是图，但它如何工作呢？

我决定创建一个可以模拟地图并探索如何查询存储的数据以实现导航的要点。为了简单起见和要点处理能力所限，地图覆盖区域将受到限制。

为此，这个要点将创建英国M3和M25高速公路部分路段以及一些连接城镇的表示。

数据 顶部

互联网上有很多适用于各种要点应用的数据源。值得查看各种来源，看看哪一个最符合您的需求，或者组合不同的来源。可以使用各种可用工具从csv文件等来源导入数据。Rik Van Bruggen的博客（https://blog.bruggen.com/）提供了关于如何执行此操作的优秀教程。

来源 顶部

我最初使用维基百科和Google地图作为我的数据源，但后来发现可编辑的Waze地图包含了所需的距离信息，而这些信息我之前是通过结合维基百科和Google地图来估计的。

关于速度数据，Waze似乎没有存储，或者没有向用户提供。我结合了有根据的猜测（M级公路通常有3条车道，限速70英里/小时）和Google Maps街景，查看速度标志，并将数据输入到我的道路关系中。

Waze也可能通过使用用户的行驶距离和时间来计算速度，或者他们可能不使用这个方法，只根据用户收集的过去数据来估计时间。

模型 顶部

最初模型相当简单，将地点和路口表示为节点，道路表示为关系，但随着时间的推移，模型演变为将路口表示为一系列由道路连接的出口和入口。

然后它再次演变，将地点也包含进来，并具有邮政编码和门牌号等各种属性。这在下面的图表中进行了建模，只使用了两个入口和两个出口（实际上只有两条道路）。

但这还不够好。它没有考虑到高速公路上的匝道或行车道（司机实际上没有离开高速公路）。每个入口都需要连接到每个出口才能考虑到这一点。因此，路口模型再次演变为以下形式（为清晰起见，去除了属性和地点）。

图填充 顶部

点击+号查看完整的Cypher设置脚本。

图可视化 顶部

这显示了上述设置脚本的结果。有关图可视化的更多信息，请参阅（链接到skillz matter）。

应用

这个图模型允许通过查询提取数据，并计算导航路线。

简单导航 顶部

我想去TW16 5AD，有哪些地址选项？ 顶部

用户可能输入“tw16 5ad”或“TW16 5AD”或“tw165ad”或“TW165AD”或类似“Tw16 5aD”的任何内容。应用需要考虑到这一点。最简单的方法是在查询提交之前去除输入中的空格，并在数据库中存储不带空格的邮政编码。应用中也可以考虑大小写（例如，如果数据库中存储的是小写，则转换为小写），但我在这个正则表达式中已经处理了。

在一个应用中，可以先向用户提供道路名称列表，然后提示他们选择门牌号。

MATCH (l:Location)
WHERE l.postcode =~ '(?i)tW16 5aD'
RETURN l.number AS number, l.street AS street, l.local AS local, l.postcode AS postcode
ORDER BY l.number

从哪些路口可以到Chertsey？ 顶部

注意：如果编号小于10的路口名称存储时带有前导零（例如J09），我就可以按j.name而不是数字排序。

MATCH (j:Junction)-[r*2]-(l:Location)
WHERE l.local = 'Chertsey'
WITH j
order by j.number
RETURN collect(distinct j.name) as junctions

复杂导航 顶部

从KT15 2QH到TW16 5AD的最短路线是什么？ 顶部

这个查询计算指定两个节点之间的最短路线。这是基于图中遍历次数的最短路线，而不是基于遍历关系上的距离属性。这是图中的最短路线，并非现实中的最短路线。下一个问题讨论实际距离。

由于可能存在多个起点和终点节点，我使用了LENGTH()、ORDER BY和LIMIT来仅返回最短路线（按遍历次数计算）。我在RETURN语句之前执行此操作，这样就不必返回计数了，如果是在RETURN语句之后按计数排序，则必须返回计数。

MATCH p=shortestPath((a:Location)-[r*]->(b:Location))
WHERE a.postcode = 'KT15 2QH'
AND b.postcode = 'TW16 5AD'
WITH p,relationships(p) AS r, length(relationships(p)) AS count
ORDER BY count
LIMIT 1
RETURN p AS route

从KT15 2QH的49号到TW16 5AD的125号有多远？ 顶部

这个查询通过将最短路径中所有关系上的距离属性值相加来计算指定两个节点之间的距离。最短路径是根据从一个节点到另一个节点的遍历次数计算的。如果通过将这两个节点之间所有可能路径上的距离属性值相加来计算，这可能并非实际的最短路径。这是可以做到的，但在Neo4j Gist系统中不行。以下代码可以在正常的Neo4j数据库中工作。

MATCH (a:Location)-[roads*]->(b:Location)
WHERE a.postcode = 'KT15 2QH' AND a.number = 49
AND b.postcode = 'TW16 5AD' AND b.number = 125
WITH reduce(d=0, r in roads | d + r.km) as km
RETURN km, round(km) as rounded
ORDER BY km DESC
LIMIT 1
MATCH p=shortestPath((a:Location)-[r*]->(b:Location))
WHERE a.postcode = 'KT15 2QH' AND a.number = 49
AND b.postcode = 'TW16 5AD' AND b.number = 125
WITH p, length(relationships(p)) AS count
ORDER BY count
LIMIT 1
WITH relationships(p) AS roads
WITH reduce(d=0, r in roads | d + r.km) as km
RETURN km, round(km) as rounded

小数注意事项：相加浮点距离值会产生相当多的小数位。这可以在实现此查询的应用中进行四舍五入。Cypher确实提供了round()、floor()和ceiling()函数，但它们都四舍五入到整数（没有小数位），并且无法指定小数位数。

Chertsey和Sunbury-on-Thames之间的平均限速是多少？ 顶部

这将根据道路数量和它们的速度计算平均速度（单位为公里/小时）。它没有考虑道路长度。请参阅以下查询了解加权平均速度。

MATCH p=shortestPath((a:Location)-[r*]-(b:Location))
WHERE a.local = 'Chertsey' AND b.local = 'Sunbury-on-Thames'
WITH relationships(p) AS roads
ORDER BY length(roads)
LIMIT 1
WITH roads, length(roads) AS l, reduce(d=0, r in roads | d + r.speed) as total
RETURN total / l AS average_kph

加权平均速度是多少？ 顶部

所有道路（关系）的长度不同，因此在计算此路线的平均速度时必须考虑到这一点。加权平均速度会考虑速度、距离和时间。

MATCH p=shortestPath((a:Location)-[r*]-(b:Location))
WHERE a.local = 'Chertsey' AND b.local = 'Sunbury-on-Thames'
WITH relationships(p) AS roads
ORDER BY length(roads)
LIMIT 1
WITH reduce(d=0, r in roads | d + (r.speed*r.km)) as weighted, roads
WITH reduce(d=0, r in roads | d + (r.km)) as totalkm, weighted
WITH weighted / totalkm AS average_kph
RETURN average_kph, round(average_kph) AS rounded_average_kph, average_kph * 0.621371 as mph, round(average_kph) * 0.621371 as rounded_mph

从Addlestone Moor London Road 48号开车到Staines Road 123号需要多长时间？ 顶部

这假设您全程都以最高速度行驶，但在实际应用中需要进行调整。这可能通过假设在70英里/小时的限速下行驶60英里/小时，或在30英里/小时的限速下行驶25英里/小时来实现。一些卫星导航系统允许用户自定义这些数值。

MATCH p=shortestPath((a:Location)-[r*]-(b:Location))
WHERE a.number = 48 AND a.street = 'Addlestone Moor'
AND b.number = 123 AND b.street = 'Staines Road'
WITH relationships(p) AS roads
WITH reduce(d=0.0, r in roads | d + ((r.km*0.62)/r.speed)) as t
WITH floor(t) AS hours, t
WITH (t-hours)*60 AS minutes, hours
RETURN round(hours) + ':' + (CASE WHEN minutes < 10 THEN '0' ELSE '' END) + round(minutes) as time

高峰时段呢？ 顶部

这考虑到了大多数道路在高峰时段因车辆数量较多而速度较慢的情况。应用程序会定义高峰时段，从而知道应该运行哪个查询。

MATCH p=shortestPath((a:Location)-[r*]-(b:Location))
WHERE a.number = 48 AND a.street = 'Addlestone Moor'
AND b.number = 123 AND b.street = 'Staines Road'
WITH relationships(p) AS roads
WITH reduce(d=0.0, r in roads | d + ((r.km*0.62)/r.peak)) as t
WITH floor(t) AS hours, t
WITH (t-hours)*60 AS minutes, hours
RETURN round(hours) + ':' + (CASE WHEN minutes < 10 THEN '0' ELSE '' END) + round(minutes) as time

如果发生事故或其他延误怎么办？ 顶部

这是非高峰时段，要切换到高峰时段，只需将r.speed更改为r.peak。应用程序会定义高峰时段，从而知道应该运行哪个查询。考虑了一位数分钟的情况。解释添加了哪些延误以及如何考虑这些延误。如果放在未来部分，请链接到路口延误。

MATCH p=shortestPath((a:Location)-[r*]-(b:Location))
WHERE a.number = 48 AND a.street = 'Addlestone Moor'
AND b.number = 123 AND b.street = 'Staines Road'
WITH relationships(p) AS roads, nodes(p) AS junc
WITH junc, reduce(d=0.0, r in roads | d + (CASE WHEN has(r.delay)
											  THEN ((r.km*0.62)/r.delay)
											  ELSE ((r.km*0.62)/r.speed) END)) as t
WITH floor(t) AS hours, t
WITH (t-hours)*60 AS minutes, hours
RETURN round(hours) + ':' + (CASE WHEN minutes < 10
								  THEN '0'
								  ELSE '' END) + round(minutes) as revised_time

返回顶部

控制台

点击第一个查询旁边的绿色播放按钮，为控制台设置数据库，然后尝试您自己的查询。 返回顶部

© . All rights reserved.