Neo4j 公交路线应用建模

6

我的问题是,我有一个包含很多节点的图表,表示公交车的停靠站点。我应该如何包含公交车信息,例如哪些公交车在节点之间可用。

我考虑创建节点之间的公交车关系,其中包含两个节点之间所有公交车的信息和标记两个停靠站之间距离的关系属性。

      buses[500A,182A],distance:500m     buses[121B,542W,222A,111Z],distance:400m

就像A------------------------------------------------------->B----------------------------------------------------------->C一样。

那么如果没有直达路径,我该如何找到从A到M的公交车或公交车路线?

首先,我会查找从A到M的路径(一个neo4j查询)。

假设我的路径是:

buses[11A],distance:1000m    buses[11A],distance:250m   buses[13B,100A],distance:2000m

A----------------------------------------->L----------------------------------->N------------------------------------------->M

问题是如何通过编程检查是否有直达M的公交车,或者如何在中途换乘公交车。

根据上述情况,我可以通过11A从A到N,然后通过13B或100A之一从N到M。

我需要以编程方式完成这个任务。

我想要检索两个站点之间所有可能的路径以及路径的总距离和公交车信息。


你想要最小化距离还是转移次数? - Nicole White
我想获取所有可能的公交换乘路线信息,以及每条路径的总距离。 - Mahtab Alam
3个回答

14

您的模型需要更加具备图形化特点。也就是说,我认为在停止节点之间与公交信息之间的关系中,您不应该有一个数组属性。相反,公交车本身应该是节点,并且存在一种关系来表示它们在哪些站停靠。请考虑以下示例数据:

CREATE (a:Stop {name:'A'}),
       (b:Stop {name:'B'}),
       (c:Stop {name:'C'}),
       (d:Stop {name:'D'}),

       (a)-[:NEXT {distance:1}]->(b),
       (b)-[:NEXT {distance:2}]->(c),
       (c)-[:NEXT {distance:3}]->(d),

       (b1:Bus {id:1}),
       (b2:Bus {id:2}),
       (b3:Bus {id:3}),

       (b1)-[:STOPS_AT]->(a),
       (b1)-[:STOPS_AT]->(b),
       (b2)-[:STOPS_AT]->(a),
       (b2)-[:STOPS_AT]->(b),
       (b2)-[:STOPS_AT]->(c),
       (b3)-[:STOPS_AT]->(b),
       (b3)-[:STOPS_AT]->(c),
       (b3)-[:STOPS_AT]->(d);

现在的图像如下:

model

使用这个模型,可以轻松地找到最小换乘次数的行程,并返回所有必要的换乘信息(如果适用)。例如,从A到D的所有最短行程(以换乘次数为标准):

MATCH (a:Stop {name:'A'}), (d:Stop {name:'D'})
MATCH p = allShortestPaths((a)-[:STOPS_AT*]-(d))
RETURN EXTRACT(x IN NODES(p) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                    WHEN x:Bus THEN 'Bus ' + x.id
                               ELSE '' END) AS itinerary

找到了三条路线,它们都需要一次换乘:

Stop A, Bus 2, Stop C, Bus 3, Stop D
Stop A, Bus 1, Stop B, Bus 3, Stop D
Stop A, Bus 2, Stop B, Bus 3, Stop D

当然,你可以使用 EXTRACT() 函数以任何你想要的方式返回这些信息。

另一个例子。查找从 A 到 C 的行程:

MATCH (a:Stop {name:'A'}), (c:Stop {name:'C'})
MATCH p = allShortestPaths((a)-[:STOPS_AT*]-(c))
RETURN EXTRACT(x IN NODES(p) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                    WHEN x:Bus THEN 'Bus ' + x.id
                               ELSE '' END)

找到了一条路线,且无需换乘:

Stop A, Bus 2, Stop C
请告诉我这是否回答了您的问题。
编辑:要获取距离:
MATCH (a:Stop {name:'A'}), (d:Stop {name:'D'})
MATCH route = allShortestPaths((a)-[:STOPS_AT*]-(d)),
      stops = (a)-[:NEXT*]->(d)
RETURN EXTRACT(x IN NODES(route) | CASE WHEN x:Stop THEN 'Stop ' + x.name
                                        WHEN x:Bus THEN 'Bus ' + x.id
                                   ELSE '' END) AS itinerary,
       REDUCE(d = 0, x IN RELATIONSHIPS(stops) | d + x.distance) AS distance


                           itinerary  distance
Stop A, Bus 1, Stop B, Bus 3, Stop D         6
Stop A, Bus 2, Stop B, Bus 3, Stop D         6
Stop A, Bus 2, Stop C, Bus 3, Stop D         6

谢谢Nicole,这正是我在寻找的。我在停靠点之间的NEXT关系中添加了distance属性。我尝试使用以下查询获取每条可能路径的总距离。但它返回空值。MATCH (a:Stop {name:'A'}), (c:Stop {name:'C'}) MATCH p = allShortestPaths((a)-[:STOPS_AT*]-(c)) RETURN EXTRACT(x IN NODES(p) | CASE WHEN x:Stop THEN 'Stop ' + x.name WHEN x:Bus THEN 'Bus ' + x.id ELSE '' END),reduce(distance=0,r in relationships(p)|distance+r.distance)as Distance你能解释一下这个查询是如何内部工作的吗? - Mahtab Alam
1
我没有意识到距离是一个因素 - 你能编辑你的问题来包括这个吗?你上面的查询返回空值是因为你匹配了“STOPS_AT”关系,而不是“NEXT”关系。 - Nicole White

0

由于您可以在相同节点之间创建多个关系,我建议为每个公交车创建一个关系。因此,以您的示例为例:

A<-----------------B<-------------------------------C
   buses[180Q,171B]      buses[80A,43B,121S]

你可以做类似于这样的事情:
<somehow MATCH on A and B>
CREATE B-[:connects_to {bus: '180Q'}]->A
CREATE B-[:connects_to {bus: '171B'}]->A

等等...

这样您就可以做到

MATCH path=(start {id: '123'})-[:connects_to {bus: '180Q'}*1..10]-(end: {id: '321'})
UNWIND relationships(path) AS hop
WITH path, hop
WITH path, collect(DISTINCT hop.bus) AS busses
WHERE length(busses) <= 2
RETURN path

说实话,我从来没有同时使用关系属性匹配和变量长度规范,但我想它应该可以工作。

我明白我可以在节点之间创建多个关系。但是@Brian的问题是,即使我通过Cypher查询获得了节点之间的最短路径,我仍然需要通过编程方式检查由Cypher查询返回的路径,以表示车站之间的公交换乘。该查询没有告诉我在哪里换乘,它只给出了从A到B的最短路径和到达目的地所需的公交车详细信息。我希望我能够清楚地表达我的问题。 - Mahtab Alam
啊,我想我可能明白了。你想找到包括换乘(在一个站点下车并换乘另一条路线)的最短路线吗? - Brian Underwood
是的,@Brian,那就是我要找的。有什么办法吗? - Mahtab Alam
我刚刚更新了答案,加入了一个查询语句。虽然我没有尝试过,也不确定它是否能够正常工作,但是我猜测如果你多试几次,可能会有所帮助。此外,根据你想回答的问题类型,你可能需要考虑编写/查找未管理的扩展程序。 - Brian Underwood
谢谢 @Brian,我会处理这个查询。看起来 Neo4j 有我需要的查询。 - Mahtab Alam

0

我尝试了很多Cypher查询,但无法得到我要查找的公交换乘信息。到目前为止,我的查询是:

MATCH (from:Stop { name:"A" }), (to:Stop { name: "S"}) , path = (from)-[:CONNECTED*]->(to)
unwind relationships(path) as hop
RETURN extract(n IN nodes(path)| n.name) AS Shortest_Route,collect(hop.Buses) as Buses,length(path) as Stop_Count,
reduce(distance = 0, r in relationships(path) | distance+r.distance) AS Shortest_Distance
ORDER BY Shortest_Distance ASC
LIMIT 1 .

我发现很难获取公交换乘信息。我认为我必须通过编程来实现它。这看起来并不是很复杂,但我在想如果我可以从Cypher查询本身获取它。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接