考虑Java中修补匠的权重的最短路径 [英] Shortest path taking into consideration the weight on tinkergraph in Java

问题描述

我正在尝试考虑边缘的权重属性找到最短路径我的工作是在TinkerGraph上进行的，我想在Java中完成.

I'm trying to find the shortest path taking into consideration the weights properties on the edges my work is on TinkerGraph and i want to do it in 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");

这为我提供了最短的路径，而没有考虑边缘的权重属性.

this gives me the shortest path without taking into consideration the weight property on the edges .

我的例子:

已插入边缘:

源，目标

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.重量，而不是最短的边缘.路径(b1，b2)= b1-> b3-> b2

in other words the weight of the edge gets updated according to the frequency of an edge, for example if b1,b2 appeared 4 time the edge will be of weight 4.Now i want Dijkstra to return the shortest path in terms of weight and not the shortest in terms of edges. path(b1,b2) = b1->b3->b2

推荐答案

您的Gremlin几乎是正确的，但您缺少一些东西.我在TinkerPop附带的现代"玩具图上进行了测试，您应该会发现这可行:

Your Gremlin is close to being right but you're missing something things. I tested on the "modern" toy graph that ships with TinkerPop and you should find that this works:

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()的调用中，该行也缺失了-第一项是 Path 仅包含顶点.如果您看一下第4行，您会发现为什么这很重要，因为 Path 已展开，并且该 Path 的权重"属性相加，从而为您带来了成本".

1. You needed to replace both() in your repeat() with bothE().otherV() so that the edges would be accounted for.
2. Following on from the previous item, you needed the edges so that they would appear in the call to path() on line 3 that was also missing - with item 1 the Path would only contain vertices. If you look at line 4, you can see why that is important because the Path is unfolded and the "weight" properties summed for that Path which gives you "cost".

请注意，当TinkerPop 3.4.0发行时，最短路径"成为

Note that when TinkerPop 3.4.0 releases, "shortest path" becomes a core step which should make such operations much more straightforward.

这篇关于考虑Java中修补匠的权重的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！