GraphGists

道路、节点和汽车

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

我在 SkillsMatter 上分享了关于此图示的演讲，您可以在线观看 https://bit.ly/neo4jrna

灵感 顶部

导航与我的日常工作无关，但我经常使用卫星导航。这个图示的灵感来自 Waze，这是一个卫星导航系统，允许用户编辑地图。很容易在图的结构中看到地图，但是它如何工作呢？

我决定创建一个图示，可以模拟地图以及存储的数据如何被查询以允许某人导航该地图。为了简单起见，以及图示处理能力的限制，将限制要绘制的区域。

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

数据 顶部

互联网上有很多关于各种图示应用的数据源。值得查看各种来源以了解哪一个最适合您的需求，或者组合不同的来源。可以使用各种可用工具从诸如 csv 文件之类的源导入数据。Rik Van Bruggen 的博客 (https://blog.bruggen.com/) 是关于如何执行此操作的教程的良好来源。

来源 顶部

我最初使用维基百科和谷歌地图作为我的数据源，但后来发现可编辑的 Waze 地图包含我需要的距离信息，而这些信息我之前是根据维基百科和谷歌地图的组合估算的。

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

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

从哪些路口可以到达切尔西？ 顶部

注意：如果低于 10 的路口名称以 0 开头存储（例如 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

从 48 Addlestone Moor London Road 驾驶到 123 Staines Road 需要多长时间？ 顶部

这假设您始终以最大速度行驶，但在应用程序中需要进行调整。这可以通过假设在 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

返回顶部

控制台

单击查询一上的绿色播放按钮以设置控制台的数据库，并尝试使用您自己的查询。返回顶部