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_find_all_path(VERTEX source_v, VERTEX target_v, INT maxDepth,
  BOOL print_accum = TRUE, STRING file_path = "")

Bidirectional

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

Parameters

Parameter Data type Description

Parameter	Data type	Description
`source_v`	`VERTEX`	Source vertex where the paths start.
`target_v`	`VERTEX`	Target vertex where the paths end.
`maxDepth`	`INT`	The maximum length of the path returned.
`print_accum`	`BOOL`	If `true`, write output to the console in JSON format.
`file_path`	`SET<STRING>`	If not empty, write output to this file.

source_v

VERTEX

Source vertex where the paths start.

target_v

VERTEX

Target vertex where the paths end.

maxDepth

INT

The maximum length of the path returned.

print_accum

BOOL

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

file_path

SET<STRING>

If not empty, write output to this file.

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_find_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