2.12. CALL Clause¶

The CALL clause executes procedures from a catalog of available procedures. Procedures optionally take arguments as inputs and either produce resulting arguments or modify the system through side effects. Procedures that have output arguments produce rows of results where the output arguments define the columns of the rows. The YIELD sub-clause defines which output parameters of the procedure are included in the result and their order. The syntax for the CALL clause is

CALL procedure_name([input_param][, input_param...])
YIELD output_param [, output_param...]

The YIELD sub-clause is usually required. The CALL clause must also usually be followed by a RETURN or WITH statement. Here are a couple of examples of valid CALL usage.

CALL procedure_name(input_param1, input_param2)
YIELD output_param1
RETURN output_param1

CALL procedure_name(input_param1)
YIELD output_param1, output_param2
WITH output_param1, output_param2
WHERE output_param1 > 7
RETURN output_param1, output_param2

The one exception to requiring YIELD and RETURN or WITH clauses is a stand-alone CALL clause. In this case, the RETURN clause or both the YIELD and RETURN clauses may be omitted, and all the outputs of the procedure are returned in the default order. Examples are

CALL procedure_name(input_param1, input_param2)

CALL procedure_name(input_param1, input_param2)
YIELD output_param1

A CALL can also be followed by a WHERE clause to filter the results.

CALL procedure_name(input_param1)
YIELD output_param1, output_param2
WHERE output_param1 > 7
RETURN output_param1, output_param2

A CALL clause can follow a WITH statement. This is useful because it allows preceding statements to generate inputs for a CALL statement.

MATCH (v:VertexFrame)
WHERE v.prop1 = 50
WITH v.prop2 AS input_param1
CALL procedure_name(input_param1)
YIELD output_param1, output_param2
RETURN output_param1, output_param2

Note that when a CALL statement follows a WITH clause that the CALL is executed for each row generated by the WITH.

2.12.1. Whole Graph Algorithms¶

xGT supports the following whole graph algorithms:

Breadth First Search (BFS)
PageRank
Strongly Connected Components (SCC)
Weakly Connected Components (WCC)

One common concept used in the graph algorithms is the graph on which an algorithm operates. In xGT a graph is a collection of vertex frames and edge frames that are connected. A vertex frame without any attached edge frames would just be a bunch of isolated vertices so can’t be in a graph. An edge frame can’t be in a graph if one of its source or target vertex frames is not included. Graphs are defined by a list of edge frames. The source and target vertex frames of each of the edge frames are included in the graph. The frames in the graph will often be all connected, but it is possible to have multiple separate components.

All graph algorithms take two parameters. The first describes the graph on which the algorithm operates, and the second is a map giving any additional parameters to the algorithm. Here is an example call for page_rank():

CALL page_rank("graph_namespace",
               { tolerance : .0001 })
YIELD vertex, rank
RETURN vertex, rank
INTO Results

The first parameter can be either a string literal representing a namespace or a list of string literals representing a list of edge frames. When a namespace name is given, all the edge frames the user has access to in the namespace along with their source and target vertex frames the user has access to in the namespace are used to define the graph. If one of the source or target vertex frames of an edge frame is not in the given namespace or the user doesn’t have access to the source or target vertex frame, that edge frame is not included. The example above shows calling a whole graph algorithm giving a namespace to define the graph.

When a list of edge frames is given, those frames along with their source and target vertex frames are used to define a graph. If a user gives an edge frame they don’t have access to or if the user doesn’t have access to one of the source or target vertex frames, a security error is thrown. Passing an empty list of edge frames causes all edge frames the user has access to in all namespaces in the system along with their source and target vertex frames to be used to define the graph. As before if the user doesn’t have access to the source or target vertex frame of one of the edge frames, that edge frame is not included. This example shows calling a whole graph algorithm giving a list of edge frames to define the graph.

CALL breadth_first_search(["Graph__Edge1", "Graph__Edge2"],
                          { sources   : [id(Graph__Vertex1, "key1")],
                            max_depth : 2 })
YIELD vertex, parent, edge, depth
RETURN vertex, parent, edge, depth
INTO Results

2.12.1.1. Vertex and Edge Representation¶

Whole graph algorithms use vertices and edges as both input and output parameters. As inputs, vertices and edges can be bound variables or row IDs. The above example shows giving the source of a BFS using the id() function to construct a vertex row ID from a frame and vertex key. See Type Construction Functions for a detailed description of using the id() function.

The following example shows generating a bound variable in a preceding MATCH that is used as the source of a BFS. This example uses the same source vertex as the previous one.

MATCH (v:Graph__Vertex1)
WHERE v.key = "key1"
WITH v AS source
CALL breadth_first_search(["Graph__Edge1", "Graph__Edge2"],
                          { sources   : [source],
                            max_depth : 2 })
YIELD vertex, parent, edge, depth
RETURN vertex, parent, edge, depth
INTO Results

Since the BFS is run for each row generated by the MATCH, the user must take care to give WHERE conditions that generate a single row if they only want to run a single BFS.

Another example uses a preceding MATCH with a collect() to generate a list of vertices used as the sources for a BFS.

MATCH (v:Graph__Vertex1)
WHERE v.prop > 100
WITH collect(v) AS sources
CALL breadth_first_search(["Graph__Edge1", "Graph__Edge2"],
                          { sources   : sources,
                            max_depth : 2 })
YIELD vertex, parent, edge, depth
RETURN vertex, parent, edge, depth
INTO Results

Vertices and edges are also output parameters of whole graph algorithms. These outputs are bound variables just like the variables generated by a MATCH clause and can be used in the same ways. For example, this query returns properties from the vertex and edge outputs of a BFS:

CALL breadth_first_search(["Graph__Edge1"],
                          { sources : [id(Graph__Vertex1, "key1")] })
YIELD vertex AS v1, parent AS v2, edge
RETURN v1.key, v1.prop, v2.key, v2.prop, edge.prop1, edge.prop2
INTO Results

The vertex and edge output parameters can come from any vertex or edge frame in the search graph. When there are multiple frames, some rules apply for property access. See Property Extraction from Multiple Candidate Frames for details.

2.12.1.2. Breadth First Search¶

The algorithm breadth_first_search() performs a breadth first search on a graph. This algorithm starts from one or more source vertices and visits all the vertices reachable from the source vertices by traversing incident edges, expanding out a level of neighbors at a time. The algorithm supports the following input parameters given in the map:

BFS Input Parameters¶
Name	Type	Default	Description
sources	List of row IDs or bound variables	N/A	A list of source vertices.
max_depth	Integer	No limit	The depth at which to stop the search.
direction	String	forward	The direction to perform the search. Valid values are “forward”, “reverse”, or “undirected”.
all_edges	Boolean	false	False returns only edges in the BFS tree. True returns all edges traversed by the search.

The “sources” parameter is required. All other parameters are optional. The “sources” parameter indicates the vertices from which the search starts. It is a list containing bound variables or row IDs.

The “max_depth” parameter indicates the depth at which to stop the search. A depth of 1 indicates one level out from the sources. The default behavior is to continue searching until no new vertices are discovered.

The “direction” parameter indicates the direction the search traverses incident edges. The default is the “forward” direction which traverses outgoing edges of vertices. The “reverse” direction traverses incoming edges of vertices. The “undirected” direction traverses both outgoing and incoming edges of vertices essentially treating the graph as if it were undirected. For a forward search, the parent is always the source of the edge. For a reverse search, the parent is always the target of the edge. For an undirected search, the parent could be either the source or target of the edge.

The “all_edges” parameter determines which edges traversed by the search are included in the results. The default value of “false” returns only the edges in the BFS tree. These are the edges where the child vertex is newly discovered by the search. This behavior returns a row for each unique vertex discovered by the search. A value of “true” returns all the edges traversed by the search. This behavior returns a row for each unique edge visited by the search. Child vertices are not unique with this behavior.

For all combinations of options, the search traverses edges only once. Thus, edge uniqueness is guaranteed in the results. For an all_edges search, the same pair of vertex and parent could appear multiple times in a search as multiple edges can exist between any two vertices. However, the edge output parameter will always be unique.

Breadth first search has the following output parameters:

BFS Output Parameters¶
Name	Type	Description
vertex	Bound vertex variable	A vertex found by the search.
parent	Bound vertex variable	The parent of a vertex found by the search.
edge	Bound edge variable	The edge connecting the parent to the child vertex.
depth	Integer	Depth at which the vertex was found.
direction	String	Direction the search traversed the edge. Either “forward” or “reverse”.

The breadth first search algorithm outputs the vertices it finds along with the parent vertex, the edge connecting the parent to the child vertex, the depth the vertex was found at, and the direction the edge between the child and parent vertices was traversed.

When the direction output is “forward” that means the search traversed an edge with the parent as the source and the child as the target. When the direction output is “reverse” that means the search traversed an edge with the child as the source and the parent as the target. For a search in the “forward” direction, the direction output is always “forward”. For a search in the “reverse” direction, the direction output is always “reverse”. The direction output is more useful when the search is in the “undirected” direction as the search can traverse edges in both directions.

2.12.1.3. PageRank¶

The algorithm page_rank() assigns a score to each vertex in the graph based on the number of incoming edges to the vertex and the scores of the sources of those edges. This is the well-known PageRank algorithm developed by Larry Page. The algorithm supports the following optional input parameters given in the map:

PageRank Input Parameters¶
Name	Type	Default	Description
damping_factor	Float	0.85	The damping factor used by PageRank.
max_iterations	Integer	20	The maximum number of iterations before stopping the algorithm.
tolerance	Float	0.0001	The algorithm stops after the norm of the difference between the score vectors of successive iterations is less than this value.
norm	String	infinity	The norm used to decide when to stop the algorithm. Valid values are “L1”, “L2”, and “infinity”.
sources	List of row IDs or bound variables	Empty list	Personalization vertices to run personalized PageRank.

The “damping_factor” parameter is the standard PageRank damping factor that balances between visiting an adjacent vertex or teleporting to a random vertex. PageRank is an iterative algorithm. When the iteration stops is determined by a combination of the “max_iterations”, “tolerance”, and “norm” parameters. The iteration stops when either the maximum number of iterations has been reached or the norm of the difference between the score vectors of successive iterations is less than the tolerance. Each iteration generates a score vector that contains a score for each vertex in the graph. Taking the norm of the difference between successive score vectors gives a value to how much the last iteration improved the scores, and the algorithm stops if this value is less than a tolerance. The standard “L1”, “L2”, and “infinity” norms are supported. The “sources” parameter is used to perform personalized PageRank which restricts the vertices visited by a teleportation to the set of vertices given.

PageRank has the following output parameters:

PageRank Output Parameters¶
Name	Type	Description
vertex	Bound vertex variable	Vertex from the graph.
rank	Float	PageRank of a vertex.

The PageRank algorithm outputs all the vertices in the graph along with the PageRank score for each vertex.

2.12.1.4. Strongly Connected Components¶

The algorithm strongly_connected_components() finds the strongly connected components of a directed graph. A strong component is a subset of the vertices of a graph that are all reachable from each other both by traversing only forward edges and by traversing only reverse edges. The algorithm has no input parameters beyond the graph.

Strongly connected components has the following output parameters:

Strongly Connected Components Output Parameters¶
Name	Type	Description
vertex	Bound vertex variable	Vertex from the graph.
component	Integer	Integer representing the component.

The strongly connected components algorithm outputs all the vertices in the graph along with an integer representing the component each vertex belongs to. Each component has a unique integer, and the integers are not necessarily contiguous.

2.12.1.5. Weakly Connected Components¶

The algorithm weakly_connected_components() finds the weakly connected components of a directed graph. A weak component is a subset of the vertices of a graph that are all reachable from each other by traversing edges, ignoring direction. The algorithm has no input parameters beyond the graph.

Weakly connected components has the following output parameters:

Weakly Connected Components Output Parameters¶
Name	Type	Description
vertex	Bound vertex variable	Vertex from the graph.
component	Integer	Integer representing the component.

The weakly connected components algorithm outputs all the vertices in the graph along with an integer representing the component each vertex belongs to. Each component has a unique integer, and the integers are not necessarily contiguous.