apoc.algo.aStarConfig

Details

Syntax

apoc.algo.aStarConfig(startNode, endNode, relTypesAndDirections, config) :: (path, weight)

Description

Runs the A* search algorithm to find the optimal path between two NODE values, using the given RELATIONSHIP property name for the cost function. This procedure looks for weight, latitude and longitude properties in the config.

Input arguments

Name

Type

Description

startNode

NODE

The node to start the search from.

endNode

NODE

The node to end the search on.

relTypesAndDirections

STRING

The relationship types to restrict the algorithm to. Relationship types are represented using APOC’s rel-direction-pattern syntax; [<]RELATIONSHIP_TYPE1[>]|[<]RELATIONSHIP_TYPE2[>]|…​.

config

MAP

{ weight = 'distance' :: STRING, default = Double.MAX_VALUE :: FLOAT, y = 'latitude' :: STRING, x = 'longitude' :: STRING, pointPropName :: STRING }

Return arguments

Name

Type

Description

path

PATH

The path result.

weight

FLOAT

The weight of the given path.

Example

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
Results
weight path

697430.0

{
  "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