How to stop traversal based on inbound edge

Question

I have a graph in ArangoDB with two vertices collections, P and F, and one edge collection with two types of edges: fp and hp.

Note that the image above has been simplified - the "F" nodes connect themselves to other F nodes via more "fp" edges. In other words, I do not know in advance (for example) if "F4" has an inbound "fp" edge or more.

I would like to use one AQL query to traverse the graph, starting from node PA, but stopping at any vertex that do not have an inbound "hp" edge. The Documentation indicates that the way to stop traversal is to use a query like:

FOR v, e, p IN 0..100 OUTBOUND 'P/PA'GRAPH 'test'
  FILTER p.<vertices|edges>... <condition>
  RETURN v

And I would like to see:

PA, PC, PE, PF 

But I don't know how to achieve that without first populating a new property on the "P" nodes indicating that they have an inbound "fp" edge. If I did that, this would then be possible:

FOR v, e, p IN 0..100 OUTBOUND 'P/PA'GRAPH 'test'
  FILTER p.vertices[*].hasFP ALL == true
  RETURN v

Is there a way to achieve this without the pre-processing step, in one AQL query?

Answer 1

You can do this with the following query. It starts a traversal at your starting point P/PA and check whether there is no connecting edge (needed for the starting point itself) or the type of the edge is hp. Then it starts another traversal for every found vertex directly or indirectly connected with P/PA with a depth of 1 and direction INBOUND. Here it filters for edge type equal fp and return the vertex from the surrounding traversal. You need DISTINCT in this RETURN otherwise your starting point will be returned twice.

FOR v, e, p IN 0..100 OUTBOUND 'P/PA' GRAPH 'test'
  FILTER e == null
  OR e.type == 'hp'
  FOR v1, e1, p1 IN 1 INBOUND v._id GRAPH 'test'
    FILTER e1.type == 'fp'
    RETURN DISTINCT v

Answer 2

If I understand the question correctly, the answer is: use a sub-query to check the condition. Unfortunately, however, at the moment, AQL does not support pruning, so (with the current version, i.e. 3.2), this approach may be too slow.

In brief, the sub-query would look like this:

(FOR v0 IN p.vertices
   LET hasP = (FOR v1, e1 IN 1..1 INBOUND v0 GRAPH “test”
                 FILTER e1.type == “fp”
                 COLLECT WITH COUNT INTO c
                 RETURN c>0)
   FILTER hasP
   COLLECT WITH COUNT INTO c
   RETURN c == LENGTH(p.vertices) )