OpenStreetMaps - Implementation of Shortest Path Algorithm using Neo4J
This project is maintained by krithivasanchandran
Structure of XML OSM Schema: Node , Way and Relationships - For more details please visit : http://wiki.openstreetmap.org/wiki/OSM_XML
Designing DOM XML Parser:
DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); DocumentBuilder builder = factory.newDocumentBuilder(); Document document = builder.parse(new File("C:/Users/KRITHIVASAN CHANDRAN/Desktop/eclipse/LisbonNavigationOSMParser/Lisboa.xml"));
//Getting the Child Elements by Named Node Name – Way and Node –
//Getting the Child Elements by Named Node Name Way and Node
NodeList nodeList = document.getDocumentElement().getElementsByTagName("node");
NodeList way_Node_List = document.getDocumentElement() .getElementsByTagName("way");
Designing JSON Parser:
public class JSONParser {
public static void main(String[] args) throws IOException {
// Getting the tag data
Map popularkeys = new HashMap();
for(int i=0;i<=2;i++) {
URL url = new URL("http://taginfo.openstreetmap.org/api/4/tags/popular?sortname=count_all&sortorder=desc&page="+i+"&rp=15&qtype=tag&format=json_pretty");
InputStream is = url.openStream();
JsonParserFactory factory=JsonParserFactory.getInstance();
com.json.parsers.JSONParser parser=factory.newJsonParser();
Map jsonData=parser.parseJson(is, "UTF-8");
List value = (List) jsonData.get("data");
for(Map dataset : value){
String keyset = (String) dataset.get("key");
if(!keyset.equalsIgnoreCase("source") && keyset != null){
String datavalue = (String) dataset.get("value");
popularkeys.put(keyset, datavalue); } } }
System.out.println(popularkeys.entrySet());
} }
String datavalue = (String) dataset.get("value");
popularkeys.put(keyset, datavalue); }}}
System.out.println(popularkeys.entrySet()); }}
Writing Data to Neo4J Server:
Connection con = DriverManager.getConnection("jdbc:neo4j://localhost:7474/");
PreparedStatement statement = con.prepareStatement(synchronizercontainer.toString());
statement.executeQuery();
Writing Cypher Query to write nodes and relationships to Neo4J graph database:
Create a node with reference Id , longitude , latitude and tag contents parsed from OpenStreetMap data
query = "CREATE ( n:way {refid :'"+coordinateWay.get(jk).getReferenceId() +"',"+ bufferTag.toString() +" Lat:'"+coordinateWay.get(jk).getLatitude() +"', Long:'"+coordinateWay.get(jk).getLongitude()+"'})";
Creating Unique Relationships between lanes with reference to refId from OSM XML data:
CREATE UNIQUE (33360496)-[:localway]->(33360529)
CREATE UNIQUE (33360529)-[:localway]->(33360530)
CREATE UNIQUE (33360530)-[:localway]->(33360504)
CREATE UNIQUE (33360504)-[:localway]->(33360505)
CREATE UNIQUE (33360505)-[:localway]->(1135629360)
Sample Cypher Query Language:
MATCH N RETURN COUNT(*) – Return the total number of nodes.
START n=node(*) MATCH (n)-[r]? (m) RETURN n,r,m; - Return all the nodes with following outgoing directed relationship
MATCH (lane : way {name : ‘Rua Augusta’ }) ? (way) RETURN way.name; - Returns the name of nodes connected to ‘Rua Augusta’.
MATCH (lane : way {name : ‘Rua Augusta’ }) ? (way) RETURN way.name; - Returns the name of nodes incoming relationship to ‘Rua Augusta’.
MATCH (lane:Way { name:"Rua da Alfândega" }),(laner:Way { name:"Oliver Stone" }), p = shortestPath((lane)-[*..15]?(laner)) RETURN p; - Returns the shortest path from Source to Destination in 15 hops .
MATCH (lane:Way { name:"Rua da Alfândega" }),(laner:Way { name:"Oliver Stone" }), p = allShortestPaths((lane)-[*..15]?(laner)) RETURN p; - Returns all the shortest path from Source to Destination
MATCH N RETURN COUNT(*) : Return the total number of nodes.
START n=node(*) MATCH (n)-[r]ïƒ (m) RETURN n,r,m; - Return all the nodes with following outgoing directed relationship
MATCH (lane : way {name : ‘Rua Augusta’ }) ïƒ (way) RETURN way.name; - Returns the name of nodes connected to ‘Rua Augusta’.
MATCH (lane : way {name : ‘Rua Augusta’ })  (way) RETURN way.name; - Returns the name of nodes incoming relationship to ‘Rua Augusta’.
MATCH (lane:Way { name:"Rua da Alfândega" }),(laner:Way { name:"Oliver Stone" }), p = shortestPath((lane)-[*..15]ïƒ (laner)) RETURN p; - Returns the shortest path from Source to Destination in 15 hops .
MATCH (lane:Way { name:"Rua da Alfândega" }),(laner:Way { name:"Oliver Stone" }), p = allShortestPaths((lane)-[*..15]ïƒ (laner)) RETURN p; - Returns all the shortest path from Source to Destination
Visualizing the directed Graph:
START n=node(*) MATCH (n)-[r]->(m) RETURN n,r,m LIMIT 250;
This cypher query returns all the outgoing relationship associated with the node and is limited to 250 nodes. The screenshot of the graph is attached below .
Node Relationships:
LOCAL_CONNECT :
Way Named Node contains child elements identified by referenceID. The relationship that exists between a single lane is [:LOCAL_CONNECT]. The relationship is as shown below:
EXTERNAL_CONNECT:
Totally distinct different ways with one similar reference Ids are connected by [:EXTERNAL_CONNECT] relationship. Cypher.java identifies the similar referenceID between different lanes and connects them relationally.
GraphDatabaseService db = new GraphDatabaseFactory().newEmbeddedDatabase("C:/Users/KRITHIVASAN CHANDRAN/Documents/Neo4j/default.graphdb");
ExecutionEngine engine = new ExecutionEngine( db );
result = engine.execute(" MATCH (n:way { refid :'" + str + "'}) RETURN DISTINCT n.name AS name;");
Iterator column = result.columnAs( "name" );
//Returns the Distinct referenceId ad stores in the ArrayList.
buffer.append("MATCH (n:way),(lane:way) WHERE n.name = '"+source+"' AND lane.name = '"+destination+"' AND n.refid ='"+str+"' AND lane.refid= '"+str+"'");
buffer.append("CREATE UNIQUE (n)-[:EXTERNAL_CONNECT]-(lane);");
Distance Calculation given their Latitudes and Longitudes : (Reference StackOverflow)
double dLat = getRad(latitude2 - latitude1);
double dLong = getRad(longitude2 - longitude1);
double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(getRad(latitude1)) * Math.cos(getRad(latitude2)) *
Math.sin(dLong / 2) * Math.sin(dLong / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return (RADIUS_EARTH * c) * 1000;
}
private Double getRad(Double x) {
return x * Math.PI / 180;
}
Case Study : Lisbon , Portugal - 50 Mile Radius
Analysis 1:
Source : Calçada do Carmo , Lisbon , Portugal
Destination : Rua de São Julião , Lisbon , Portugal
Query:
MATCH (martin:way { name:"Calçada do Carmo" }),(oliver:way { name:"Rua -de São Julião" }), p = shortestPath((martin)-[*..13]-(oliver))
The Output of Neo4J is in JSON format is included in project Jar file with Name Analysis_Json1 for analysis.
Analysis2: Source : Rua da Padaria, Lisboa, Portugal
Destination : Rua do Instituto Virgílio Machado, Lisboa, Portugal
Source Node : Rua da Padaria Transit Node : Rua dos Bacalhoeiros, Rua dos Arameiros, Rua da Alfândega, Rua Instituto Virgilio Machado
Destination : Rua do Instituto VirgÃlio Machado, Lisboa, Portugal
MATCH (martin:way { name:"Rua Instituto Virgilio Machado"}), (oliver:way { name:"Rua da Padaria"}), p = shortestPath((martin)-[*]-(oliver)) RETURN p;
The Output of Neo4J is in JSON format is included in project Jar file with Name Analysis_Json3 .
Environment: • Eclipse – Juno • Neo4J Database (No SQL graph Database) (www.neo4j.org) • XML , JSON • TileMill – Custom Map designer • QGIS – Vector Mapping • OpenXC (Fords Open Source Platform) • Open Data Portugal - http://www.dados.gov.pt/pt/inicio/inicio.aspx • Sublime Text Editor • Open Street Maps
References: • StackOverflow.com • Neo4J Manual – Cypher Query Language • Java 8 Complete reference.
Author: Implemented and Designed by @KrithivasanChandran - Krithivasan Chandran
Support: You can contact me c.keerthivasan@gmail.com if you are experiencing any issues running my code.