public
Last active

Emits a Google KML stream of the shortest path between two points. A "point" is a Neo4j node having latitude and and longitude properties. The Neo4j A* algorithm does the work.

  • Download Gist
Neo4j shortest path
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
public void findShortestPath(PrintStream ps, long startNode, long endNode) {
try {
RouterService router = Initializer.getApplicationContext().getBean(RouterService.class);
router.emitShortestPathKML(ps, startNode, endNode);
} catch (Exception e) {
e.printStackTrace();
}
}
public void emitShortestPathKML(PrintStream ps, long keyValueA, long keyValueB)
throws ApplicationException {
log.info(String.format("Finding least-expensive route from node %d to node %d", keyValueA, keyValueB));
GraphDatabaseService graphDb = getDbWrapper().getDbRef();
 
Index<Node> nodeIndex = graphDb.index().forNodes(DomainConstants.INDEX_NAME);
Node nodeA = nodeIndex.get(DomainConstants.PROP_NODE_ID, keyValueA)
.getSingle();
Node nodeB = nodeIndex.get(DomainConstants.PROP_NODE_ID, keyValueB)
.getSingle();
 
log.info(String.format("nodeA ID %d", nodeA.getId()));
log.info(String.format("nodeB ID %d", nodeB.getId()));
Transaction tx = graphDb.beginTx();
try {
Expander relExpander = Traversal.expanderForTypes(
DomainConstants.RelTypes.DOMAIN_LINK, Direction.BOTH);
 
relExpander.add(DomainConstants.RelTypes.DOMAIN_LINK, Direction.BOTH);
 
PathFinder<WeightedPath> shortestPath = GraphAlgoFactory.aStar(relExpander,
costEval, estimateEval);
 
emitCoordinates(ps, shortestPath, nodeA, nodeB);
tx.success();
} finally {
tx.finish();
}
}
 
private void emitCoordinates(PrintStream printSteam, PathFinder<WeightedPath> shortestPath, Node nodeA, Node nodeB) {
 
WeightedPath path = shortestPath.findSinglePath(nodeA, nodeB);
if (null != path){
printSteam.println(KMLConstants.KML_LINE_START);
for (Node node : path.nodes()) {
double lat = (Double) node.getProperty(DomainConstants.PROP_LATITUDE);
double lon = (Double) node.getProperty(DomainConstants.PROP_LONGITUDE);
printSteam.println(String.format("%f,%f,2300", lon, lat));
}
log.info(String.format("Emitted route having shortest path coordinates (%d...%d)",
nodeA.getId(), nodeB.getId()));
printSteam.println(KMLConstants.KML_LINE_END);
} else {
log.info(String.format("No route found between coordinates (%d...%d)", nodeA.getId(),
nodeB.getId()));
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.