Search code examples
neo4jcypherneo4j-apoc

Neo4J APOC A* and Dijkstra Conditions

I'm currently using built-in dijkstra for Neo4J path finding using conditions (see-below).

CYPHER

PROFILE MATCH path = shortestpath((s:Node {UID: 73946372})-[Road*]->(e:Node {UID: 2383529534}))
WHERE ALL(x in relationships(path) WHERE x.LG_6 > 0 || x.C60 > 100)
WITH path, reduce(s = 0, r IN relationships(path) | s + r.Length) AS dist
RETURN path, dist LIMIT 1

However, I would like to know if it's possible to do the same with APOC and have conditions such as x.LG_6 > 2000 AND x.C60> 0. The cypher below is what I currently use but they have no conditions.

APOC A*

PROFILE MATCH (s:Node {UID: 73946372}),(e:Node {UID: 2383529534})
CALL apoc.algo.aStar(s, e, 'Road', 'Length','Latitude','Longitude') YIELD path, weight
RETURN path, weight LIMIT 1

APOC Dijkstra

PROFILE MATCH (s:Node {UID: 73946372}),(e:Node {UID: 2383529534})
CALL apoc.algo.dijkstra(s, e, 'Road', 'Length') YIELD path AS path, weight AS weight
RETURN path, weight LIMIT 1
Solution

    1. The Cypher function shortestPath does not use a relationship weight property to calculate the shortest path -- it only uses the length of the path (i.e., the number of relationships in the path).

      So the dist returned by your first query is misleading, since it is NOT what the shortestPath function looked at to determine the path result. This is also why your first query's result may not match the result of another algorithm that does use a weight property.

    2. The Graph Algorithms plugin contains path-finding algorithms that support (via Cypher projection) what you want, and they can use a weight property. The stream variants of those methods return the native ID of each node in the resulting path, along with the total weight up to that point in the path. Currently, this plugin is only supported by neo4j version 3.5.14 and below.

    For example:

    A*

    MATCH (s:Node {UID: 73946372}), (e:Node {UID: 2383529534})
CALL algo.shortestPath.astar.stream(s, e, null, 'Latitude', 'Longitude', {
  nodeQuery: 'MATCH (p:Node) RETURN id(p) as id',
  relationshipQuery: 'MATCH (a:Node)-[x:Road]->(b:Node) WHERE x.LG_6 > 0 || x.C60 > 100 RETURN id(a) AS source, id(b) AS target, x.Length AS weight',
  graph: 'cypher'
}) YIELD nodeId, cost
RETURN nodeId,cost

    Dijkstra

    MATCH (s:Node {UID: 73946372}), (e:Node {UID: 2383529534})
CALL algo.shortestPath.stream(s, e, null, {
  nodeQuery: 'MATCH (p:Node) RETURN id(p) as id',      
  relationshipQuery: 'MATCH (a:Node)-[x:Road]->(b:Node) WHERE x.LG_6 > 0 || x.C60 > 100 RETURN id(a) AS source, id(b) AS target, x.Length AS weight',
  graph: 'cypher'
}) YIELD nodeId, cost
RETURN nodeId, cost