ArangoDB Logo

ArangoDB v3.13 is under development and not released yet. This documentation is not final and potentially incomplete.

k Paths in AQL

Find all paths between two nodes with a fixed range of path lengths

General query idea

This type of query finds all paths between two given documents (startNode and endNode) in your graph. The paths are restricted by a minimum and maximum length that you specify.

Every such path is returned as a JSON object with two components:

  • an array containing the vertices on the path
  • an array containing the edges on the path

Example

Here is an example graph to explain how the k Paths algorithm works:

Train Connection Map

Each ellipse stands for a train station with the name of the city written inside of it. They are the nodes of the graph. Arrows represent train connections between cities and are the edges of the graph. The numbers near the arrows describe how long it takes to get from one station to another. They are used as edge weights.

Assume that you want to go from Aberdeen to London by train.

You have a couple of alternatives:

a) Straight way

  1. Aberdeen
  2. Leuchars
  3. Edinburgh
  4. York
  5. London

b) Detour at York

  1. Aberdeen
  2. Leuchars
  3. Edinburgh
  4. York
  5. Carlisle
  6. Birmingham
  7. London

c) Detour at Edinburgh

  1. Aberdeen
  2. Leuchars
  3. Edinburgh
  4. Glasgow
  5. Carlisle
  6. Birmingham
  7. London

d) Detour at Edinburgh to York

  1. Aberdeen
  2. Leuchars
  3. Edinburgh
  4. Glasgow
  5. Carlisle
  6. York
  7. London

Note that only paths that do not contain the same node twice are consider to be valid. The following alternative would visit Aberdeen twice and is not returned by the k Paths algorithm:

  1. Aberdeen
  2. Inverness
  3. Aberdeen
  4. Leuchars
  5. Edinburgh
  6. York
  7. London

Example Use Cases

The use-cases for k Paths are about the same as for unweighted k Shortest Paths. The main difference is that k Shortest Paths enumerates all paths with increasing length. It stops as soon as a given number of paths is reached. k Paths enumerates all paths within a given range of path lengths instead, and is thereby upper-bounded.

The k Paths traversal can be used as foundation for several other algorithms:

  • Transportation of any kind (e.g. road traffic, network package routing)
  • Flow problems: You need to transfer items from A to B, which alternatives do you have? What is their capacity?

Syntax

The syntax for k Paths queries is similar to the one for K Shortest Path with the addition to define the minimum and maximum length of the path.

It is highly recommended that you use a reasonable maximum path length or a LIMIT statement, as k Paths is a potentially expensive operation. It can return a large number of paths for large connected graphs.

Working with named graphs 

FOR path
  IN MIN..MAX OUTBOUND|INBOUND|ANY K_PATHS
  startNode TO endNode
  GRAPH graphName
  [OPTIONS options]
  • FOR: Emits the variable path which contains one path as an object containing vertices (nodes) and edges of the path.
  • IN MIN..MAX: The minimal and maximal depth for the traversal:
    • min (number, optional): Paths returned by this query have at least a length of this many edges. If not specified, it defaults to 1. The minimal possible value is 0.
    • max (number, optional): Paths returned by this query have at most a length of this many edges. If omitted, it defaults to the value of min. Thus, only the nodes and edges in the range of min are returned. You cannot specify max without min.
  • OUTBOUND|INBOUND|ANY: Defines in which direction edges are followed (outgoing, incoming, or both).
  • K_PATHS: The keyword to compute all paths with the specified lengths.
  • startNode TO endNode (both string|object): The two nodes between which the paths are computed. This can be specified in the form of a document identifier string or in the form of an object with the _id attribute. All other values lead to a warning and an empty result. This is also the case if one of the specified documents does not exist.
  • GRAPH graphName (string): The name identifying the named graph. Its node and edge collections are looked up for the path search.
  • OPTIONS options (object, optional): See the path search options.

Working with collection sets 

FOR path
  IN MIN..MAX OUTBOUND|INBOUND|ANY K_PATHS
  startNode TO endNode
  edgeCollection1, ..., edgeCollectionN
  [OPTIONS options]

Instead of GRAPH graphName you can specify a list of edge collections. The involved node collections are determined by the edges of the given edge collections.

Path search options

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

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 k paths 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 search direction and ANY specifically for edges2 as follows:

FOR node IN OUTBOUND K_PATHS
  startNode TO endNode
  edges1, ANY edges2, edges3

All collections in the list that do not specify their own direction use the direction defined after IN (here: OUTBOUND). This allows to use a different direction for each collection in your path search.

Graph path searches 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 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 path searches 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 path search query that starts (and ends) 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 p IN 4 ANY K_PATHS "person/1544" TO "person/52560" acts_in
  LIMIT 2
  RETURN p.vertices[*].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 p IN 4 ANY K_PATHS "person/1544" TO "person/52560" acts_in
  LIMIT 2
  RETURN p.vertices[*].label

// Chris Rock --> Dogma <-- Ben Affleck --> Surviving Christmas <-- Jennifer Morrison
// Chris Rock --> The Longest Yard <-- Rob Schneider --> Big Stan <-- Jennifer Morrison

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

Examples

You can load the kShortestPathsGraph example graph to get a named graph that reflects some possible train connections in Europe and North America.

Train Connection Map

var examples = require("@arangodb/graph-examples/example-graph");
var graph = examples.loadGraph("kShortestPathsGraph");
db.places.toArray();
db.connections.toArray();
Show output
[ 
  { 
    "_key" : "Inverness", 
    "_id" : "places/Inverness", 
    "_rev" : "_hg5kISW---", 
    "label" : "Inverness" 
  }, 
  { 
    "_key" : "Aberdeen", 
    "_id" : "places/Aberdeen", 
    "_rev" : "_hg5kISW--_", 
    "label" : "Aberdeen" 
  }, 
  { 
    "_key" : "Leuchars", 
    "_id" : "places/Leuchars", 
    "_rev" : "_hg5kISa---", 
    "label" : "Leuchars" 
  }, 
  { 
    "_key" : "StAndrews", 
    "_id" : "places/StAndrews", 
    "_rev" : "_hg5kISe---", 
    "label" : "StAndrews" 
  }, 
  { 
    "_key" : "Edinburgh", 
    "_id" : "places/Edinburgh", 
    "_rev" : "_hg5kISe--_", 
    "label" : "Edinburgh" 
  }, 
  { 
    "_key" : "Glasgow", 
    "_id" : "places/Glasgow", 
    "_rev" : "_hg5kISi---", 
    "label" : "Glasgow" 
  }, 
  { 
    "_key" : "York", 
    "_id" : "places/York", 
    "_rev" : "_hg5kISi--_", 
    "label" : "York" 
  }, 
  { 
    "_key" : "Carlisle", 
    "_id" : "places/Carlisle", 
    "_rev" : "_hg5kISi--A", 
    "label" : "Carlisle" 
  }, 
  { 
    "_key" : "Birmingham", 
    "_id" : "places/Birmingham", 
    "_rev" : "_hg5kISi--B", 
    "label" : "Birmingham" 
  }, 
  { 
    "_key" : "London", 
    "_id" : "places/London", 
    "_rev" : "_hg5kISm---", 
    "label" : "London" 
  }, 
  { 
    "_key" : "Brussels", 
    "_id" : "places/Brussels", 
    "_rev" : "_hg5kISm--_", 
    "label" : "Brussels" 
  }, 
  { 
    "_key" : "Cologne", 
    "_id" : "places/Cologne", 
    "_rev" : "_hg5kISm--A", 
    "label" : "Cologne" 
  }, 
  { 
    "_key" : "Toronto", 
    "_id" : "places/Toronto", 
    "_rev" : "_hg5kISm--B", 
    "label" : "Toronto" 
  }, 
  { 
    "_key" : "Winnipeg", 
    "_id" : "places/Winnipeg", 
    "_rev" : "_hg5kISm--C", 
    "label" : "Winnipeg" 
  }, 
  { 
    "_key" : "Saskatoon", 
    "_id" : "places/Saskatoon", 
    "_rev" : "_hg5kISm--D", 
    "label" : "Saskatoon" 
  }, 
  { 
    "_key" : "Edmonton", 
    "_id" : "places/Edmonton", 
    "_rev" : "_hg5kISq---", 
    "label" : "Edmonton" 
  }, 
  { 
    "_key" : "Jasper", 
    "_id" : "places/Jasper", 
    "_rev" : "_hg5kISq--_", 
    "label" : "Jasper" 
  }, 
  { 
    "_key" : "Vancouver", 
    "_id" : "places/Vancouver", 
    "_rev" : "_hg5kISq--A", 
    "label" : "Vancouver" 
  } 
]

[ 
  { 
    "_key" : "62300", 
    "_id" : "connections/62300", 
    "_from" : "places/Inverness", 
    "_to" : "places/Aberdeen", 
    "_rev" : "_hg5kISq--B", 
    "travelTime" : 3 
  }, 
  { 
    "_key" : "62302", 
    "_id" : "connections/62302", 
    "_from" : "places/Aberdeen", 
    "_to" : "places/Inverness", 
    "_rev" : "_hg5kISq--C", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "62304", 
    "_id" : "connections/62304", 
    "_from" : "places/Aberdeen", 
    "_to" : "places/Leuchars", 
    "_rev" : "_hg5kISq--D", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "62306", 
    "_id" : "connections/62306", 
    "_from" : "places/Leuchars", 
    "_to" : "places/Aberdeen", 
    "_rev" : "_hg5kISu---", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62308", 
    "_id" : "connections/62308", 
    "_from" : "places/Leuchars", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_hg5kISu--_", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "62310", 
    "_id" : "connections/62310", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/Leuchars", 
    "_rev" : "_hg5kISu--A", 
    "travelTime" : 3 
  }, 
  { 
    "_key" : "62312", 
    "_id" : "connections/62312", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/Glasgow", 
    "_rev" : "_hg5kISu--B", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62314", 
    "_id" : "connections/62314", 
    "_from" : "places/Glasgow", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_hg5kISu--C", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62316", 
    "_id" : "connections/62316", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/York", 
    "_rev" : "_hg5kISu--D", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "62318", 
    "_id" : "connections/62318", 
    "_from" : "places/York", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_hg5kISu--E", 
    "travelTime" : 4 
  }, 
  { 
    "_key" : "62320", 
    "_id" : "connections/62320", 
    "_from" : "places/Glasgow", 
    "_to" : "places/Carlisle", 
    "_rev" : "_hg5kISy---", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62322", 
    "_id" : "connections/62322", 
    "_from" : "places/Carlisle", 
    "_to" : "places/Glasgow", 
    "_rev" : "_hg5kISy--_", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62324", 
    "_id" : "connections/62324", 
    "_from" : "places/Carlisle", 
    "_to" : "places/York", 
    "_rev" : "_hg5kISy--A", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "62326", 
    "_id" : "connections/62326", 
    "_from" : "places/York", 
    "_to" : "places/Carlisle", 
    "_rev" : "_hg5kISy--B", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "62328", 
    "_id" : "connections/62328", 
    "_from" : "places/Carlisle", 
    "_to" : "places/Birmingham", 
    "_rev" : "_hg5kISy--C", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "62330", 
    "_id" : "connections/62330", 
    "_from" : "places/Birmingham", 
    "_to" : "places/Carlisle", 
    "_rev" : "_hg5kISy--D", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "62332", 
    "_id" : "connections/62332", 
    "_from" : "places/Birmingham", 
    "_to" : "places/London", 
    "_rev" : "_hg5kISy--E", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "62334", 
    "_id" : "connections/62334", 
    "_from" : "places/London", 
    "_to" : "places/Birmingham", 
    "_rev" : "_hg5kISy--F", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "62336", 
    "_id" : "connections/62336", 
    "_from" : "places/Leuchars", 
    "_to" : "places/StAndrews", 
    "_rev" : "_hg5kIS2---", 
    "travelTime" : 0.2 
  }, 
  { 
    "_key" : "62338", 
    "_id" : "connections/62338", 
    "_from" : "places/StAndrews", 
    "_to" : "places/Leuchars", 
    "_rev" : "_hg5kIS2--_", 
    "travelTime" : 0.2 
  }, 
  { 
    "_key" : "62340", 
    "_id" : "connections/62340", 
    "_from" : "places/York", 
    "_to" : "places/London", 
    "_rev" : "_hg5kIS2--A", 
    "travelTime" : 1.8 
  }, 
  { 
    "_key" : "62342", 
    "_id" : "connections/62342", 
    "_from" : "places/London", 
    "_to" : "places/York", 
    "_rev" : "_hg5kIS2--B", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "62344", 
    "_id" : "connections/62344", 
    "_from" : "places/London", 
    "_to" : "places/Brussels", 
    "_rev" : "_hg5kIS2--C", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "62346", 
    "_id" : "connections/62346", 
    "_from" : "places/Brussels", 
    "_to" : "places/London", 
    "_rev" : "_hg5kIS6---", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "62348", 
    "_id" : "connections/62348", 
    "_from" : "places/Brussels", 
    "_to" : "places/Cologne", 
    "_rev" : "_hg5kIS6--_", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "62350", 
    "_id" : "connections/62350", 
    "_from" : "places/Cologne", 
    "_to" : "places/Brussels", 
    "_rev" : "_hg5kIS6--A", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "62352", 
    "_id" : "connections/62352", 
    "_from" : "places/Toronto", 
    "_to" : "places/Winnipeg", 
    "_rev" : "_hg5kIS6--B", 
    "travelTime" : 36 
  }, 
  { 
    "_key" : "62354", 
    "_id" : "connections/62354", 
    "_from" : "places/Winnipeg", 
    "_to" : "places/Toronto", 
    "_rev" : "_hg5kIS6--C", 
    "travelTime" : 35 
  }, 
  { 
    "_key" : "62356", 
    "_id" : "connections/62356", 
    "_from" : "places/Winnipeg", 
    "_to" : "places/Saskatoon", 
    "_rev" : "_hg5kIS6--D", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "62358", 
    "_id" : "connections/62358", 
    "_from" : "places/Saskatoon", 
    "_to" : "places/Winnipeg", 
    "_rev" : "_hg5kIS6--E", 
    "travelTime" : 5 
  }, 
  { 
    "_key" : "62360", 
    "_id" : "connections/62360", 
    "_from" : "places/Saskatoon", 
    "_to" : "places/Edmonton", 
    "_rev" : "_hg5kIT----", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "62362", 
    "_id" : "connections/62362", 
    "_from" : "places/Edmonton", 
    "_to" : "places/Saskatoon", 
    "_rev" : "_hg5kIT---_", 
    "travelTime" : 17 
  }, 
  { 
    "_key" : "62364", 
    "_id" : "connections/62364", 
    "_from" : "places/Edmonton", 
    "_to" : "places/Jasper", 
    "_rev" : "_hg5kIT---A", 
    "travelTime" : 6 
  }, 
  { 
    "_key" : "62366", 
    "_id" : "connections/62366", 
    "_from" : "places/Jasper", 
    "_to" : "places/Edmonton", 
    "_rev" : "_hg5kIT---B", 
    "travelTime" : 5 
  }, 
  { 
    "_key" : "62368", 
    "_id" : "connections/62368", 
    "_from" : "places/Jasper", 
    "_to" : "places/Vancouver", 
    "_rev" : "_hg5kIT---C", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "62370", 
    "_id" : "connections/62370", 
    "_from" : "places/Vancouver", 
    "_to" : "places/Jasper", 
    "_rev" : "_hg5kIT---D", 
    "travelTime" : 13 
  } 
]

Suppose you want to query all routes from Aberdeen to London.

FOR p IN 1..10 OUTBOUND K_PATHS 'places/Aberdeen' TO 'places/London'
GRAPH 'kShortestPathsGraph'
    RETURN { places: p.vertices[*].label, travelTimes: p.edges[*].travelTime }
Show output
[ 
  { 
    "places" : [ 
      "Aberdeen", 
      "Leuchars", 
      "Edinburgh", 
      "York", 
      "London" 
    ], 
    "travelTimes" : [ 
      1.5, 
      1.5, 
      3.5, 
      1.8 
    ] 
  }, 
  { 
    "places" : [ 
      "Aberdeen", 
      "Leuchars", 
      "Edinburgh", 
      "Glasgow", 
      "Carlisle", 
      "Birmingham", 
      "London" 
    ], 
    "travelTimes" : [ 
      1.5, 
      1.5, 
      1, 
      1, 
      2, 
      1.5 
    ] 
  }, 
  { 
    "places" : [ 
      "Aberdeen", 
      "Leuchars", 
      "Edinburgh", 
      "Glasgow", 
      "Carlisle", 
      "York", 
      "London" 
    ], 
    "travelTimes" : [ 
      1.5, 
      1.5, 
      1, 
      1, 
      2.5, 
      1.8 
    ] 
  }, 
  { 
    "places" : [ 
      "Aberdeen", 
      "Leuchars", 
      "Edinburgh", 
      "York", 
      "Carlisle", 
      "Birmingham", 
      "London" 
    ], 
    "travelTimes" : [ 
      1.5, 
      1.5, 
      3.5, 
      3.5, 
      2, 
      1.5 
    ] 
  } 
]

If you ask for routes that don’t exist, you get an empty result (from Aberdeen to Toronto):

FOR p IN 1..10 OUTBOUND K_PATHS 'places/Aberdeen' TO 'places/Toronto'
GRAPH 'kShortestPathsGraph'
    RETURN { places: p.vertices[*].label, travelTimes: p.edges[*].travelTime }
Show output
[ ]

And finally clean up by removing the named graph:

var examples = require("@arangodb/graph-examples/example-graph");
examples.dropGraph("kShortestPathsGraph");
Show output
Empty Output

On this page