r - 获取n个节点间最短路径的子图

Question

我有一个未加权的图，我想得到一个子图，该子图的节点和边包含 n 个已知节点之间的最短路径。在本例中有 3 个节点(11、29 和 13 是名称)。

问题

我如何获得 R 中 n 个节点之间的最短路径子图？

MWE

library(ggraph)
library(igraph)

hs <- highschool[highschool$year == '1958',]
set.seed(11)
graph <- graph_from_data_frame(hs[sample.int(nrow(hs), 60),])


# plot using ggraph
ggraph(graph, layout = 'kk') + 
    geom_edge_fan() + 
    geom_node_text(aes(label = name)) 

期望的输出

所需的输出将是以下绿色子图(或者接近，我正在观察上面的图并从视觉上挑选出子图)忽略/删除其他节点和边。

Answer 1

你找不到n个节点之间的最短路径。由于最短路径仅在两个节点之间定义。

我认为您需要从 1 节点到您可以使用的其他 n-1 节点的最短路径
get_all_shortest_paths(v, to=None, mode=ALL) 来自 igraph 库。

• v - 计算路径的来源
• to - 描述目标的顶点选择器计算的路径。这可以是单个顶点 ID，顶点列表ID，单个顶点名称，顶点名称列表。无表示所有顶点。
• mode - 路径的方向性。 IN表示计算输入路径，OUT 表示计算输出路径，ALL 表示计算两者。

返回:列表中从给定节点到图中每个其他可达节点的所有最短路径。
get_all_shortest_paths

因此，现在您必须根据最短路径列表创建一个图。

1. 初始化一个空图，然后从列表中添加所有路径到它路径
   adding path in graph

   或

2. 为找到的每条最短路径制作一个图，并取图并集。
   union igraph