# Path¶

Standard algorithms related to graph traversal.

Most algorithms are adapted from SciPy.

## Shortest path¶

sknetwork.path.distance(adjacency: scipy.sparse.csr.csr_matrix, sources: Optional[Union[int, Iterable]] = None, method: str = 'D', return_predecessors: bool = False, unweighted: bool = False, n_jobs: Optional[int] = None)[source]

Compute distances between nodes.

• Graphs

• Digraphs

Based on SciPy (scipy.sparse.csgraph.shortest_path)

Parameters

• sources – If specified, only compute the paths for the points at the given indices. Will not work with method =='FW'.

• method

The method to be used.

• 'D' (Dijkstra),

• 'BF' (Bellman-Ford),

• 'J' (Johnson).

• return_predecessors – If True, the size predecessor matrix is returned

• unweighted – If True, the weights of the edges are ignored

• n_jobs – If an integer value is given, denotes the number of workers to use (-1 means the maximum number will be used). If None, no parallel computations are made.

Returns

• dist_matrix (np.ndarray) – The matrix of distances between graph nodes. dist_matrix[i,j] gives the shortest distance from point i to point j along the graph. If no path exists between nodes i and j, then dist_matrix[i, j] = np.inf.

• predecessors (np.ndarray, optional) – Returned only if return_predecessors == True. The matrix of predecessors, which can be used to reconstruct the shortest paths. Row i of the predecessor matrix contains information on the shortest paths from point i: each entry predecessors[i, j] gives the index of the previous node in the path from point i to point j. If no path exists between nodes i and j, then predecessors[i, j] = -9999.

Examples

>>> from sknetwork.data import cyclic_digraph
array([0., 1., 2.])
(array([0., 1., 2.]), array([-9999,     0,     1]))

sknetwork.path.shortest_path(adjacency: scipy.sparse.csr.csr_matrix, sources: Union[int, Iterable], targets: Union[int, Iterable], method: str = 'D', unweighted: bool = False, n_jobs: Optional[int] = None)[source]

Compute the shortest paths in the graph.

• Graphs

• Digraphs

Parameters

• sources (int or iterable) – Sources nodes.

• targets (int or iterable) – Target nodes.

• method

The method to be used.

• 'D' (Dijkstra),

• 'BF' (Bellman-Ford),

• 'J' (Johnson).

• unweighted – If True, the weights of the edges are ignored

• n_jobs – If an integer value is given, denotes the number of workers to use (-1 means the maximum number will be used). If None, no parallel computations are made.

Returns

paths – If single source and single target, return a list containing the nodes on the path from source to target. If multiple sources or multiple targets, return a list of paths as lists. An empty list means that the path does not exist.

Return type

list

Examples

>>> from sknetwork.data import linear_digraph
[0, 1, 2]
[]
[[0, 1], [0, 1, 2]]
[[0, 1, 2], [1, 2]]


Summary of the different methods and their worst-case complexity for $$n$$ nodes and $$m$$ edges (for the all-pairs problem):

Method

Worst-case time complexity

Remarks

Dijkstra

$$O(n^2 \log n + nm)$$

For use on graphs with positive weights only

Bellman-Ford

$$O(nm)$$

For use on graphs without negative-weight cycles only

Johnson

$$O(n^2 \log n + nm)$$

## Metrics¶

sknetwork.path.diameter(adjacency: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray], n_sources: Optional[Union[int, float]] = None, n_jobs: Optional[int] = None) → int[source]

Lower bound on the diameter of a graph which is the length of the longest shortest path between two nodes.

Parameters

• n_sources

Number of node sources to use for approximation.

• If None, compute exact diameter.

• If int, sample n_sample source nodes at random.

• If float, sample (n_samples * n) source nodes at random.

• n_jobs – If an integer value is given, denotes the number of workers to use (-1 means the maximum number will be used). If None, no parallel computations are made.

Returns

diameter

Return type

int

Examples

>>> from sknetwork.data import house