FIltering out intermediate points in ArangoDB traversal

Question

Given a graph via "contains" I have the following:

D contains LibD
C contains LibC and D
B contains LibB and D
A contains LibA, B, and C

Using:

FOR v,e,p IN 1..50 INBOUND 'pmconfig/899018092734' pm_content RETURN p.vertices

I get the following paths:

A->B->LibB
A->B->D->LibD
A->B->D
A->B
A->LibA
A->C->LibC
A->C->D->LibD
A->C->D
A->C

I'd like to filter out intermediate points so I get:

A->B->LibB
A->B->D->LibD
A->LibA
A->C->LibC
A->C->D->LibD

If the LibX elements were leafs, I could add a filter like

FILTER LENGTH(EDGES(pm_content,v._id,'inbound'))==0

But suppose I had one path: A->B->C->D->B

In this case I would filter everything out. What I would like to have is A->B->C->D since the walk should stop when it recognizes a cycle.

How can I construct a filter that removes intermediate points? Specifically, only those that end with a leaf node or all content links point to vertex that were already traversed.

dothebart dothebart · Accepted Answer · 2016-05-19T13:54:14

To filter the "unfinished paths" we need to predict whether the traverser would be able to continue its journey further down along the graph.

The only way to find out is to try - so we add a second traversal originating from the current vertex (v) in a sub query, which goes one step at most.

The sub-query will return two possible results: [1] if there are more nodes, [] if not. We can test for this using the LENGTH() function.

We will then use this information to filter the unfinished paths from the result:

FOR v,e,p IN 1..50 INBOUND 'pmconfig/899018092734' pm_content
  LET next = (FOR x IN 1 INBOUND v pm_content LIMIT 1 RETURN 1)
  FILTER LENGTH(next) == 0
  RETURN p.vertices

Lets try to test this on the Traversal Graph; We change the direction to OUTBOUND since we get more results with that easily. We Restrict the output to only give us the _key, so we can revalidate the result without problems.

var examples = require("org/arangodb/graph-examples/example-graph.js");
var graph = examples.loadGraph("traversalGraph");
db._query(`
FOR v,e,p IN 1..50 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
  LET next = (FOR x IN 1 OUTBOUND v GRAPH 'traversalGraph' LIMIT 1 RETURN 1)
  FILTER LENGTH(next) == 0
  RETURN p.vertices[*]._key
`).toArray()

[ 
  [ "A", "B", "C", "D" ], 
  [ "A", "B", "E", "F" ], 
  [ "A", "G", "H", "I" ], 
  [ "A", "G", "J", "K" ] 
]

As we can see, we only get the paths to the endpoints - as expected.

FIltering out intermediate points in ArangoDB traversal

1 Answers