shortestpath (biograph) - Solve shortest path problem in biograph object

Syntax

[dist, path, pred] = shortestpath(BGObj, S) [dist, path, pred] = shortestpath(BGObj, S, T) [...] = shortestpath(..., 'Directed', DirectedValue, ...) [...] = shortestpath(..., 'Method', MethodValue, ...) [...] = shortestpath(..., 'Weights', WeightsValue, ...)

Arguments

`BGObj`	Biograph object created by `biograph` (object constructor).
`S`	Node in graph represented by an N-by-N adjacency matrix extracted from a biograph object, `BGObj`.
`T`	Node in graph represented by an N-by-N adjacency matrix extracted from a biograph object, `BGObj`.
`DirectedValue`	Property that indicates whether the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, is directed or undirected. Enter `false` for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is `true`.
`MethodValue`	String that specifies the algorithm used to find the shortest path. Choices are: `'Bellman-Ford'` — Assumes weights of the edges to be nonzero entries in the N-by-N adjacency matrix. Time complexity is `O(NE)`, where `N` and `E` are the number of nodes and edges respectively. `'BFS'` — Breadth-first search. Assumes all weights to be equal, and nonzero entries in the N-by-N adjacency matrix to represent edges. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively. `'Acyclic'` — Assumes the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, to be a directed acyclic graph and that weights of the edges are nonzero entries in the N-by-N adjacency matrix. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively. `'Dijkstra'` — Default algorithm. Assumes weights of the edges to be positive values in the N-by-N adjacency matrix. Time complexity is `O(log(N)E)`, where `N` and `E` are the number of nodes and edges respectively.
`WeightsValue`	Column vector that specifies custom weights for the edges in the N-by-N adjacency matrix extracted from a biograph object, `BGObj`. It must have one entry for every nonzero value (edge) in the N-by-N adjacency matrix. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N adjacency matrix when it is traversed column-wise. This property lets you use zero-valued weights. By default, `shortestpaths` gets weight information from the nonzero entries in the N-by-N adjacency matrix.

Description

Tip For introductory information on graph theory functions, see Graph Theory Functions in the Bioinformatics Toolbox User's Guide.

[dist, path, pred] = shortestpath(BGObj, S) determines the single-source shortest paths from node S to all other nodes in the graph represented by an N-by-N adjacency matrix extracted from a biograph object, BGObj. Weights of the edges are all nonzero entries in the N-by-N adjacency matrix. dist are the N distances from the source to every node (using Infs for nonreachable nodes and 0 for the source node). path contains the winning paths to every node. pred contains the predecessor nodes of the winning paths.

[dist, path, pred] = shortestpath(BGObj, S, T) determines the single source-single destination shortest path from node S to node T.

[...] = shortestpath(..., 'PropertyName', PropertyValue, ...) calls shortestpath with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each PropertyName must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

[...] = shortestpath(..., 'Directed', DirectedValue, ...) indicates whether the graph represented by the N-by-N adjacency matrix extracted from a biograph object, BGObj, is directed or undirected. Set DirectedValue to false for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is true.

[...] = shortestpath(..., 'Method', MethodValue, ...) lets you specify the algorithm used to find the shortest path. Choices are:

'Bellman-Ford' — Assumes weights of the edges to be nonzero entries in the N-by-N adjacency matrix. Time complexity is O(N*E), where N and E are the number of nodes and edges respectively.
'BFS' — Breadth-first search. Assumes all weights to be equal, and nonzero entries in the N-by-N adjacency matrix to represent edges. Time complexity is O(N+E), where N and E are the number of nodes and edges respectively.
'Acyclic' — Assumes the graph represented by the N-by-N adjacency matrix extracted from a biograph object, BGObj, to be a directed acyclic graph and that weights of the edges are nonzero entries in the N-by-N adjacency matrix. Time complexity is O(N+E), where N and E are the number of nodes and edges respectively.
'Dijkstra' — Default algorithm. Assumes weights of the edges to be positive values in the N-by-N adjacency matrix. Time complexity is O(log(N)*E), where N and E are the number of nodes and edges respectively.

[...] = shortestpath(..., 'Weights', WeightsValue, ...) lets you specify custom weights for the edges. WeightsValue is a column vector having one entry for every nonzero value (edge) in the N-by-N adjacency matrix extracted from a biograph object, BGObj. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N adjacency matrix when it is traversed column-wise. This property lets you use zero-valued weights. By default, shortestpath gets weight information from the nonzero entries in the N-by-N adjacency matrix.

References

[1] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.

[2] Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 87–90.

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

shortestpath (biograph) - Solve shortest path problem in biograph object

Syntax

Arguments

Description

References

See Also

Recommended Products