Skip to content

Instantly share code, notes, and snippets.

@aviatorBeijing
Forked from mauget/Neo4j shortest path
Created August 19, 2016 07:34
Show Gist options
  • Save aviatorBeijing/1dd3c3f71216ae1246527af11786f4aa to your computer and use it in GitHub Desktop.
Save aviatorBeijing/1dd3c3f71216ae1246527af11786f4aa to your computer and use it in GitHub Desktop.
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.
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()));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment