4

Suppose I have a neo4j database with a single node type and a single relationship type to keep things simple. All relationships have a "cost" property (as in classical graph problems), whose values are non-negative.

Suppose now I want to find all the possible paths between node with ID A and node with ID B, with an upper bound on path length (e.g. 10) such that the total path cost is below or equal to a given constant (e.g. 20).

The Cypher code to accomplish this is the following (and it works):

START a = node(A), b = node(B)
MATCH (a) -[r*0..10]-> (b)
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
WHERE totalcost < 20
RETURN costs, totalcost

The problem with this query is that it doesn't take advange of the fact that costs are non-negative and thus paths where the total cost limit is passed can be pruned. Instead, it lists all possible paths of length 0 to 10 between nodes A and B (which can be ridiculously expensive), calculates total costs and then filters out paths that fall above the limit. Pruning paths in time would lead to massive performance improvements.

I know this is doable with the traversal framework by using BranchStates and preventing expansion when relevant, but I would like to find a Cypher solution (mainly due to the reasons exposed here).

I am currently using version 2.2.2, if that matters.

Community
  • 1
  • 1
Gerardo Lastra
  • 645
  • 5
  • 15

1 Answers1

0

Would a sum of relationships costs before the extract be sufficient ?

START a = node(A), b = node(B)
MATCH (a)-[r*0..10]->(b)
WHERE sum(r.cost) < 20
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
RETURN costs, totalcost

By the way, wanting to prune is meaning you want imperative way !

Also, please help Cypher a bit, use labels

Christophe Willemsen
  • 19,399
  • 2
  • 29
  • 36
  • I am getting an "Invalid use of aggregating function sum(...)" if I do that. I have the feeling aggregating functions cannot be used in the WHERE clause (somewhat akin to SQL). Regarding labels, that is not my raw Cypher code, just an example (and as I mentioned in the first sentence, we should assume only one type of node and one type of relationship, so labels don't really matter here, do they?). – Gerardo Lastra Jun 23 '15 at 20:28
  • Oh, and regarding the "wanting to prune" part, I do not "want" to prune. Pruning would give back my results (declarative way) in a more efficient way. Also, specifying whether the result can be pruned (or perhaps specifying a broader concept, like the non-negativity of a property) is by no means imperative. – Gerardo Lastra Jun 23 '15 at 20:35