Neo4j: Customize Path Traversal

Question

I am pretty new to Neo4j. I have implemented an example use case with the following setup:

• acyclic directed graph
• nodes have a property called externalID
• Nodes:
  • Node Type S (Start Node)
  • Node Type E (End Node)
  • Node Type I (Intermediate Node)
• Relations:
  • Node Type S can only have outgoing relations to Nodes of Type I
  • Node Type I can have ingoing relations from I and S
  • Node Type I can have outgoing relations to I and E
  • Node Type E can only have incomming relations from I
  • All relations have a weight property assigned which can be any number

With the help of stackoverflow and several tutorials I was able to formulate a Cypher query which gets me all paths from any start node with one externalID to the matching end node with the same externalID.

MATCH p=(a:S)-[r*]->(b:E) 
WHERE a.externalID=b.externalID
WITH p, relationships(p) as rcoll 
RETURN p

The query works more or less good so far ...

However, I have no idea how to change the behavior on how the graph is scanned for possible paths. Actually I only need a subset of all possible paths. Such paths fulfill the following requirement:

• The path traversal is started at a Start Node S with a given capacity C.
• if a relationship is traversed the weight property of this relationship is subtracted from the current capacity C (that means negative weights are added)
  • if the capacity gets negative the path up to this point is invalid (the path up to the previous node is still valid and may continue with other relationships)
  • if the capacity is still positive continue with another relationship from this point and use the result of C - weight as new C

Can I somehow adjust the query or is there any other possibility with Neo4j to get all paths using the strategy above?

Thanks a lot for your help in advance.

Answer 1

This Cypher query might be suitable for your use case:

MATCH p = (a:S)-[r*]->(b:E) 
WHERE a.externalID = b.externalID
WITH
  p,
  REDUCE(c = a.capacity, r IN RELATIONSHIPS(p) |
    CASE WHEN c < 0 THEN -1 ELSE c - r.weight END) AS residual
WHERE residual >= 0
RETURN p;

The REDUCE clause will set residual to a negative value if the capacity is ever reduced below 0, even if subsequent weights would normally cause it to go positive.