Graph traversals in AQL

Syntax

There are two slightly different syntaxes for traversals in AQL, one for

• named graphs and another to
• specify a set of edge collections (anonymous graph).

Working with named graphs

The syntax for AQL graph traversals using named graphs is as follows (square brackets denote optional parts and | denotes alternatives):

FOR node[, edge[, path]]
  IN [min[..max]]
  OUTBOUND|INBOUND|ANY startNode
  GRAPH graphName
  [PRUNE [pruneVariable = ]pruneCondition]
  [OPTIONS options]

• FOR: emits up to three variables:

  • node (object): the current node in a traversal
  • edge (object, optional): the current edge in a traversal
  • path (object, optional): representation of the current path with the following attributes:
    • vertices: An array of all nodes on this path.
    • edges: An array of all edges on this path.
    • weights: An array of the edge weight sums at each depth of this path. See the "weighted" setting of the order traversal option.

• IN min..max: the minimal and maximal depth for the traversal:

  • min (number, optional): edges and nodes returned by this query start at the traversal depth of min (thus edges and nodes below it are not returned). If not specified, it defaults to 1. The minimal possible value is 0.
  • max (number, optional): up to max length paths are traversed. If omitted, max defaults to min. Thus only the nodes and edges in the range of min are returned. max cannot be specified without min.

• OUTBOUND|INBOUND|ANY: follow outgoing, incoming, or edges pointing in either direction in the traversal. Note that this can’t be replaced by a bind parameter.

• startNode (string|object): a node where the traversal originates from. This can be specified in the form of an ID string or in the form of a document with the _id attribute. All other values lead to a warning and an empty result. If the specified document does not exist, the result is empty as well and there is no warning.

• GRAPH graphName (string): the name identifying the named graph. Its node and edge collections are looked up. Note that the graph name is like a regular string, hence it must be enclosed by quote marks, like GRAPH "graphName".

• PRUNE expression (AQL expression, optional): An expression, like in a FILTER statement, which is evaluated in every step of the traversal, as early as possible. The semantics of this expression are as follows:

  • If the expression evaluates to false, the traversal continues on the current path.
  • If the expression evaluates to true, the traversal does not continue on the current path. However, the paths up to this point are considered as a result (they might still be post-filtered or ignored due to depth constraints). For example, a traversal over the graph (A) -> (B) -> (C) starting at A and pruning on B results in (A) and (A) -> (B) being valid paths, whereas (A) -> (B) -> (C) is not returned because it gets pruned on B.

  You can only use a single PRUNE clause per FOR traversal operation, but the prune expression can contain an arbitrary number of conditions using AND and OR statements for complex expressions. You can use the variables emitted by the FOR operation in the prune expression, as well as all variables defined before the traversal.

  You can optionally assign the prune expression to a variable like PRUNE var = <expr> to use the evaluated result elsewhere in the query, typically in a FILTER expression.

  See Pruning for details.

• OPTIONS options (object, optional): See the traversal options.

Working with collection sets

The syntax for AQL graph traversals using collection sets is as follows (square brackets denote optional parts and | denotes alternatives):

[WITH nodeCollection1[, nodeCollection2[, nodeCollectionN]]]
FOR node[, edge[, path]]
  IN [min[..max]]
  OUTBOUND|INBOUND|ANY startNode
  edgeCollection1[, edgeCollection2[, edgeCollectionN]]
  [PRUNE [pruneVariable = ]pruneCondition]
  [OPTIONS options]

• WITH: Declaration of collections. Optional for single server instances, but required for graph traversals in a cluster. Needs to be placed at the very beginning of the query.

  • collections (collection, repeatable): list of node collections that are involved in the traversal

• edgeCollections (collection, repeatable): One or more edge collections to use for the traversal (instead of using a named graph with GRAPH graphName). Node collections are determined by the edges in the edge collections.

  You can override the default traversal direction by setting OUTBOUND, INBOUND, or ANY before any of the edge collections.

  If the same edge collection is specified multiple times, it behaves as if it were specified only once. Specifying the same edge collection is only allowed when the collections do not have conflicting traversal directions.

  Views cannot be used as edge collections.

• See the named graph variant for the remaining traversal parameters as well as the traversal options. The edgeCollections restriction option is redundant in this case.

Traversal options

You can optionally specify the following options to modify the execution of a graph traversal. If you specify unknown options, query warnings are raised.

order

Specify which traversal algorithm to use (string):

• "bfs": The traversal is executed breadth-first. The results first contain all nodes at depth 1, then all nodes at depth 2, and so on.

• "dfs" (default): The traversal is executed depth-first. It first returns all paths from min depth to max depth for one node at depth 1, then for the next node at depth 1, and so on.

• "weighted": The traversal is a weighted traversal. Paths are enumerated with increasing cost. The order of paths having the same cost is non-deterministic.

  You can define what attribute to use as the cost of an edge with the weightAttribute traversal option, as well as a fallback with defaultWeight. Negative weights are not supported and abort the query with an error.

  The path variable emitted by the traversal has a weights attribute with a list of the calculated edge weight sums at each depth:

  • Depth 0: The first value is always 0.
  • Depth 1: The second value is the weight of the edge between the start node and the direct neighbor node.
  • Depth 2: The third value is the sum of weights of the edges between the start node, the direct neighbor node, and the neighbor’s neighbor node.
  • And so on for greater depths, summing all edge weights along the path.

  Note that the weightAttribute and defaultWeight options are ignored for traversal orders other than "weighted", which means the weights attribute is like [0, 1, 2, 3, …] for e.g. order: "dfs" and therefore not useful.

uniqueVertices

Ensure node uniqueness (string):

• "path" – it is guaranteed that there is no path returned with a duplicate node
• "global" – it is guaranteed that each node is visited at most once during the traversal, no matter how many paths lead from the start node to this one. If you start with a min depth > 1 a node that was found before min depth might not be returned at all (it still might be part of a path). It is required to set order: "bfs" or order: "weighted" because with depth-first search the results would be unpredictable. Note: Using this configuration the result is not deterministic any more. If there are multiple paths from startNode to node, one of those is picked. In case of a weighted traversal, the path with the lowest weight is picked, but in case of equal weights it is undefined which one is chosen.
• "none" (default) – no uniqueness check is applied on nodes

uniqueEdges

Ensure edge uniqueness (string):

• "path" (default) – it is guaranteed that there is no path returned with a duplicate edge
• "none" – no uniqueness check is applied on edges. Note: Using this configuration, the traversal follows edges in cycles.

edgeCollections

Restrict edge collections the traversal may visit (string|array).

If omitted or an empty array is specified, then there are no restrictions.

• A string parameter is treated as the equivalent of an array with a single element.
• Each element of the array should be a string containing the name of an edge collection.

vertexCollections

Restrict node collections the traversal may visit (string|array).

If omitted or an empty array is specified, then there are no restrictions.

• A string parameter is treated as the equivalent of an array with a single element.
• Each element of the array should be a string containing the name of a node collection.
• The starting node is always allowed, even if it does not belong to one of the collections specified by a restriction.

parallelism

Parallelize traversal execution (number).

If omitted or set to a value of 1, the traversal execution is not parallelized. If set to a value greater than 1, then up to that many worker threads can be used for concurrently executing the traversal. The value is capped by the number of available cores on the target machine.

Parallelizing a traversal is normally useful when there are many inputs (start nodes) that the nested traversal can work on concurrently. This is often the case when a nested traversal is fed with several tens of thousands of start nodes, which can then be distributed randomly to worker threads for parallel execution.

maxProjections

Specifies the number of document attributes per FOR loop to be used as projections (number). The default value is 5.

The AQL optimizer automatically detects which document attributes you access in traversal queries and optimizes the data loading. This optimization is beneficial if you have large documents but only access a few document attributes. The maxProjections option lets you tune when to load individual attributes versus the whole document.

indexHint

Introduced in: v3.12.1

You can provide index hints for traversals to let the optimizer prefer the vertex-centric indexes you specify over the regular edge index.

This is useful for cases where the selectively estimate of the edge index is higher than the ones for suitable vertex-centric indexes (and thus they aren’t picked automatically) but the vertex-centric indexes are known to perform better.

The indexHint option expects an object in the following format:

{ "<edgeColl>": { "<direction>": { "<level>": <index> } } }

• <edgeColl>: The name of an edge collection for which the index hint shall be applied. Collection names are case-sensitive.
• <direction>: The direction for which to apply the index hint. Valid values are inbound and outbound, in lowercase. You can specify indexes for both directions.
• <level>: The level/depth for which the index should be applied. Valid values are the string base (to define the default index for all levels) and any stringified integer values greater or equal to zero. You can specify multiple levels.
• <index>: The name of an index as a string, or multiple index names as a list of strings in the order of preference. The optimizer uses the first suitable index.

Because collection names and levels/depths are used as object keys, enclose them in quotes to avoid query parse errors.

Example:

FOR v, e, p IN 1..4 OUTBOUND startNode edgeCollection
OPTIONS {
  indexHint: {
    "edgeCollection": {
      "outbound": {
        "base": ["edge"],
        "1": "myIndex1",
        "2": ["myIndex2", "myIndex1"],
        "3": "myIndex3",
      }
    }
  }
}
FILTER p.edges[1].foo == "bar" AND
       p.edges[2].foo == "bar" AND
       p.edges[2].baz == "qux"

Index hints for levels other than base are only considered if the traversal actually uses a specific filter condition for the specified level. In the above example, this is true for levels 1 and 2, but not for level 3. Consequently, the index hint for level 3 is ignored here.

An expression like FILTER p.edges[*].foo ALL == "bar" cannot utilize the indexes you specify for individual levels (level 1, level 2, etc.) but uses the index for the base level.

The vertex-centric indexes you specify are only used if they are eligible and the index hints for traversals cannot be forced.

weightAttribute

This option is only used for traversals with order: "weighted".

The edge attribute to use as the weight (string|array):

• A string refers to a top-level attribute of exactly this name. A . is interpreted as a literal dot and not as a separator for an attribute path. For example, "attr.sub" reads the weight from an edge document like { "attr.sub": 5 }.

• An array of strings describes an attribute path, letting you use a sub-attribute as the edge weight. Each element is one level of nesting, for example ["attr", "sub"] to read the weight from an edge document like { "attr": { "sub": 3 } }.

  An array with a single element is equivalent to passing that element as a string. ["attr.sub"] therefore refers to the top-level attribute attr.sub just like "attr.sub" does.

If the value is neither a string nor an array of strings, a query warning is raised and the option is ignored, which means the defaultWeight is used as the weight of every edge. An empty string or an empty array has the same effect but raises no warning.

For example, consider edge documents with both a nested sub attribute and a top-level attribute whose name contains a dot:

{
  "attr": { "sub": 3 },
  "attr.sub": 5
}

FOR v, e, p IN 1..3 OUTBOUND startNode edgeCollection
  OPTIONS { order: "weighted", weightAttribute: ["attr", "sub"] }
  RETURN p.weights

If no attribute is specified, or if the attribute path cannot be resolved in the edge document, or if the value it refers to is non-numeric, then the defaultWeight is used.

The attribute value must not be negative.

defaultWeight

This option is only used for traversals with order: "weighted".

Specifies the default weight of an edge (number). The default value is 1.

The value must not be negative.

useCache

Introduced in: v3.12.2

Whether to use the in-memory cache for edges. The default is true.

You can set this option to false to not make a large graph operation pollute the edge cache.

Traversing in mixed directions

For traversals with a list of edge collections you can optionally specify the direction for some of the edge collections. Say for example you have three edge collections edges1, edges2 and edges3, where in edges2 the direction has no relevance but in edges1 and edges3 the direction should be taken into account. In this case you can use OUTBOUND as general traversal direction and ANY specifically for edges2 as follows:

FOR node IN OUTBOUND
  startNode
  edges1, ANY edges2, edges3

All collections in the list that do not specify their own direction use the direction defined after IN. This allows you to use a different direction for each collection in your traversal.

Graph traversals in a cluster

Due to the nature of graphs, edges may reference nodes from arbitrary collections. Following the paths can thus involve documents from various collections and it is not possible to predict which are visited in a path search - unless you use named graphs that define all node and edge collections that belong to them and the graph data is consistent.

If you use anonymous graphs / collection sets for graph queries, which node collections need to be loaded by the graph engine can be deduced automatically if there is a named graph with a matching edge collection in its edge definitions (introduced in v3.12.6). Edge collections are always declared explicitly in queries, directly or via referencing a named graph.

Without a named graph, the involved node collections can only be determined at run time. Use the WITH operation to declare the node collections upfront. This is required for traversals using collection sets in cluster deployments (if there is no named graph to deduce the node collections from). Declare the collection of the start node as well if it’s not declared already (like by a FOR loop).

For example, suppose you have two node collections, person and movie, and an acts_in edge collection that connects them. If you want to run a traversal query that starts at a person that you specify with its document ID, you need to declare both node collections at the beginning of the query:

WITH person, movie
FOR v, IN 0..1 OUTBOUND "person/1544" acts_in
  LIMIT 4
  RETURN v.label

However, if there is a named graph that includes an edge definition for the acts_in edge collection, with person as the from collection and movie as the to collection, you can omit WITH person, movie. That is, if you specify acts_in as an edge collection in an anonymous graph query, all named graphs are checked for this edge collection, and if there is a matching edge definition, its node collections are automatically added as data sources to the query.

FOR v, IN 0..1 OUTBOUND "person/1544" acts_in
  LIMIT 4
  RETURN v.label

// Chris Rock
// A.I. Artificial Intelligence
// Lethal Weapon 4
// Madagascar

You can still declare collections manually, in which case they are added as data sources in addition to automatically deduced collections.

Pruning

You can define stop conditions for graph traversals to return specific data and to improve the query performance. This is called pruning and works by checking conditions during the traversal as opposed to filtering the results afterwards (post-filtering). This reduces the amount of data to be checked by stopping the traversal down specific paths early.

You can specify one PRUNE expression per graph traversal, but it can contain an arbitrary number of conditions. You can use the node, edge, and path variables emitted by the traversal in a prune expression, as well as all other variables defined before the FOR operation. Note that PRUNE is an optional clause of the FOR operation and that the OPTIONS clause needs to be placed after PRUNE.

FOR v, e, p IN 0..10 OUTBOUND "places/Toronto" GRAPH "kShortestPathsGraph"
  PRUNE v.label == "Edmonton"
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", p.vertices[*].label)

[ 
  "Toronto", 
  "Toronto -- Winnipeg", 
  "Toronto -- Winnipeg -- Saskatoon", 
  "Toronto -- Winnipeg -- Saskatoon -- Edmonton" 
]

The above example shows a graph traversal using a train station and connections dataset:

The traversal starts at Toronto (bottom left), the traversal depth is limited to 10, and every station is only visited once. The traversal could continue up to Vancouver (bottom right) at depth 5, but it is stopped early on this path (the only path in this example) at Edmonton because of the prune expression.

The traversal along paths is stopped as soon as the prune expression evaluates to true for a given path. The current depth is still included in the result, however. This can be seen in the query result of the example which includes the Edmonton node at which it stopped.

The following example starts a traversal at London (middle right), with a depth between 2 and 3, and every station is only visited once. The station names as well as the travel times are returned:

FOR v, e, p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2.5 -- Brussels -- 2 -- Cologne", 
  "London -- 2 -- York -- 3.5 -- Carlisle", 
  "London -- 2 -- York -- 3.5 -- Carlisle -- 2 -- Birmingham", 
  "London -- 2 -- York -- 3.5 -- Carlisle -- 1 -- Glasgow", 
  "London -- 2 -- York -- 4 -- Edinburgh", 
  "London -- 2 -- York -- 4 -- Edinburgh -- 1 -- Glasgow", 
  "London -- 2 -- York -- 4 -- Edinburgh -- 3 -- Leuchars", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle -- 2.5 -- York", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle -- 1 -- Glasgow" 
]

The same example with an added prune expression, with node and edge conditions:

FOR v, e, p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE v.label == "Carlisle" OR e.travelTime > 3
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2.5 -- Brussels -- 2 -- Cologne", 
  "London -- 2 -- York -- 3.5 -- Carlisle", 
  "London -- 2 -- York -- 4 -- Edinburgh", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle" 
]

If either the Carlisle node or an edge with a travel time of over three hours is encountered, the subsequent paths are pruned. In the example, this removes the train connections to Birmingham, Glasgow, and York, which come after Carlisle, as well as the connections to and via Edinburgh because of the four hour duration for the section from York to Edinburgh.

If your graph is comprised of multiple node or edge collections, you can also prune as soon as you reach a certain collection, using a condition like PRUNE IS_SAME_COLLECTION("stopCollection", v).

If you want to only return the results of the depth at which the traversal stopped due to the prune expression, you can use a FILTER in addition. You can assign the evaluated result of a prune expression to a variable (PRUNE var = <expr>) and use it for filtering:

FOR v, e, p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE cond = v.label == "Carlisle" OR e.travelTime > 3
  OPTIONS { uniqueVertices: "path" }
  FILTER cond
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2 -- York -- 3.5 -- Carlisle", 
  "London -- 2 -- York -- 4 -- Edinburgh", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle" 
]

Only paths that end at Carlisle or with the last edge having a travel time of over three hours are returned. This excludes the connection to Cologne from the results compared to the previous query.

If you want to exclude the depth at which the prune expression stopped the traversal, you can assign the expression to a variable and use its negated value in a FILTER:

FOR v, e, p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE cond = v.label == "Carlisle" OR e.travelTime > 3
  OPTIONS { uniqueVertices: "path" }
  FILTER NOT cond
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2.5 -- Brussels -- 2 -- Cologne" 
]

This only returns the connection to Cologne, which is the opposite of the previous example.

You may combine the prune variable with arbitrary other conditions in a FILTER operation. For example, you can remove results where the last edge has as lower travel time than the second to last edge of the path:

FOR v, e, p IN 2..5 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE cond = v.label == "Carlisle" OR e.travelTime > 3
  OPTIONS { uniqueVertices: "path" }
  FILTER cond AND p.edges[-1].travelTime >= p.edges[-2].travelTime
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2 -- York -- 3.5 -- Carlisle", 
  "London -- 2 -- York -- 4 -- Edinburgh" 
]

The following examples shows a graph traversal starting at London, with a traversal depth between 2 and 3, and every station is only visited once:

FOR v, e, p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2.5 -- Brussels -- 2 -- Cologne", 
  "London -- 2 -- York -- 3.5 -- Carlisle", 
  "London -- 2 -- York -- 3.5 -- Carlisle -- 2 -- Birmingham", 
  "London -- 2 -- York -- 3.5 -- Carlisle -- 1 -- Glasgow", 
  "London -- 2 -- York -- 4 -- Edinburgh", 
  "London -- 2 -- York -- 4 -- Edinburgh -- 1 -- Glasgow", 
  "London -- 2 -- York -- 4 -- Edinburgh -- 3 -- Leuchars", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle -- 2.5 -- York", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle -- 1 -- Glasgow" 
]

If you add prune conditions to stop the traversal if the station is Glasgow or the travel time less than some number, no results are turned. This is even the case for a value of 2.5, for which two paths exist that fulfill the criterion – to Cologne and Carlisle:

FOR v,e,p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE v.label == "Glasgow" OR e.travelTime < 2.5
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ ]

The problem is that null, false, and true are all less than any number (< 2.5) because of AQL’s Type and value order, and because the edge at depth 0 is always null. The prune condition is accidentally fulfilled at the start node, stopping the traversal too early. This similarly happens if you check an edge attribute for inequality (!=) and compare it to string, for instance, which evaluates to true for the null value.

The depth at which a traversal is stopped by pruning is considered as a result, but in the above example, the minimum depth of 2 filters the start node out. If you lower the minimum depth to 0, you get London as the sole result. This confirms that the traversal stopped at the start node.

To avoid this problem, exclude the null value. For example, you can use e.travelTime > 0 AND e.travelTime < 2.5, but more generic solutions are to exclude depth 0 from the check (LENGTH(p.edges) > 0) or to simply ignore the null edge (e != null):

FOR v,e,p IN 2..3 OUTBOUND "places/London" GRAPH "kShortestPathsGraph"
  PRUNE v.label == "Glasgow" OR (e != null AND e.travelTime < 2.5)
  OPTIONS { uniqueVertices: "path" }
  RETURN CONCAT_SEPARATOR(" -- ", INTERLEAVE(p.vertices[*].label, p.edges[*].travelTime))

[ 
  "London -- 2.5 -- Brussels -- 2 -- Cologne", 
  "London -- 2.5 -- Birmingham -- 1 -- Carlisle" 
]

Using filters

All three variables emitted by the traversals might as well be used in filter statements. For some of these filter statements the optimizer can detect that it is possible to prune paths of traversals earlier, hence filtered results are not emitted to the variables in the first place. This may significantly improve the performance of your query. Whenever a filter is not fulfilled, the complete set of node, edge and path is skipped. All paths with a length greater than the max depth are never computed.

Filter conditions that are AND-combined can be optimized, but OR-combined conditions cannot.

Filtering on paths

Filtering on paths allows for the second most powerful filtering and may have the second highest impact on performance. Using the path variable you can filter on specific iteration depths. You can filter for absolute positions in the path by specifying a positive number (which then qualifies for the optimizations), or relative positions to the end of the path by specifying a negative number.

Filtering edges on the path

This example traversal filters all paths where the start edge (index 0) has the attribute theTruth equal to true. The resulting paths are up to 5 items long:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[0].theTruth == true
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ 
  { 
    "vertices" : [ 
      "A", 
      "G" 
    ], 
    "edges" : [ 
      "right_foo" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J", 
      "K" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip", 
      "right_zup" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H", 
      "I" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob", 
      "right_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B" 
    ], 
    "edges" : [ 
      "left_bar" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E", 
      "F" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub", 
      "left_schubi" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C", 
      "D" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg", 
      "left_blorg" 
    ] 
  } 
]

Filtering nodes on the path

Similar to filtering the edges on the path, you can also filter the nodes:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.vertices[1]._key == "G"
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ 
  { 
    "vertices" : [ 
      "A", 
      "G" 
    ], 
    "edges" : [ 
      "right_foo" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J", 
      "K" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip", 
      "right_zup" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H", 
      "I" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob", 
      "right_blub" 
    ] 
  } 
]

Combining several filters

You can combine filters in any way you like:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[0].theTruth == true
       AND p.edges[1].theFalse == false
    FILTER p.vertices[1]._key == "G"
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J", 
      "K" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip", 
      "right_zup" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H", 
      "I" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob", 
      "right_blub" 
    ] 
  } 
]

The query filters all paths where the first edge has the attribute theTruth equal to true, the first node is "G" and the second edge has the attribute theFalse equal to false. The resulting paths are up to 5 items long.

Note: Despite the min depth of 1, this only returns results of depth 2. This is because for all results in depth 1, the second edge does not exist and hence cannot fulfill the condition here.

Filter on the entire path

With the help of array comparison operators filters can also be defined on the entire path, like ALL edges should have theTruth == true:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[*].theTruth ALL == true
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ 
  { 
    "vertices" : [ 
      "A", 
      "G" 
    ], 
    "edges" : [ 
      "right_foo" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J", 
      "K" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip", 
      "right_zup" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H", 
      "I" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob", 
      "right_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B" 
    ], 
    "edges" : [ 
      "left_bar" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E", 
      "F" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub", 
      "left_schubi" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C", 
      "D" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg", 
      "left_blorg" 
    ] 
  } 
]

Or NONE of the edges should have theTruth == true:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[*].theTruth NONE == true
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ ]

Both examples above are recognized by the optimizer and can potentially use other indexes than the edge index.

It is also possible to define that at least one edge on the path has to fulfill the condition:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[*].theTruth ANY == true
    RETURN { vertices: p.vertices[*]._key, edges: p.edges[*].label }

[ 
  { 
    "vertices" : [ 
      "A", 
      "G" 
    ], 
    "edges" : [ 
      "right_foo" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "J", 
      "K" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_zip", 
      "right_zup" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "G", 
      "H", 
      "I" 
    ], 
    "edges" : [ 
      "right_foo", 
      "right_blob", 
      "right_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B" 
    ], 
    "edges" : [ 
      "left_bar" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "E", 
      "F" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blub", 
      "left_schubi" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg" 
    ] 
  }, 
  { 
    "vertices" : [ 
      "A", 
      "B", 
      "C", 
      "D" 
    ], 
    "edges" : [ 
      "left_bar", 
      "left_blarg", 
      "left_blorg" 
    ] 
  } 
]

It is guaranteed that at least one, but potentially more edges fulfill the condition. All of the above filters can be defined on nodes in the exact same way.

Filter a subset of the path

Introduced in: v3.12.11

An array expansion in a path filter can contain an inline FILTER to restrict which nodes or edges the array comparison operator applies to. This is useful if a condition is only meaningful for some of the path elements, for instance because an attribute is optional:

FOR v, e, p IN 1..5 OUTBOUND startNode GRAPH "myGraph"
  FILTER p.edges[* FILTER CURRENT.validUntil != null].validUntil ALL > DATE_NOW()
  RETURN p.edges[*]._key

Only the edges that have a validUntil attribute are compared against the current date. Without the inline FILTER, an edge without this attribute would evaluate null > DATE_NOW() to false and thus reject the entire path.

The optimizer can check such a condition during the traversal instead of filtering the emitted paths afterwards. Each node and edge is checked as the traversal reaches it, and the elements that the inline FILTER excludes are skipped. The traversal can thus stop following a path as soon as an element violates the condition, and the condition can be taken into account for the edge index lookups.

An inline FILTER only allows the condition to be evaluated during the traversal if all of the following apply. Otherwise, the condition remains a post-filter that is applied to the paths the traversal emits:

• The array comparison operator is ALL or NONE. ANY and AT LEAST (<number>) need to count the matching elements of the entire path and cannot be expressed as a condition for a single node or edge.
• The array expansion uses FILTER only, without an inline LIMIT or a RETURN projection. Both of them need the complete array and therefore the complete path.
• The inline FILTER condition doesn’t use the path variable, because the path isn’t available when the traversal evaluates a single node or edge. It may refer to CURRENT and to variables defined before the traversal, however.
• The inline FILTER condition doesn’t use the question mark operator.

Conditions that can be evaluated during the traversal:

// Only check the edges that have a `weight` attribute
FILTER p.edges[* FILTER CURRENT.weight != null].weight ALL <= 10

// `NONE` is supported as well, and so are function calls in the inline `FILTER`
FILTER p.edges[* FILTER HAS(CURRENT, "weight")].weight NONE > 10

// A variable from outside of the traversal can be used in the inline `FILTER`
FILTER p.edges[* FILTER CURRENT.weight > threshold].weight ALL <= 10

// A nested array expansion in the inline `FILTER` is allowed
FILTER p.edges[* FILTER LENGTH(CURRENT.tags[* FILTER CURRENT != "draft"]) > 0].weight ALL <= 10

Conditions that remain post-filters:

// `ANY` and `AT LEAST` cannot be checked per edge
FILTER p.edges[* FILTER CURRENT.weight != null].weight ANY <= 10
FILTER p.edges[* FILTER CURRENT.weight != null].weight AT LEAST (2) <= 10

// An inline `LIMIT` or `RETURN` needs the entire path
FILTER p.edges[* FILTER CURRENT.weight != null LIMIT 3].weight ALL <= 10
FILTER p.edges[* FILTER CURRENT.weight != null RETURN CURRENT.weight] ALL <= 10

// The inline `FILTER` cannot use the path variable
FILTER p.edges[* FILTER CURRENT.weight > LENGTH(p.vertices)].weight ALL <= 10

To check whether a condition is evaluated during the traversal, inspect the execution plan. If the optimize-traversals rule can move the condition into the traversal, no FilterNode remains for it.

Filtering on the path vs. filtering on nodes or edges

Filters on the emitted path (p variable) influence how the graph is traversed. If a path doesn’t fulfill a condition, the traversal may stop following this path and not explore it any further.

Filters on the emitted node (v variable) or edge (e variable) only determine whether the current node and edge become part of the result. The traversal walks past them either way, because vertices and edges further down the path may still match. This is comparable to setting a minimum traversal depth greater than zero. With a minimum depth of 2, the traversal still has to walk over the first two vertices of every path, you just don’t see them in the result.

Examples

Create a simple symmetric traversal demonstration graph:

var examples = require("@arangodb/graph-examples/example-graph");
var graph = examples.loadGraph("traversalGraph");
db.circles.toArray();
db.edges.toArray();
print("once you don't need them anymore, clean them up:");
examples.dropGraph("traversalGraph");

[ 
  { 
    "_key" : "A", 
    "_id" : "circles/A", 
    "_rev" : "_hg5kJV----", 
    "label" : "1" 
  }, 
  { 
    "_key" : "B", 
    "_id" : "circles/B", 
    "_rev" : "_hg5kJV---_", 
    "label" : "2" 
  }, 
  { 
    "_key" : "C", 
    "_id" : "circles/C", 
    "_rev" : "_hg5kJVC---", 
    "label" : "3" 
  }, 
  { 
    "_key" : "D", 
    "_id" : "circles/D", 
    "_rev" : "_hg5kJVC--_", 
    "label" : "4" 
  }, 
  { 
    "_key" : "E", 
    "_id" : "circles/E", 
    "_rev" : "_hg5kJVC--A", 
    "label" : "5" 
  }, 
  { 
    "_key" : "F", 
    "_id" : "circles/F", 
    "_rev" : "_hg5kJVC--B", 
    "label" : "6" 
  }, 
  { 
    "_key" : "G", 
    "_id" : "circles/G", 
    "_rev" : "_hg5kJVC--C", 
    "label" : "7" 
  }, 
  { 
    "_key" : "H", 
    "_id" : "circles/H", 
    "_rev" : "_hg5kJVG---", 
    "label" : "8" 
  }, 
  { 
    "_key" : "I", 
    "_id" : "circles/I", 
    "_rev" : "_hg5kJVG--_", 
    "label" : "9" 
  }, 
  { 
    "_key" : "J", 
    "_id" : "circles/J", 
    "_rev" : "_hg5kJVG--A", 
    "label" : "10" 
  }, 
  { 
    "_key" : "K", 
    "_id" : "circles/K", 
    "_rev" : "_hg5kJVG--B", 
    "label" : "11" 
  } 
]

[ 
  { 
    "_key" : "66331", 
    "_id" : "edges/66331", 
    "_from" : "circles/A", 
    "_to" : "circles/B", 
    "_rev" : "_hg5kJVG--C", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_bar" 
  }, 
  { 
    "_key" : "66333", 
    "_id" : "edges/66333", 
    "_from" : "circles/B", 
    "_to" : "circles/C", 
    "_rev" : "_hg5kJVG--D", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blarg" 
  }, 
  { 
    "_key" : "66335", 
    "_id" : "edges/66335", 
    "_from" : "circles/C", 
    "_to" : "circles/D", 
    "_rev" : "_hg5kJVK---", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blorg" 
  }, 
  { 
    "_key" : "66337", 
    "_id" : "edges/66337", 
    "_from" : "circles/B", 
    "_to" : "circles/E", 
    "_rev" : "_hg5kJVK--_", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blub" 
  }, 
  { 
    "_key" : "66339", 
    "_id" : "edges/66339", 
    "_from" : "circles/E", 
    "_to" : "circles/F", 
    "_rev" : "_hg5kJVK--A", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_schubi" 
  }, 
  { 
    "_key" : "66341", 
    "_id" : "edges/66341", 
    "_from" : "circles/A", 
    "_to" : "circles/G", 
    "_rev" : "_hg5kJVK--B", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_foo" 
  }, 
  { 
    "_key" : "66343", 
    "_id" : "edges/66343", 
    "_from" : "circles/G", 
    "_to" : "circles/H", 
    "_rev" : "_hg5kJVK--C", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_blob" 
  }, 
  { 
    "_key" : "66345", 
    "_id" : "edges/66345", 
    "_from" : "circles/H", 
    "_to" : "circles/I", 
    "_rev" : "_hg5kJVO---", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_blub" 
  }, 
  { 
    "_key" : "66347", 
    "_id" : "edges/66347", 
    "_from" : "circles/G", 
    "_to" : "circles/J", 
    "_rev" : "_hg5kJVO--_", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_zip" 
  }, 
  { 
    "_key" : "66349", 
    "_id" : "edges/66349", 
    "_from" : "circles/J", 
    "_to" : "circles/K", 
    "_rev" : "_hg5kJVO--A", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_zup" 
  } 
]

once you don't need them anymore, clean them up:

To get started we select the full graph. For better overview we only return the node IDs:

FOR v IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
  RETURN v._key

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

FOR v IN 1..3 OUTBOUND 'circles/A' edges RETURN v._key

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

We can nicely see that it is heading for the first outer node, then goes back to the branch to descend into the next tree. After that it returns to our start node, to descend again. As we can see both queries return the same result, the first one uses the named graph, the second uses the edge collections directly.

Now we only want the elements of a specific depth (min = max = 2), the ones that are right behind the fork:

FOR v IN 2..2 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
  RETURN v._key

[ 
  "J", 
  "H", 
  "E", 
  "C" 
]

FOR v IN 2 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
  RETURN v._key

[ 
  "J", 
  "H", 
  "E", 
  "C" 
]

As you can see, we can express this in two ways: with or without the max depth parameter.

Filter examples

Now let’s start to add some filters. We want to cut of the branch on the right side of the graph, we may filter in two ways:

• we know the node at depth 1 has _key == G
• we know the label attribute of the edge connecting A to G is right_foo

FOR v, e, p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.vertices[1]._key != 'G'
    RETURN v._key

[ 
  "B", 
  "E", 
  "F", 
  "C", 
  "D" 
]

FOR v, e, p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[0].label != 'right_foo'
    RETURN v._key

[ 
  "B", 
  "E", 
  "F", 
  "C", 
  "D" 
]

As we can see, all nodes behind G are skipped in both queries. The first filters on the node _key, the second on an edge label. Note again, as soon as a filter is not fulfilled for any of the three elements v, e or p, the complete set of these is excluded from the result.

We also may combine several filters, for instance to filter out the right branch (G), and the E branch:

FOR v,e,p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.vertices[1]._key != 'G'
    FILTER p.edges[1].label != 'left_blub'
    RETURN v._key

[ 
  "B", 
  "C", 
  "D" 
]

FOR v,e,p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.vertices[1]._key != 'G' AND p.edges[1].label != 'left_blub'
    RETURN v._key

[ 
  "B", 
  "C", 
  "D" 
]

As you can see, combining two FILTER statements with an AND has the same result.

Comparing OUTBOUND / INBOUND / ANY

All our previous examples traversed the graph in OUTBOUND edge direction. You may however want to also traverse in reverse direction (INBOUND) or both (ANY). Since circles/A only has outbound edges, we start our queries from circles/E:

FOR v IN 1..3 OUTBOUND 'circles/E' GRAPH 'traversalGraph'
    RETURN v._key

[ 
  "F" 
]

FOR v IN 1..3 INBOUND 'circles/E' GRAPH 'traversalGraph'
    RETURN v._key

[ 
  "B", 
  "A" 
]

FOR v IN 1..3 ANY 'circles/E' GRAPH 'traversalGraph'
    RETURN v._key

[ 
  "B", 
  "A", 
  "G", 
  "C", 
  "D", 
  "F" 
]

The first traversal only walks in the forward (OUTBOUND) direction. Therefore from E we only can see F. Walking in reverse direction (INBOUND), we see the path to A: B → A.

Walking in forward and reverse direction (ANY) we can see a more diverse result. First of all, we see the simple paths to F and A. However, these nodes have edges in other directions and they are traversed.

Note: The traverser may use identical edges multiple times. For instance, if it walks from E to F, it continues to walk from F to E using the same edge once again. Due to this, we see duplicate nodes in the result.

Please note that the direction can’t be passed in by a bind parameter.

Use the AQL explainer for optimizations

Now let’s have a look what the optimizer does behind the curtain and inspect traversal queries using the explainer:

FOR v,e,p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    LET localScopeVar = RAND() > 0.5
    FILTER p.edges[0].theTruth != localScopeVar
    RETURN v._key

[ 
  "G", 
  "J", 
  "K", 
  "H", 
  "I", 
  "B", 
  "D" 
]

FOR v,e,p IN 1..3 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
    FILTER p.edges[0].label == 'right_foo'
    RETURN v._key

[ 
  "G", 
  "J", 
  "K", 
  "H", 
  "I" 
]

We now see two queries: In one we add a localScopeVar variable, which is outside the scope of the traversal itself - it is not known inside of the traverser. Therefore, this filter can only be executed after the traversal, which may be undesired in large graphs. The second query on the other hand only operates on the path, and therefore this condition can be used during the execution of the traversal. Paths that are filtered out by this condition won’t be processed at all.

And finally clean it up again:

var examples = require("@arangodb/graph-examples/example-graph");
examples.dropGraph("traversalGraph");

Empty Output

If this traversal is not powerful enough for your needs, like you cannot describe your conditions as AQL filter statements, then you might want to have a look at the edge collection methods in the JavaScript API.

Also see how to combine graph traversals.