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 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) – Matrix of distances between nodes.
dist_matrix[i,j]
gives the shortest distance from thei
-th source to nodej
in the graph (infinite if no path exists from thei
-th source to nodej
).predecessors (np.ndarray, optional) – Returned only if
return_predecessors == True
. The matrix of predecessors, which can be used to reconstruct the shortest paths. Rowi
of the predecessor matrix contains information on the shortest paths from thei
-th source: each entrypredecessors[i, j]
gives the index of the previous node in the path from thei
-th source to nodej
(-1 if no path exists from thei
-th source to nodej
).
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 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) >>> 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)\) |
Search
- sknetwork.path.breadth_first_search(adjacency: scipy.sparse._csr.csr_matrix, source: int, return_predecessors: bool = True)[source]
Breadth-first ordering starting with specified node.
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 breadth-first 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 breadth-first 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]
Depth-first ordering starting with specified node.
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 depth-first 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 depth-first 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.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