Path

Standard algorithms related to graph traversal.

Most algorithms are adapted from SciPy.

Shortest path

sknetwork.path.get_distances(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) – Matrix of distances between nodes. dist_matrix[i,j] gives the shortest distance from the i-th source to node j in the graph (infinite if no path exists from the i-th source to node j).

• 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 the i-th source: each entry predecessors[i, j] gives the index of the previous node in the path from the i-th source to node j (-1 if no path exists from the i-th source to node j).

Examples

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

sknetwork.path.get_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.

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.get_diameter(adjacency: Union[scipy.sparse._csr.csr_matrix, numpy.ndarray], n_sources: Optional[Union[int, float]] = None, unweighted: bool = False, 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.

• unweighted – Whether or not the graph is unweighted.

• 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
>>> d_exact
2
>>> d_approx <= d_exact
True
>>> d_approx <= d_exact
True


Notes

This is a basic implementation that computes distances between nodes and returns the maximum.

sknetwork.path.get_radius(adjacency: Union[scipy.sparse._csr.csr_matrix, numpy.ndarray], n_sources: Optional[Union[int, float]] = None, unweighted: bool = False, n_jobs: Optional[int] = None) int[source]

Computes the radius of the graph which. The radius of the graph is the minimum eccentricity of the graph.

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.

• unweighted – Whether the graph is unweighted.

• 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

Return type

int

Notes

This is a basic implementation that computes distances between nodes and returns the maximum.

sknetwork.path.get_eccentricity(adjacency: Union[scipy.sparse._csr.csr_matrix, numpy.ndarray], node: int, unweighted: bool = False, n_jobs: Optional[int] = None) int[source]

Computes the eccentricity of a node. The eccentricity of a node, u, is the maximum length of the shortest paths from u to the other nodes in the graph.

Parameters

• node – The node to compute the eccentricity for.

• unweighted – Whether or not the graph is unweighted.

• 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

eccentricity

Return type

int