shortest_paths.adoc

neo4j installation

• Install Neo4j 3.1.0-M12-beta2

• copy APOC library to plugins folder

• drop Node.txt and Link.txt to import folder

prepare data files

Node.txt and Link.txt do have couple of header lines we should get rid of to make it more easy to process them with LOAD CSV. Be aware the following sed commands do inplace editing.

sed -i -e '4d' -e '3d' -e '1d' Node.txt
sed -i -e '4d' -e '3d' -e '1d' Link.txt

prepare indexes

create index on :Location(id)

data import

using periodic commit 10000
load csv with headers from 'file:///Node.txt' as row FIELDTERMINATOR ';'
create (:Location{id:row.NODE_ID, longitude:toFloat(row.X), latitude:toFloat(row.Y)})

Added 1246456 labels, created 1246456 nodes, set 3739366 properties, statement completed in 80032 ms.

using periodic commit 10000
load csv with headers from 'file:///Link.txt' as row FIELDTERMINATOR ';'
match (s:Location{id:row.FROM_NODE})
match (e:Location{id:row.TO_NODE})
create (s)-[:CONNECTED_TO{d:distance(point(s), point(e))}]->(e)

Set 1468141 properties, created 1468141 relationships, statement completed in 157996 ms.

querying for weighted shortest paths

Now trying to find a weighted shortest path of a length of 506 between two randomly choosen nodes using 2 different algorthims.

Using dijkstra algorithm:

match (s:Location{id:'18967684'})
match (e:Location{id:'18028696'})
call apoc.algo.dijkstra(s, e, "CONNECTED_TO", "d") yield path, weight
return length(path), weight

Returned 1 record in 1741 ms.

Using AStar algorithm

match (s:Location{id:'18967684'})
match (e:Location{id:'18028696'})
call apoc.algo.aStar(s, e, "CONNECTED_TO", "d", "latitude", "longitude") yield path, weight
return length(path), weight

Returned 1 record in 591 ms.