Skip to content

Instantly share code, notes, and snippets.

Last active March 3, 2019 23:10
Show Gist options
  • Save mauget/4419767 to your computer and use it in GitHub Desktop.
Save mauget/4419767 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) {
public void emitShortestPathKML(PrintStream ps, long keyValueA, long keyValueB)
throws ApplicationException {"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)
Node nodeB = nodeIndex.get(DomainConstants.PROP_NODE_ID, keyValueB)
.getSingle();"nodeA ID %d", nodeA.getId()));"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);
} finally {
private void emitCoordinates(PrintStream printSteam, PathFinder<WeightedPath> shortestPath, Node nodeA, Node nodeB) {
WeightedPath path = shortestPath.findSinglePath(nodeA, nodeB);
if (null != path){
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));
}"Emitted route having shortest path coordinates (%d...%d)",
nodeA.getId(), nodeB.getId()));
} else {"No route found between coordinates (%d...%d)", nodeA.getId(),
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment