All Paths (Single-Pair)

Supported Graph Characteristics

Unweighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm links: All Paths (Single-Pair)

This algorithm finds and prints all paths between two input vertices. This is similar to the all-paths functionality in the standard GraphStudio viewer, except that it supports output of all vertices in all paths to a file or to the console. If you are using GraphStudio and only want a fast visual display of all paths, use the GraphStudio implementation instead of this algorithm.

There are directional and bidirectional versions of this algorithm.

Specifications

Directional

CREATE QUERY tg_all_path(VERTEX source_v, VERTEX target_v, INT maxDepth = 10,
  BOOL print_accum = TRUE, STRING file_path = "")

Bidirectional

CREATE QUERY tg_all_path_bidirection(VERTEX source_v, VERTEX target_v, SET<STRING> e_type, INT maxDepth = 3,
  BOOL print_accum = TRUE, STRING file_path = "")

Parameters

Parameter Description Default value

Parameter	Description	Default value
`VERTEX source_v`	Source vertex where the paths start. Provide the vertex ID and type as a tuple: `("id","type")`	N/A
`VERTEX target_v`	Target vertex where the paths end. Provide the vertex ID and type as a tuple: `("id","type")`	N/A
`SET<STRING> e_type`	Used for the bidirectional version of the algorithm. A set of strings referring to the edge types to use.	(empty set of strings)
`INT maxDepth`	The maximum length of the path returned.	10
`BOOL print_accum`	If `true`, write output to the console in JSON format.	True
`STRING file_path`	If not empty, write output to this file.	(empty string)

VERTEX source_v

Source vertex where the paths start. Provide the vertex ID and type as a tuple: ("id","type")

N/A

VERTEX target_v

Target vertex where the paths end. Provide the vertex ID and type as a tuple: ("id","type")

N/A

SET<STRING> e_type

Used for the bidirectional version of the algorithm. A set of strings referring to the edge types to use.

(empty set of strings)

INT maxDepth

The maximum length of the path returned.

BOOL print_accum

If true, write output to the console in JSON format.

True

STRING file_path

If not empty, write output to this file.

(empty string)

Output

In both JSON and CSV outputs, the result is a list of vertices visited on each path.

Time complexity

\(O(1)-O(VE)\), where \(V\) is the number of vertices and \(E\) is the number of edges.

Space complexity

\(O(1)-O(V^2E)\)

Example

Suppose we have a large network of consumers, products, and the contexts in which the products are used. We want to find the contexts in which products P001 and P002 are both used.

single pair all paths

This image was generated from GraphStudio using the Find Paths option in the Explore Graph window and limiting the maximum depth, or number of vertices in the path, to 3.

The paths can also be output in JSON format to the console or CSV format to a file using the all-paths algorithm.

Query

RUN QUERY tg_all_path("P001", "P002", 3, TRUE, "/home/tigergraph/output.csv")

JSON
CSV

[
  {
    "path": [
      [
        "P001",
        "GW",
        "P002"
      ],
      [
        "P001",
        "T3",
        "P002"
      ],
      [
        "P001",
        "T4",
        "P002"
      ]
    ]
  }
]

P001,GW,P002
P001,T3,P002
P001,T4,P002