路径

距离

获取从源节点（或一组源节点）到其他节点的跳数距离。

参数:

input_matrix – 图的邻接矩阵或二部邻接矩阵。
source – 如果是整数，则为源节点的索引。如果列表或数组，则为源节点的索引（返回到其中一个节点的最短距离）。
source_row – 对于二部图，源节点在行和列上的索引。参数 source_row 是 source 的别名（至少其中一个必须为 None）。
source_col – 对于二部图，源节点在行和列上的索引。参数 source_row 是 source 的别名（至少其中一个必须为 None）。
transpose – 如果为 True，则转置输入矩阵。
force_bipartite – 如果为 True，则将输入矩阵视为二部图的二部邻接矩阵。如果指定了参数 source_row 或 source_col，则将其设置为 True。

返回值:

distances – 从源节点到其他节点的距离向量（如果不存在从源节点到目标节点的路径，则距离为 -1）。对于二部图，返回两个向量，一个用于行，另一个用于列。

返回值类型:

形状为 (n_nodes,) 的 np.ndarray

示例

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

最短路径

获取从源节点（或一组源节点）到其他节点的最短路径（以跳数表示）。

参数:

input_matrix – 图的邻接矩阵或二部邻接矩阵。
source – 如果是整数，则为源节点的索引。如果是列表，则为源节点的索引（返回到其中一个节点的最短距离）。
source_row – 对于二部图，源节点在行和列上的索引。参数 source_row 是 source 的别名（至少其中一个必须为 None）。
source_col – 对于二部图，源节点在行和列上的索引。参数 source_row 是 source 的别名（至少其中一个必须为 None）。
force_bipartite – 如果为 True，则将输入矩阵视为二部图的二部邻接矩阵。如果指定了参数 source_row 或 source_col，则将其设置为 True。

返回值:

path – 从源节点（或一组源节点）到其他节点的最短路径的邻接矩阵。如果输入图是二部图，则矩阵的形状为 (n_row + n_col, n_row + n_col)，其中新索引对应于原始图的行列。

返回值类型:

sparse.csr_matrix

示例

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

搜索

sknetwork.path.breadth_first_search(adjacency: csr_matrix, source: int)[source]

从某个节点开始的广度优先排序。

参数:

adjacency – 图的邻接矩阵。
source (int) – 源节点。

返回值:

index – 与从源节点开始的广度优先搜索相对应的节点索引。向量的长度是从源节点可达的节点数量。

返回值类型:

np.ndarray