Кратчайший путь с учетом веса тинкерграфа в Java - PullRequest
Новая
       31

Кратчайший путь с учетом веса тинкерграфа в Java

0 голосов
/ 14 ноября 2018

Я пытаюсь найти кратчайший путь, учитывая свойства весов по краям моя работа на TinkerGraph, и я хочу сделать это в Java.

Гремлин не очень полезен для меня 

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. Теперь я хочу, чтобы Дейкстра вернул кратчайший путь с точки зрения вес и не самый короткий с точки зрения ребер. путь (b1, b2) = b1-> b3-> b2

Ответы [ 2 ]

0 голосов
/ 19 ноября 2018

Согласно вашему описанию, это ваш тестовый график: 

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]
0 голосов
/ 14 ноября 2018

Ваш Гремлин близок к тому, чтобы быть правым, но вы что-то упускаете.Я протестировал на «современном» игрушечном графике, который поставляется с 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() на bothE().otherV(), чтобы были учтены края.
  2. Вслед за предыдущим элементом вам понадобились ребра, чтобы они появлялись при вызове path() в строке 3, которая также отсутствовала - с элементом 1 Path будет содержать только вершины.Если вы посмотрите на строку 4, вы поймете, почему это важно, потому что Path развернут и свойства «веса» суммированы для этого Path, что дает вам «стоимость».

Примечаниечто когда TinkerPop 3.4.0 выйдет, «кратчайший путь» станет базовым шагом , что должно сделать такие операции намного проще.

...