java - 考虑Java中tinkergraph权重的最短路径

Question

我正在尝试考虑边缘的权重属性来找到最短路径我的工作是在 TinkerGraph 上，我想用 java 来做。

gremlin 对我帮助不大

g.V().has(id1).
  repeat(both().simplePath()).
    until(has(id2)).as("path").
  map(unfold().coalesce(values("weight"),
                        constant(0)).
      sum()).as("cost").
  select("cost","path").next().get("path");

这给了我最短路径，而不考虑边缘的权重属性。

编辑:我的例子:

插入的边:

源、目标

b1,b2

b1,b2

b1,b2

b1,b2

b1,b3

b3,b2

private void add(Vertex source,Vertex target){
    if(!checkEdgeExist(graph,source,target))
        source.addEdge(target).property(WEIGHT,1.0);
    else {
        Edge e = getEdgeBetweenTwoVertices(graph,source,target);
       source.edges(Direction.OUT).forEachRemaining(edge -> {
            if(edge.inVertex().equals(target))
                edge.property(WEIGHT,(double)e.property(WEIGHT).value()+1);
        });

    private  static  boolean checkEdgeExist(TinkerGraph graph,Vertex source,Vertex target){
    return graph.traversal().V(source).outE().filter(p -> p.get().inVertex().equals(target)).hasNext();
}

换句话说，边的权重根据边的频率进行更新，例如，如果 b1,b2 出现 4 次，边的权重将为 4。现在我希望 Dijkstra 返回最短路径重量，而且就边缘而言不是最短的。路径(b1，b2)= b1->b3->b2

Answer 1

你的 Gremlin 几乎是正确的，但你错过了一些东西。我在 TinkerPop 附带的“现代”玩具图上进行了测试，您应该会发现它有效:

gremlin> g.V().has('person','name','marko').
......1>   repeat(bothE().otherV().simplePath()).
......2>     until(has('software','name','ripple')).
......3>   path().as("path").
......4>   map(unfold().coalesce(values("weight"),
......5>                         constant(0)).sum()).as("cost").
......6>   select("cost","path")
==>[cost:2.0,path:[v[1],e[8][1-knows->4],v[4],e[10][4-created->5],v[5]]]
==>[cost:1.8,path:[v[1],e[9][1-created->3],v[3],e[11][4-created->3],v[4],e[10][4-created->5],v[5]]]

您缺少的关键部分是:

1. 您需要将 repeat() 中的 both() 替换为 bothE().otherV()，以便边缘为占。
2. 继上一项之后，您需要边缘，以便它们出现在第 3 行对 path() 的调用中，该调用也缺失 - 第 1 项中的 Path 只包含顶点。如果您查看第 4 行，您就会明白为什么这很重要，因为 Path 已展开，并且对该 Path 的“权重”属性求和，从而得出“成本”。

请注意，当 TinkerPop 3.4.0 发布时，“最短路径”变为 core step这应该使此类操作更加简单。