allpaths

Find all paths between two graph nodes

Since R2021a

Syntax

paths = allpaths(G,s,t)

[paths,edgepaths] = allpaths(G,s,t)

[___] = allpaths(G,s,t,Name,Value)

Description

paths = allpaths(G,s,t) returns all paths in graph G that start at source node s and end at target node t. The output paths is a cell array where the contents of each cell paths{k} lists nodes that lie on a path.

[paths,edgepaths] = allpaths(G,s,t) also returns the edges on each path from s to t. The output edgepaths is a cell array where edgepaths{k} gives the edges along the corresponding path, paths{k}.

[___] = allpaths(G,s,t,Name,Value) specifies additional options using one or more name-value arguments. You can use any of the output argument combinations in previous syntaxes. For example, you can specify MaxNumPaths and a scalar to limit the number of paths returned.

Examples

All Paths in Undirected Graph

Create an adjacency matrix for a complete graph with four nodes, and then create an undirected graph from the adjacency matrix. Plot the graph.

A = ones(4);
G = graph(A);
plot(G)

Calculate all paths in the graph that begin at node 1 and end at node 3.

paths = allpaths(G,1,3)

paths=5×1 cell array
    {[  1 2 3]}
    {[1 2 4 3]}
    {[    1 3]}
    {[1 4 2 3]}
    {[  1 4 3]}

Edges Along Paths

The second output argument of allpaths returns the edges that are along each path. This is particularly useful for multigraphs, where the edge index is required to uniquely identify the edges on the path.

Create a directed multigraph with eight nodes and 18 edges. Specify names for the nodes. Plot the graph with labeled nodes and edges.

s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];
t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];
names = {'A','B','C','D','E','F','G','H'};
G = digraph(s,t,[],names);
p = plot(G,'EdgeLabel',1:numedges(G));

Calculate all paths between node A and node H. Specify two output arguments to also return the edge indices for edges along each path.

[paths,edgepaths] = allpaths(G,'A','H');

View the nodes and edges along the first path.

paths{1}

ans = 1×6 cell
    {'A'}    {'B'}    {'C'}    {'E'}    {'G'}    {'H'}

edgepaths{1}

ans = 1×5

     1     4     9    13    17

Highlight the nodes and edges along the first path.

highlight(p,'Edges',edgepaths{1},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)

Limit Number of Paths Returned

Use the 'MaxNumPaths', 'MaxPathLength', and 'MinPathLength' options to limit the number of paths returned by allpaths.

Create an adjacency matrix for a complete graph with 20 nodes. Create an undirected graph from the adjacency matrix, omitting self-loops.

A = ones(20);
G = graph(A,'omitselfloops');

Since all of the nodes in the graph are connected to all other nodes, there are a large number of paths in the graph between any two nodes (more than 1.7e16). Therefore, it is not feasible to calculate all of the paths between two nodes since the results will not fit in memory. Instead, calculate the first 10 paths from node 2 to node 5.

paths1 = allpaths(G,2,5,'MaxNumPaths',10)

paths1=10×1 cell array
    {[                       2 1 3 4 5]}
    {[                     2 1 3 4 6 5]}
    {[                   2 1 3 4 6 7 5]}
    {[                 2 1 3 4 6 7 8 5]}
    {[               2 1 3 4 6 7 8 9 5]}
    {[            2 1 3 4 6 7 8 9 10 5]}
    {[         2 1 3 4 6 7 8 9 10 11 5]}
    {[      2 1 3 4 6 7 8 9 10 11 12 5]}
    {[   2 1 3 4 6 7 8 9 10 11 12 13 5]}
    {[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

Now calculate the first 10 paths between node 2 and node 5 that have a path length less than or equal to 2.

paths2 = allpaths(G,2,5,'MaxNumPaths',10,'MaxPathLength',2)

paths2=10×1 cell array
    {[ 2 1 5]}
    {[ 2 3 5]}
    {[ 2 4 5]}
    {[   2 5]}
    {[ 2 6 5]}
    {[ 2 7 5]}
    {[ 2 8 5]}
    {[ 2 9 5]}
    {[2 10 5]}
    {[2 11 5]}

Finally, calculate the first 10 paths between node 2 and node 5 that have a path length greater than or equal to 3.

paths3 = allpaths(G,2,5,'MaxNumPaths',10,'MinPathLength',3)

paths3=10×1 cell array
    {[                       2 1 3 4 5]}
    {[                     2 1 3 4 6 5]}
    {[                   2 1 3 4 6 7 5]}
    {[                 2 1 3 4 6 7 8 5]}
    {[               2 1 3 4 6 7 8 9 5]}
    {[            2 1 3 4 6 7 8 9 10 5]}
    {[         2 1 3 4 6 7 8 9 10 11 5]}
    {[      2 1 3 4 6 7 8 9 10 11 12 5]}
    {[   2 1 3 4 6 7 8 9 10 11 12 13 5]}
    {[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

Input Arguments

G — Input graph

graph object | digraph object

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

s, t — Source and target node IDs (as separate arguments)

node indices | node names

Source and target node IDs, specified as separate arguments of node indices or node names.

Value	Example
Scalar node index	1
Character vector node name	'A'
String scalar node name	"A"

Example: allpaths(G,2,5) computes all paths between node 2 and node 5.

Example: allpaths(G,'node1','node2') computes all paths between the named nodes node1 and node2.

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose Name in quotes.

Example: allpaths(G,s,t,'MaxNumPaths',100) returns only the first 100 results in the lexicographic ordering of paths.

MaxNumPaths — Maximum number of paths

nonnegative integer scalar

Maximum number of paths, specified as the comma-separated pair consisting of 'MaxNumPaths' and a nonnegative integer scalar. This option is useful when the number of paths between two nodes grows large enough to hit memory limits. You can specify MaxNumPaths to limit the number of paths returned by allpaths so that the results fit within available memory.

Example: allpaths(G,s,t,'MaxNumPaths',100)

MaxPathLength — Maximum path length

nonnegative integer scalar

Maximum path length, specified as the comma-separated pair consisting of 'MaxPathLength' and a nonnegative integer scalar. This option filters the results returned by allpaths so that no paths with length larger than the specified limit are returned. The length of a path is measured by the number of edges in it, ignoring edge weights.

To find paths with a range of lengths, specify both 'MaxPathLength' and 'MinPathLength'. To find paths with an exact specified length, specify the same value for both 'MaxPathLength' and 'MinPathLength'.

Example: allpaths(G,s,t,'MaxPathLength',4) returns paths that have a length less than or equal to 4.

Example: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) returns paths that have a length of 3, 4, or 5.

MinPathLength — Minimum path length

nonnegative integer scalar

Minimum path length, specified as the comma-separated pair consisting of 'MinPathLength' and a nonnegative integer scalar. This option filters the results returned by allpaths so that no paths with length smaller than the specified limit are returned. The length of a path is measured by the number of edges in it, ignoring edge weights.

To find paths with a range of lengths, specify both 'MaxPathLength' and 'MinPathLength'. To find paths with an exact specified length, specify the same value for both 'MaxPathLength' and 'MinPathLength'.

Example: allpaths(G,s,t,'MinPathLength',2) returns paths that have a length greater than or equal to 2.

Example: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) returns paths that have a length of 3, 4, or 5.

Output Arguments

paths — Paths between specified nodes

cell array

Paths between specified nodes, returned as a cell array. Each element paths{k} contains the nodes that lie along one of the paths between the specified source and target nodes. The paths are returned in lexicographical order. If the source and target nodes s and t specify the same node, then by convention allpaths returns a single path containing that node. If node t is unreachable from node s, then paths is empty.

The data type of the entries in paths depends on the way s and t are specified:

• If s and t are specified as numeric node indices, then each element paths{k} is a numeric vector of node indices.

• If s and t are specified as string node names, then each element paths{k} is a string array of node names.

• If s and t are specified as character vector node names, then each element paths{k} is a cell array of character vector node names.

edgepaths — Edges along each path

cell array

Edges along each path, returned as a cell array. Each element edgepaths{k} contains the edge indices for edges that lie along the corresponding path, paths{k}. If node t is unreachable from node s, then edgepaths is empty.

More About

Graph Paths

A path in a graph is a set of graph edges that can be followed from a defined starting node to reach a defined ending node. By convention, the nodes along the path must be unique, so paths do not contain repeated nodes or edges.

Tips

• The number of paths in a graph depends heavily on the structure of the graph. For some graph structures, the number of paths can grow exponentially with the number of nodes. For example, a complete graph with 12 nodes given by G = graph(ones(12)) contains nearly 10 million paths between any two of its nodes. Use the MaxNumPaths, MaxPathLength, and MinPathLength name-value pairs to control the output of allpaths in these cases.

Version History

Introduced in R2021a