Tidygraph：沿最短路径获取节点序列

Question

我想使用 tidygraph 获取沿两个节点之间最短路径的节点序列。考虑这个例子。

library(tidygraph)
library(tidyverse)
demo_netw <- tbl_graph(nodes = tibble(node_id = c("A", "B", "C", "D")),
                       edges = tribble(~from, ~to,
                                       "B", "A",
                                       "D", "C",
                                       "A", "D"))
shortest_path_from_B_to_C <-
  demo_netw %>%
  convert(to_shortest_path, node_id == "B", node_id == "C")
shortest_path_from_B_to_C

## # A tbl_graph: 4 nodes and 3 edges
## #
## # A rooted tree
## #
## # Node Data: 4 x 2 (active)
##   node_id .tidygraph_node_index
##   <chr>                   <int>
## 1 A                           1
## 2 B                           2
## 3 C                           3
## 4 D                           4
## #
## # Edge Data: 3 x 3
##    from    to .tidygraph_edge_index
##   <int> <int>                 <int>
## 1     2     1                     1
## 2     4     3                     2
## 3     1     4                     3

输出显示节点A、B、C、D在最短路径上，但并没有显示出序列节点是 B -> A -> D -> C。返回的边数据也不显示边的顺序。

我知道我可以用 igraph 完成这些任务。

library(igraph)
demo_igraph <-
  demo_netw %>%
  activate(edges) %>%
  as_tibble() %>%
  graph_from_data_frame()

# We cannot easily access the node_id column, so we must manually make the
# mapping "B" -> "2", "C" -> "3"
shortest_paths(demo_igraph, "2", "3")$vpath

## [[1]]
## + 4/4 vertices, named, from a854191:
## [1] 2 1 4 3

但是，由于多种原因，这并不优雅。

我正在寻找不求助于其他软件包的 tidygraph 解决方案。
导出tidygraph边缘数据时，节点数据列node_id中包含的信息丢失，所以我必须手动制作映射“B”->“2”，“C”-> “3”或编写更复杂的代码来加入来自节点和边缘数据的信息。
我希望输出是 "B" "A" "D" "C"，而不是 2 1 4 3。

有没有什么简单的方法可以直接用tidygraph获取最短路径上的节点序列？

Answer 1

编辑： 可以使用任何名称作为 node_key 参数，这将导致成功构建 tbl_graph。但是，仅当列在节点数据中被称为 name 时，将其传递给 igraph 函数才有效。这可能是要向 tidygraph.

报告的问题

可以直接使用 tidygraph 执行此操作，方法是使用 igraph 函数，考虑以下因素：

一个tbl_graph对象子类igraph所以不需要将你的数据转换成一个tibble然后从一个数据框到一个igraph，你可以直接运行 igraph函数到 tbl_graph 对象。
构建图表时可以设置 node_key 参数。这被传递到 igraph 并因此存储在其属性中。但是，像您在示例中所做的那样使用 node_id 将不起作用，因为 igraph 在内部对节点索引使用相同的名称，因此将以某种方式被覆盖。因此，如果您调用不同于“node_id”的节点键列，则可以将其设置为您的 node_key 参数。
根据 tidygraph 应该可以将列名作为 node_key 传递，参见 here。

node_key The name of the column in nodes that character represented to and from columns should be matched against. If NA the first column is always chosen. This setting has no effect if to and from are given as integers.

如果具有 ID 的列称为 name，那么这也被 igraph 识别，并且在调用 shortest_paths() 函数时将 return 命名路径。但是，当将任何其他节点列作为 node_key 传递时，这似乎会失败，因此对于此示例，我们可以调用列 name.

在下面查看在构造过程中进行了这些少量修改的相同代码，以及您要求的输出。

library(tidygraph)
library(tidyverse)
library(igraph)

demo_netw <- tbl_graph(nodes = tibble(name = c("A", "B", "C", "D")),
                       edges = tribble(~from, ~to,
                                       "B", "A",
                                       "D", "C",
                                       "A", "D"))

shortest_paths(demo_netw, "B", "C")$vpath
#> [[1]]
#> + 4/4 vertices, named, from e00d5b2:
#> [1] B A D C

Tidygraph：沿最短路径获取节点序列

Tidygraph: obtain sequence of nodes along shortest path

r

tidyverse

igraph

tidygraph