Is it possible to get the shortest path with traversal cost by using Cypher or Gremlin?

Question

I know it is possible to get the shortest path of minimum number of nodes by using Cypher and Gremlin? How about getting a path with minimum traversal cost? One of the example I can think of is the bus route. Some routes may have less bus stops (nodes) but need longer time (cost) to travel from one stop to another, some are reverse.

Is it possible to get the shortest path with minimum travel time by using Cypher or Gremlin?

Answer 1

You can look at and prob use this one:

http://components.neo4j.org/neo4j-graph-algo/stable/apidocs/org/neo4j/graphalgo/GraphAlgoFactory.html#dijkstra(org.neo4j.graphdb.RelationshipExpander, org.neo4j.graphalgo.CostEvaluator)

---

Here are some tests showing other built in algos that you might be able to use.

https://github.com/neo4j/neo4j/tree/master/community/graph-algo/src/test/java/org/neo4j/graphalgo/shortestpath

---

To roll your own algo you can call the neo4j java api and even gremlin/groovy pipes with something like this:

http://neo4j-contrib.github.io/gremlin-plugin/#rest-api-send-an-arbitrary-groovy-script---lucene-sorting

Answer 2

See this other question for more on shortest paths. In answer to this specific question though, calculating the cost of a path, I first altered the toy graph to make it so that the weights from marko to josh to lop was cheaper than marko to lop:

gremlin> g = TinkerGraphFactory.createTinkerGraph()
==>tinkergraph[vertices:6 edges:6]
gremlin> g.e(8).weight = 0.1f
==>0.1
gremlin> g.e(11).weight = 0.1f                                                        
==>0.1

Then to calculate the "cost" of the paths between marko and lop:

gremlin> g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path.transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]}
==>[0.4, [v[1], e[9][1-created->3], v[3]]]
==>[0.20000000298023224, [v[1], e[8][1-knows->4], v[4], e[11][4-created->3], v[3]]]

So note that the the path length 3 through marko to josh to lop is cheaper than marko to lop. In any case, the gremlin basically says:

• g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path - grab the paths between marko and lop.
• .transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]} - transform each path into a list where the first value is the sum of the weight properties and the second value is the path list itself. I calculate the total weight with a bit of groovy on the path list itself by finding all items in the path that are edges, then summing their weight values.