logo标签列表

Cypher：基于节点属性进行计算

neo4jcypher
3
我开发了一个路由系统，通过使用多种出行方式（例如公共交通或拼车），来找到最佳路径。 基本上，我有一些节点，代表公交车站，火车站等。这些站点包括每天的时间表。此外，我还有步行站点。这些站点之间通过关系相互连接。如果我从步行转换到公交车，或者在公交线路之间换乘，该关系被称为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关系具有2分钟的转换时间。这意味着我需要2分钟从当前位置到达公交车站（例如，我必须找到它）。CONNECTED_TO关系travelTimes是公交车从一个站点到另一个站点需要的时间间隔。 假设我想在7:00开始。第一次切换需要2分钟。因此，我必须查看（A：Stop：Bus）的时间表，看是否有在7:02之后的出发时间。假设下一个出发时间是7:10。然后我必须等待8分钟。这种等待时间不是固定值，而是每个特定请求的可变时间段。我从7:10开始。我需要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;

如您所见，在某些站点中，发车时间的整型数组可能也为空（如果这些天没有提供连接）。步行站点当然不包括时间表。 我的问题是：如何通过Cypher进行此查询？我必须总结这些时间以选择正确的下一个出发时间。我必须知道我何时到达目的地。而且我想向用户显示最好的5个连接。有方法可以做到这一点吗？如果没有，是否有建议如何解决这个问题？
非常感谢！ Stefan
编辑1：有办法用Java开发吗？在最简单的情况下，它可以只是一条最短路径，但使用智能成本函数？与使用固定值相反，使用一个函数来计算一个特定边缘的成本？任何帮助都将不胜感激！
你的出发时间表数值会有问题。你试图捕获和使用时间值（例如，515代表5点15分，或者至少在我看来是这样），但你正在使用整数工作。按照目前的状态，你处理时间的计算不会自动滚动到下一个小时，而是每过60分钟就会超时。时间开始变得模糊不清了。如果我们从846（8点46分）开始，一个旅程需要50分钟，那么我们会得到896（9点36分）。但如果我们再做一个连接，需要5分钟，那么我们就会得到901。这是9点01分还是9点41分？跟踪溢出是有问题的。 - InverseFalcon
没错。我因为这个问题思考了很长时间。我的想法只是将其除以100，然后分别计算小时和分钟。但当然这不是一个非常精密的解决方案。当你需要在两天之间进行计算时，它会引起额外的问题，例如从23:00到00:30。但任何更好的想法都会受到赞赏。 - Stefan
我建议将APOC Procedures添加到您的数据库中，并且您可能想要阅读有关其日期/时间支持的相关信息。链接 - InverseFalcon
我该如何通过APOC实现这个功能？我仍然不知道如何开始。你有大致的想法吗？ - Stefan
1个回答
2
< p >【先提前道歉，这本来只是一个简单的问题，但我不小心写成了一篇长篇大论。此外，这只会给你最快的路径，而不是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

好的，这给我们每个公交站周围的出发事件带来了一个代表时间的出发事件，在那个时间之前，如果你在车站，你可以开始在其他地方进行固定长度的旅行。现在，如果我们只考虑基于交通工具的移动，我们可以将每个:Stop上的:Departure节点连接到经过交通时间后下一个站可用的: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)

好的，现在我们可以为每一条交通线路计算单独行驶所需的时间，即使旅行不是连续的（火车在车站停留等）。现在是有趣的部分：整合步行选项！“行人站”这个概念并没有太多意义（除非你正在建模所有相关的离散空间，在这种情况下，祝你好运），因此我们基本上会完全放弃它们。在两个非行人站之间操作的:SWITCH_TO将被建模为在两个站点之间步行，而在行人交通工具中操作的:SWITCH_TO将转换为长时间步行，结合了两个开关和步行本身。首先是容易的部分（虽然它们不在你的样本路径中，但我认为它们最终对你很有价值）：
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)

好的，那么这就涵盖了基本的转移。顺便说一下，这个模型假设如果你要在公交车或火车“线路”之间切换，你会将它们建模为单独的站点（如果它们确实是同一个地方，则步行时间为0很好，但如果你共享:Stop，则跟踪起来更加复杂）。现在来处理更复杂的转移，以前是通过切换到: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
嘿，首先：非常有趣的概念，我可以看出你花了相当多的时间来回答！我对图形数据库完全是新手，从未想过像这样的解决方案！感谢您的想法！ 我尝试了您的代码，并在倒数第二个查询中遇到了错误：“无法使用时间的空属性值合并节点”。我知道出了什么问题，但我找不到错误。 - Stefan
这是一个非常有趣的问题！所以你的第二个评论更容易：你需要自己找到下一个可用的:Departure，这就是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)的作用（对于之前不清楚的版本表示歉意）。它将选择最接近给定时间的单个时间，这将允许您计算查询后多久公交车起飞。 - Tore Eschliman
哈！在关系中没有transitTime，只有travelTime（CONNECTED_TO），switchTime（SWITCH_TO）和time（TRAVEL）。如果我执行MATCH (n) WHERE EXISTS(n.transitTime) RETURN n结果是（无行）。不，没有额外的信息。 - Stefan
对于你的第一个回复。好的，那么我必须将这个REDUCE操作添加到最后一个查询中。好的，我会尝试的.. :) - Stefan
我的错，那是我打错了。现在已经修复了 :) - Tore Eschliman
显示剩余5条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接