通过使用Cypher或Gremlin是否可以得到具有遍历成本的最短路径? [英] Is it possible to get the shortest path with traversal cost by using Cypher or Gremlin?

问题描述

我知道可以通过使用Cypher和Gremlin获得最少节点数的最短路径吗?如何以最小的遍历成本获得路径?我能想到的例子之一就是公交路线.有些路线的巴士站(节点)数量可能较少，但从一个车站到另一个车站需要更长的时间(成本)，有些则是反向的.

I know it is possible to get the shortest path of minimum number of nodes by using Cypher and Gremlin? How about getting a path with minimum traversal cost? One of the example I can think of is the bus route. Some routes may have less bus stops (nodes) but need longer time (cost) to travel from one stop to another, some are reverse.

使用Cypher或Gremlin是否有可能以最短的旅行时间获得最短的路径?

Is it possible to get the shortest path with minimum travel time by using Cypher or Gremlin?

推荐答案

查看其他玩具图" 进行制作，以使marko to josh to lop中的权重比marko to lop中的权重便宜:

See this other question for more on shortest paths. In answer to this specific question though, calculating the cost of a path, I first altered the toy graph to make it so that the weights from marko to josh to lop was cheaper than marko to lop:

gremlin> g = TinkerGraphFactory.createTinkerGraph()
==>tinkergraph[vertices:6 edges:6]
gremlin> g.e(8).weight = 0.1f
==>0.1
gremlin> g.e(11).weight = 0.1f                                                        
==>0.1

然后计算marko和lop之间路径的成本":

Then to calculate the "cost" of the paths between marko and lop:

gremlin> g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path.transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]}
==>[0.4, [v[1], e[9][1-created->3], v[3]]]
==>[0.20000000298023224, [v[1], e[8][1-knows->4], v[4], e[11][4-created->3], v[3]]]

因此请注意，通过marko to josh to lop的路径长度3比marko to lop便宜.无论如何，格林姆林基本上说:

So note that the the path length 3 through marko to josh to lop is cheaper than marko to lop. In any case, the gremlin basically says:

• g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path-抓住marko和lop之间的路径.
• .transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]}-将每个路径转换为列表，其中第一个值是weight属性的总和，第二个值是路径列表本身.通过查找路径中所有边缘的项目，然后对它们的权重值求和，我会在路径列表本身上加上一些槽纹来计算总重量.

• g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path - grab the paths between marko and lop.
• .transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]} - transform each path into a list where the first value is the sum of the weight properties and the second value is the path list itself. I calculate the total weight with a bit of groovy on the path list itself by finding all items in the path that are edges, then summing their weight values.

这篇关于通过使用Cypher或Gremlin是否可以得到具有遍历成本的最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！