1

考虑到边缘上的权重属性，我试图找到最短路径，我的工作是在 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

4

2 回答 2

2

你的 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. 您需要替换both()您的repeat()withbothE().otherV()以便考虑边缘。
  2. 继上一项之后，您需要边，以便它们出现在path()对第 3 行的调用中，这也是缺失的 - 对于第 1 项，Path它将仅包含顶点。如果您查看第 4 行，您会明白为什么这很重要，因为它Path已展开并且“重量”属性总和为Path您提供“成本”的属性。

请注意，当 TinkerPop 3.4.0 发布时，“最短路径”成为核心步骤，这将使此类操作更加直接。

于 2018-11-14T12:12:38.703 回答
0

根据您的描述，这是您的测试图：

g = TinkerGraph.open().traversal()
g.addV().property(id, 'b1').as('b1').
  addV().property(id, 'b2').as('b2').
  addV().property(id, 'b3').as('b3').
  addE('link').
    from('b1').
    to('b2').
    property('weight', 4).
  addE('link').
    from('b1').
    to('b3').
    property('weight', 1).
  addE('link').
    from('b3').
    to('b2').
    property('weight', 1).
  iterate()

使用以下查询找到最短的加权有向路径：

gremlin> g.withSack(0).V('b1').
......1>   repeat(outE().sack(sum).by('weight').inV().simplePath()).
......2>     emit(hasId('b2')).
......3>   order().
......4>     by(sack()).
......5>   limit(1).
......6>   path().
......7>     by(id).
......8>     by('weight')
==>[b1,1,b3,1,b2]
于 2018-11-19T14:57:27.077 回答