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 to True 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 to True 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]])