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'
(BellmanFord),'J'
(Johnson).
return_predecessors – If
True
, the size predecessor matrix is returnedunweighted – If
True
, the weights of the edges are ignoredn_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 pointi
to pointj
along the graph. If no path exists between nodesi
andj
, thendist_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 pointi
: each entrypredecessors[i, j]
gives the index of the previous node in the path from pointi
to pointj
. If no path exists between nodesi
andj
, thenpredecessors[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'
(BellmanFord),'J'
(Johnson).
unweighted – If
True
, the weights of the edges are ignoredn_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 worstcase complexity for \(n\) nodes and \(m\) edges (for the allpairs problem):
Method 
Worstcase time complexity 
Remarks 

Dijkstra 
\(O(n^2 \log n + nm)\) 
For use on graphs with positive weights only 
BellmanFord 
\(O(nm)\) 
For use on graphs without negativeweight cycles only 
Johnson 
\(O(n^2 \log n + nm)\) 
Search¶

sknetwork.path.
breadth_first_search
(adjacency: scipy.sparse.csr.csr_matrix, source: int, return_predecessors: bool = True)[source]¶ Breadthfirst ordering starting with specified node.
Graphs
Digraphs
Based on SciPy (scipy.sparse.csgraph.breadth_first_order)
 Parameters
adjacency – The adjacency matrix of the graph
source (int) – The node from which to start the ordering
return_predecessors (bool) – If
True
, the size predecessor matrix is returned
 Returns
node_array (np.ndarray) – The breadthfirst list of nodes, starting with specified node. The length of node_array is the number of nodes reachable from the specified node.
predecessors (np.ndarray) – Returned only if
return_predecessors == True
. The list of predecessors of each node in a breadthfirst tree. If nodei
is in the tree, then its parent is given bypredecessors[i]
. If nodei
is not in the tree (and for the parent node) thenpredecessors[i] = 9999
.

sknetwork.path.
depth_first_search
(adjacency: scipy.sparse.csr.csr_matrix, source: int, return_predecessors: bool = True)[source]¶ Depthfirst ordering starting with specified node.
Graphs
Digraphs
Based on SciPy (scipy.sparse.csgraph.depth_first_order)
 Parameters
adjacency – The adjacency matrix of the graph
source – The node from which to start the ordering
return_predecessors – If
True
, the size predecessor matrix is returned
 Returns
node_array (np.ndarray) – The depthfirst list of nodes, starting with specified node. The length of node_array is the number of nodes reachable from the specified node.
predecessors (np.ndarray) – Returned only if
return_predecessors == True
. The list of predecessors of each node in a depthfirst tree. If nodei
is in the tree, then its parent is given bypredecessors[i]
. If nodei
is not in the tree (and for the parent node) thenpredecessors[i] = 9999
.
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.