Path
Distances
- sknetwork.path.get_distances(input_matrix: scipy.sparse._csr.csr_matrix, source: Optional[Union[int, Iterable]] = None, source_row: Optional[Union[int, Iterable]] = None, source_col: Optional[Union[int, Iterable]] = None, force_bipartite: bool = False) Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]] [source]
Get the distances from a source (or a set of sources) in number of hops.
- Parameters
input_matrix – Adjacency matrix or biadjacency matrix of the graph.
source – If an integer, index of the source node. If a list, indices of source nodes (the shortest distances to one of these nodes in returned).
source_row – For bipartite graphs, index of source nodes on rows and columns. The parameter source_row is an alias for source (at least one of them must be
None
).source_col – For bipartite graphs, index of source nodes on rows and columns. The parameter source_row is an alias for source (at least one of them must be
None
).force_bipartite – If
True
, consider the input matrix as the biadjacency matrix of a bipartite graph. Set toTrue
is the parameters source_row or source_col re specified.
- Returns
distances – Vector of distances from source (distance = -1 if no path exists from the source). For a bipartite graph, two vectors are returned, one for the rows and one for the columns.
- Return type
np.ndarray of shape (n_nodes,)
Examples
>>> from sknetwork.data import cyclic_digraph >>> adjacency = cyclic_digraph(3) >>> get_distances(adjacency, source=0) array([0, 1, 2]) >>> get_distances(adjacency, source=[0, 2]) array([0, 1, 0])
Shortest paths
- sknetwork.path.get_shortest_path(input_matrix: scipy.sparse._csr.csr_matrix, source: Optional[Union[int, Iterable]] = None, source_row: Optional[Union[int, Iterable]] = None, source_col: Optional[Union[int, Iterable]] = None, force_bipartite: bool = False) Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]] [source]
Get the shortest paths from a source (or a set of sources) in number of hops.
- Parameters
input_matrix – Adjacency matrix or biadjacency matrix of the graph.
source – If an integer, index of the source node. If a list, indices of source nodes (the shortest distances to one of these nodes in returned).
source_row – For bipartite graphs, index of source nodes on rows and columns. The parameter source_row is an alias for source (at least one of them must be
None
).source_col – For bipartite graphs, index of source nodes on rows and columns. The parameter source_row is an alias for source (at least one of them must be
None
).force_bipartite – If
True
, consider the input matrix as the biadjacency matrix of a bipartite graph. Set toTrue
is the parameters source_row or source_col are specified.
- Returns
path – Adjacency matrix of the graph of the shortest paths to the source node (or the set of source nodes). If the input graph is a bipartite graph, the shape of the matrix is (n_row + n_col, n_row + n_col) with the new index corresponding to the rows then the columns of the original graph.
- Return type
sparse.csr_matrix
Examples
>>> from sknetwork.data import cyclic_digraph >>> adjacency = cyclic_digraph(3) >>> path = get_shortest_path(adjacency, source=0) >>> path.toarray().astype(int) array([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
Search
- sknetwork.path.breadth_first_search(adjacency: scipy.sparse._csr.csr_matrix, source: int)[source]
Breadth-first ordering starting from some node.
- Parameters
adjacency – Adjacency matrix of the graph.
source (int) – Source node.
- Returns
index – Node index corresponding to the breadth-first-search from the source. The length of the vector is the number of nodes reachable from the source.
- Return type
np.ndarray