How to Implement A* on Titan Graph Database?

1
votes

I am using Titan 1.0.0 and Cassandra as a backend.

I have location data (latitude, longitude) as a nodes and edges between these nodes. I want to find shortest path from node A to node B. The graph size is very large. Currently I am using this query to find path between two nodes.

g.V(fromNode).repeat(both().simplePath()).until(is(toNode)).limit(1).path().fill(list);

This query is very inefficient and gives memory error for path size more than 10. After reading about shortest path algorithms, I got to know that implementing A* will be more feasible than implementing Dijkstra's as in A* less graph will be explored.

Now I can use JUNG and load TitanGraph into the memory and implement my own A* to get shortest path. But I don't want whole graph to be inside memory.

Kindly suggest me on how should I implement A* on TitanGraph. Should I query graph using API or should I load graph into memory first then run the A* on in-memory graph.

I will be thankful for any other suggestions as well.

1
graph-databasesdijkstraa-startitantinkerpop3

1 Answers

1
votes

First, this is a question more associated with Tinkerpop3 rather than Titan. I agree with you that loading the graph in memory is a totally bad idea.

The best way is to implement the A star algorithm to run straight on the Gremlin console.

The Gremlin console executes Groovy code. You could implement the A* algorithm on a .groovy file and load it to Gremlin console this way:

gremlin> :load my_folder/a-star-algo-tp3.groovy

Let's say you defined a method inside this file called:

List<Element> a_star_algo(Graph graph, Object fromId, Object toId)

You could just call it from your gremlin console this way:

list = a_star_algo(graph, v1.id(), v2.id())

You may implement this method using A* algorithm. This repo implements the algorithm using their own data structure in Groovy. I'm not sure how efficient their implementation is but you may have a look.