CODEWITHSUNDEEP
javagremlinshortest-pathtinkerpoptinkergraph
alaa elias
alaa elias

Reputation: 11

Shortest path taking into consideration the weight on tinkergraph in 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 is not very helpful for me

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 .

EDITED: my example:

edges inserted:

source,target

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();
}

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

Upvotes: 1

Views: 1208

Answers (2)

Daniel Kuppitz
Daniel Kuppitz

Reputation: 10904

According to your description, this is your test graph:

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()

The shortest weighted directed path is found using this query:

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]

Upvotes: 0

stephen mallette
stephen mallette

Reputation: 46216

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]]]

The key pieces you were missing were:

  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".

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

Upvotes: 2

Related Questions