neo4j - Cypher:根据节点属性计算

标签 neo4j cypher

我开发了一个路由系统，通过使用多个移动产品来找到最佳路线，例如。 G。公共(public)交通或拼车。
基本上我有节点，代表公共(public)汽车站、火车站等。这些站包括每天的时间表。此外，我有行人停止。这些停靠点通过关系连接。如果我从步行到公共(public)汽车，或在公共(public)汽车线路之间改变，这种关系称为 SWITCH_TO。如果我在不改变服务线的情况下行驶了几个停靠点，停靠点将通过名为 CONNECTED_TO 的关系连接。如果我想从 A 点到 Z 点，并且必须在 C 站换乘另一条服务线在 D 站，路径将如下所示:

(A:Stop:Pedestrian)-[SWITCH_TO{switchTime:2}]->
(A:Stop:Bus{serviceLine:1})-[CONNECTED_TO{travelTime:5}]->
(B:Stop:Bus{serviceLine:1})-[CONNECTED_TO{travelTime:6}]->
(C:Stop:Bus{serviceLine:1})-[SWITCH_TO{switchTime:2}]->
(C:Stop:Pedestrian)-[CONNECTED_TO{travelTime:7}]->
(D:Stop:Pedestrian)-[SWITCH_TO{switchTime:2}]->
(D:Stop:Bus{serviceLine:2})-[CONNECTED_TO{travelTime:8}]->(Z:Stop:Bus{serviceLine:2})-[SWITCH_TO{switchTime:2}]->
(Z:Stop:Pedestrian)

我想根据用户所需的出发时间(或者所需的到达时间)计算完整的旅行时间并获得 5 个最佳连接(更少的时间)。
在上面的示例中，您可以看到 SWITCH_TO 关系的 switchTime 为 2。这意味着我需要 2 分钟才能从当前位置切换到公交车站(例如，我必须寻找它)。 CONNECTED_TO 关系 travelTimes 是时间段，巴士需要从一站到另一站。
让我们假设我想在 7:00 开始。第一次切换需要 2 分钟。所以如果7:02以后有发车，我得看看(A:Stop:Bus)的时刻表。让我们假设下一次出发是在 7:10。然后我得等8分钟。这个等待时间不是固定值，而是每个特定请求的可变时间段。我从 7:10 开始。我需要 5+6=11 分钟到站 (C:Stop:Bus) 和 2 分钟下车(切换到)。然后我必须步行7分钟。所以如果一定要查2号服务线的时刻表。如果7:00+2+8+5+6+2+7+2 = 7:32以后有发车，就拿这个如果下次出发时间是 7:35，我将在 7:00+2+8+5+6+2+7+2+3+8+2= 7:45 到达我的目的地。我知道，我有点复杂。 :)

我在这里准备了一个例子:
CREATE (newStop:Stop:Pedestrian {
    stopName : 'A-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'A-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[510,610,710,810,835,910],
    tuesday:[510,610,710,810,835,910],
    wednesday:[510,610,710,810,835,910],
    thursday:[510,610,710,810,835,910],
    friday:[510,610,710,810,835,910],
    saturday:[510,610,710,810,835,910],
    sunday:[510,610,710,810,835,910]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'B-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[515,615,715,815,840,915],
    tuesday:[515,615,715,815,840,915],
    wednesday:[515,615,715,815,840,915],
    thursday:[515,615,715,815,840,915],
    friday:[515,615,715,815,840,915],
    saturday:[515,615,715,815,840,915],
    sunday:[515,615,715,815,840,915]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'C-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[521,621,711,821,846,921],
    tuesday:[521,621,711,821,846,921],
    wednesday:[521,621,711,821,846,921],
    thursday:[521,621,711,821,846,921],
    friday:[521,621,711,821,846,921],
    saturday:[521,621,711,821,846,921],
    sunday:[521,621,711,821,846,921]
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'C-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'D-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'D-Bus',
    mode : 'Bus',
    serviceLine : '2',
    monday:[535,635,735,835,935],
    tuesday:[535,635,735,835,935],
    wednesday:[535,635,735,835,935],
    thursday:[535,635,735,835,935],
    friday:[535,635,735,835,935],
    saturday:[535,635,735,835,935],
    sunday:[]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'Z-Bus',
    mode : 'Bus',
    serviceLine : '2',
    monday:[543,643,743,843,943],
    tuesday:[543,643,743,843,943],
    wednesday:[543,643,743,843,943],
    thursday:[543,643,743,843,943],
    friday:[543,643,743,843,943],
    saturday:[543,643,743,843,943],
    sunday:[]
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'Z-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;




MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'A-Pedestrian' AND s2.stopName = 'A-Bus'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'A-Bus' AND s2.stopName = 'B-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 5 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'B-Bus' AND s2.stopName = 'C-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 6 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'C-Bus' AND s2.stopName = 'C-Pedestrian'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'C-Pedestrian' AND s2.stopName = 'D-Pedestrian'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 7 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'D-Pedestrian' AND s2.stopName = 'D-Bus'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'D-Bus' AND s2.stopName = 'Z-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 8 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'Z-Bus' AND s2.stopName = 'Z-Pedestrian'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

如您所见，在某些站点中，出发时间的 int 数组也可能为空(如果这些天没有提供连接)。行人停靠站当然不包括时间表。
我的问题是:如何通过密码进行此查询？我必须总结这些时间才能选择正确的下次出发时间。我必须知道我什么时候到达目的地。我想向用户展示最好的 5 个连接。有没有办法做到这一点？如果没有，有什么建议可以解决这个问题吗？

非常感谢你!
斯特凡

Edit1:有没有办法用Java开发这个？在最简单的情况下，它可能只是一条最短路径，但具有智能成本函数？不是使用固定值使用函数来计算一条特定边的成本？任何帮助，将不胜感激!

最佳答案

[提前道歉，我不看就变成俄文小说了。它仍然只会为您提供最快的路线，而不是最快的 5 条路线，但希望比我更聪明的人可以在这方面进行改进。]

您正试图根据难以计算的成本进行一些极其复杂的路径选择。您肯定需要重构一些，以便您可以更紧密地修复成本，然后应用 apoc.algo.dijkstra 来获得可行的权重路径。为此，您需要将非常通用的模型更改为某种按物理位置组织的事件“链”。交通方式结合每周时间表将为您提供一些结构；在不同地点之间行走的能力只会适度地使其复杂化。在此过程中，我们最终将剥离一些不太相关和冗余的节点。让我们深入了解。

首先，我们需要能够将您的时间转换为机器可解析的内容。您可以使用 apoc 将它们转换为 isoformat 或类似的，但对于需要频繁订购且仅以分钟为单位的循环时间，我说从周日早上的午夜开始计数为 0 分钟，然后从那里开始计数。因此，基本上，从周日到午夜的几分钟将是您关注的时间，然后通过一些技巧，您可以处理周期性部分。

MATCH (stop:Stop:Bus)
WITH stop, ['sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday'] AS days
UNWIND RANGE(0, 6) AS day_index
WITH stop, day_index, days[day_index] AS day_key
UNWIND stop[day_key] AS int_time
WITH stop, day_index * 24 * 60 AS day_minutes, int_time % 100 AS minutes, ((int_time - (int_time % 100))/100)*60 AS hour_minutes 
WHERE day_minutes IS NOT NULL
WITH stop, day_minutes + hour_minutes + minutes AS time_since_sunday
MERGE (dep:Departure:Bus {time: time_since_sunday})
MERGE (dep) - [:AT] -> (stop)
WITH stop, time_since_sunday
ORDER BY time_since_sunday
WITH stop, collect(time_since_sunday) AS times
SET stop.departure_times = times

好的，这为我们提供了每个巴士站附近的出发事件，这些事件代表您可以在其他地方开始固定长度旅行的时间，如果您在该时间之前到达车站。现在，如果我们只考虑基于运输的移动，我们可以将一个 :Departure 处的每个 :Stop 节点连接到运输时间过去后下一站可用的任何 :Departure 节点(并考虑等待时间)。不过，加入步行(多模式交通)会稍微改变这一点，因为无论何时交通到达某个地方，您都可以立即用自己的两只脚“离开”。因此，我们应该对 :Arrival 节点进行建模以对应于基于 :Departure 的行程的另一端，以便我们可以区分等待下一个基于交通的 :Departure 和步行，时间明智。
MATCH (stop:Stop:Bus) <- [:AT] - (dep:Departure:Bus)
WITH stop, dep, dep.time AS dep_time
MATCH (stop) - [r:CONNECTED_TO] -> (other:Stop:Bus)
WITH dep, dep_time, dep_time + r.travelTime AS arrival_time, other
MERGE (a:Arrival:Bus {time: arrival_time})
MERGE (a) - [:AT] -> (other)
MERGE (dep) - [:TRAVEL {time: arrival_time - dep_time, mode: 'Bus'}] -> (a)
WITH a, arrival_time, other, other.departure_times AS dep_times
WITH a, other, arrival_time, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < arrival_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH a, other, next_dep_time, next_dep_time - arrival_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure:Bus {time: next_dep_time})
MERGE (a) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)

好的，因此对于每条单独的公交线路，我们现在可以计算仅在该公交线路上从 A 到 B 需要多长时间，即使旅行是非连续的(火车停在车站等)。 ) 现在是有趣的部分:集成步行选项! “行人停止”的想法没有多大意义(除非您正在对所有相关的离散空间进行建模，在这种情况下祝您好运和神速)，因此我们基本上将完全放弃它们。在两个非行人站点之间运行的 :SWITCH_TO 将被建模为两个站点之间的步行，而行人过境的 :SWITCH_TO 将被转换为结合两个开关和步行本身的长步行。首先是简单的(不在您的示例路径中，但我认为最终对您很有值(value)):
MATCH (stop:Stop:Bus) - [r:SWITCH_TO] -> (other:Stop)
WHERE NOT other:Pedestrian
WITH stop, other, r.switchTime AS walking_time, other.departure_times AS dep_times
MATCH (stop) <- [:AT] - (arr:Arrival)
WITH arr, other, walking_time, dep_times, arr.time + walking_time AS new_arr_time
MERGE (new_arr:Arrival:Pedestrian {time: new_arr_time})
MERGE (new_arr) - [:AT] -> (other)
MERGE (arr) - [:TRAVEL {time:walking_time, mode: 'Pedestrian'}] -> (new_arr)
WITH new_arr, other, new_arr_time, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < new_arr_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH new_arr, other, next_dep_time, next_dep_time - new_arr_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure {time:next_dep_time})
MERGE (new_arr) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)

好的，这样就处理了基本的传输。这个模型假设，顺便说一句，如果你要在公共(public)汽车或火车“线路”之间切换，你会将它们建模为单独的站点(如果它们真的在同一个地方，步行时间为 0 就可以了，但它要复杂得多跟踪您是否共享 :Stop s)。现在处理更复杂的传输，这些传输以前被建模为切换到 :Pedestrian ，旅行，然后切换回来:
MATCH (stop:Stop:Bus) - [r1:SWITCH_TO] -> (:Stop:Pedestrian) - [r2:CONNECTED_TO] -> (:Stop:Pedestrian) - [r3:SWITCH_TO] -> (other:Stop)
WITH stop, other, other.departure_times AS dep_times, REDUCE(s = 0 , x IN [r1, r2, r3] | s + COALESCE(x.travelTime, x.switchTime) ) AS walking_time
MATCH (stop) <- [:AT] - (arr:Arrival)
WITH arr, other, dep_times, walking_time, arr.time + walking_time AS new_arr_time
MERGE (new_arr:Arrival:Pedestrian {time:new_arr_time})
MERGE (new_arr) - [:AT] -> (other)
MERGE (arr) - [:TRAVEL {time:walking_time, mode: 'Pedestrian'}] -> (new_arr)
WITH new_arr, new_arr_time, other, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < new_arr_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH new_arr, other, next_dep_time, next_dep_time - new_arr_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure {time:next_dep_time})
MERGE (new_arr) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)

这为您提供了将 dijkstra 算法应用于您的站间移动的加权关系的基本框架。可能有一些估计来确定哪些停靠点可能会产生好的结果，以及如何从/到给定点步行到/离开它们(参见前面的陈述:对所有离散空间进行建模)，但如果你能确定一个 :Departure 或 :Arrival节点开始(或几个候选)，以及查询另一端的 :Stop 节点:
MATCH (:Stop {stopName: {begin_id} }) <- [:AT] - (d:Departure {time: {depart_time} })
WITH d
MATCH (end:Stop {stopName: {end_id} })
CALL apoc.algo.dijkstraWithDefaultWeight(d, end, 'TRAVELS>|AT>', 'time', 0) YIELD path, weight
RETURN path

关于neo4j - Cypher:根据节点属性计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40094386/

上一篇：scala - 不变类实例列表的 LUB

下一篇：firefox - 如何自行托管 mozilla 网络扩展？

相关文章：

Neo4j:无法加载带有 ID 的节点

python /Py2neo : weakref exception

neo4j - 匹配中的多个标签非常慢？

Neo4j Cypher RegExp 忽略大小写查询不适用于非拉丁字符

database - SSD 使用对基本数据库假设有何影响？

Neo4j - 按多种关系类型匹配

python - Neo4j 如何在 python 中访问节点的属性

amazon-ec2 - 连接到 ec2 上的 neo4j

swift - 如何使用 Theo 和 Neo4j 数据库从 Swift 检索节点属性？

neo4j - 查找节点属性的唯一值

©2024 IT工具网  联系我们