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

  • adjacency – The adjacency matrix of the graph

  • 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
>>> adjacency = cyclic_digraph(3)
>>> get_distances(adjacency, sources=0)
array([0., 1., 2.])
>>> get_distances(adjacency, sources=0, return_predecessors=True)
(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

  • adjacency – The adjacency matrix of the graph

  • 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
>>> adjacency = linear_digraph(3)
>>> get_shortest_path(adjacency, 0, 2)
[0, 1, 2]
>>> get_shortest_path(adjacency, 2, 0)
[]
>>> get_shortest_path(adjacency, 0, [1, 2])
[[0, 1], [0, 1, 2]]
>>> get_shortest_path(adjacency, [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

  • adjacency – Adjacency matrix of the graph.

  • 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
>>> adjacency = house()
>>> d_exact = get_diameter(adjacency)
>>> d_exact
2
>>> d_approx = get_diameter(adjacency, 2)
>>> d_approx <= d_exact
True
>>> d_approx = get_diameter(adjacency, 0.5)
>>> 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

  • adjacency – Adjacency matrix of the graph.

  • 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

radius

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

  • adjacency – Adjacency matrix of the graph.

  • 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