获取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 列表、单个顶点名称、顶点名称列表。None 表示所有顶点。
• mode - 路径的方向性。IN表示计算传入路径，OUT表示计算传出路径，ALL表示计算两者。

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

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

1. 初始化一个空图形，然后从图形中添加路径的路径列表中添加所有路径
   

   或者

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