整洁图：获取最短路径上的节点序列

Question

整洁图：获取最短路径上的节点序列

4

我希望使用 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获取最短路径上节点序列的简单方法？

- Michael Gastner

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- loreabad6 · Accepted Answer

编辑： 可以使用任何名称作为node_key参数，这将成功构建一个tbl_graph。然而，将其传递给igraph函数仅在节点数据中的列被称为name时才起作用。这可能是要报告给tidygraph的问题。

可以通过使用igraph函数直接使用tidygraph来完成此操作，考虑以下内容：

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

node_key节点中应该匹配字符表示的列。如果NA，则始终选择第一列。如果以整数形式给出to和from，则此设置无效。

如果ID列称为name，则igraph也将识别它，并在调用shortest_paths()函数时返回命名路径。但是，当传递任何其他节点列作为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