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

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

Notes

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