Path Finding Procedures

APOC exposes some built in path-finding functions that are included in Neo4j.

apoc.algo.dijkstra(startNode, endNode, 'KNOWS|<WORKS_WITH|IS_MANAGER_OF>', 'distance') YIELD path, weight

run dijkstra with relationship property name as cost function

apoc.algo.aStar(startNode, endNode, 'KNOWS|<WORKS_WITH|IS_MANAGER_OF>', 'distance','lat','lon') YIELD path, weight

run A* with relationship property name as cost function

apoc.algo.aStarConfig(startNode, endNode, 'KNOWS

<WORKS_WITH

IS_MANAGER_OF>', {weight:'dist',default:10, x:'lon',y:'lat',pointPropName:'point'}) YIELD path, weight - run A* with relationship property name as cost function

apoc.algo.allSimplePaths(startNode, endNode, 'KNOWS|<WORKS_WITH|IS_MANAGER_OF>', 5) YIELD path, weight

run allSimplePaths with relationships given and maxNodes

apoc.stats.degrees(relTypesDirections) yield type, direction, total, min, max, mean, p50, p75, p90, p95, p99, p999

Example To find the weighted shortest path based on relationship property d from A to B following only :ROAD relationships, run the following query:

MATCH (from:Loc{name:'A'}), (to:Loc{name:'D'})
CALL apoc.algo.dijkstra(from, to, 'ROAD', 'd') yield path as path, weight as weight
RETURN path, weight

apoc.algo.aStarConfig

Given this dataset:

CREATE (b:City {name:'Berlin', coords: point({latitude:52.52464,longitude:13.40514}), lat:52.52464,lon:13.40514})
CREATE (m:City {name:'München', coords: point({latitude:48.1374,longitude:11.5755}), lat:48.1374,lon:11.5755})
CREATE (f:City {name:'Frankfurt',coords: point({latitude:50.1167,longitude:8.68333}), lat:50.1167,lon:8.68333})
CREATE (h:City {name:'Hamburg', coords: point({latitude:53.554423,longitude:9.994583}), lat:53.554423,lon:9.994583})
CREATE (b)-[:DIRECT {dist:255.64*1000}]->(h)
CREATE (b)-[:DIRECT {dist:504.47*1000}]->(m)
CREATE (b)-[:DIRECT {dist:424.12*1000}]->(f)
CREATE (f)-[:DIRECT {dist:304.28*1000}]->(m)
CREATE (f)-[:DIRECT {dist:393.15*1000}]->(h)

It is possible to execute the following query (leveraging on lat and lon node properties, which are numbers, on dist relationship property and with default cost 100):

MATCH (from:City {name:'München'}), (to:City {name:'Hamburg'})
CALL apoc.algo.aStarConfig(from, to, 'DIRECT', {weight:'dist',y:'lat', x:'lon',default:100})
YIELD weight, path
RETURN weight, path

Table 1. Results
weight	path
697430.0	[source,json] ---- { "start": { "identity": 1520006, "labels": [ "City" ], "properties": { "name": "München", "lon": 11.5755, "lat": 48.1374, "coords": point({srid:4326, x:11.5755, y:48.1374}) } }, "end": { "identity": 1520008, "labels": [ "City" ], "properties": { "name": "Hamburg", "lon": 9.994583, "lat": 53.554423, "coords": point({srid:4326, x:9.994583, y:53.554423}) } }, "segments": [ { "start": { "identity": 1520006, "labels": [ "City" ], "properties": { "name": "München", "lon": 11.5755, "lat": 48.1374, "coords": point({srid:4326, x:11.5755, y:48.1374}) } }, "relationship": { "identity": 3, "start": 1520007, "end": 1520006, "type": "DIRECT", "properties": { "dist": 304280.0 } }, "end": { "identity": 1520007, "labels": [ "City" ], "properties": { "name": "Frankfurt", "lon": 8.68333, "lat": 50.1167, "coords": point({srid:4326, x:8.68333, y:50.1167}) } } }, { "start": { "identity": 1520007, "labels": [ "City" ], "properties": { "name": "Frankfurt", "lon": 8.68333, "lat": 50.1167, "coords": point({srid:4326, x:8.68333, y:50.1167}) } }, "relationship": { "identity": 4, "start": 1520007, "end": 1520008, "type": "DIRECT", "properties": { "dist": 393150.0 } }, "end": { "identity": 1520008, "labels": [ "City" ], "properties": { "name": "Hamburg", "lon": 9.994583, "lat": 53.554423, "coords": point({srid:4326, x:9.994583, y:53.554423}) } } } ], "length": 2.0 } ----

Or equivalently, with the same result, leveraging on coords node property, which is a Point, with the same configurations. Note that in case of a 3d-coordinate, the procedure will pick only the x and y or the longitude and latitude values.

MATCH (from:City {name:'München'}), (to:City {name:'Hamburg'})
CALL apoc.algo.aStarConfig(from, to, 'DIRECT', {pointPropName:'coords', weight:'dist', default:100})
YIELD weight, path
RETURN weight, path