Tidygraph:获取沿最短路径的节点序列 [英] Tidygraph: obtain sequence of nodes along shortest path

问题描述

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

库(tidygraph)图书馆(tidyverse)demo_netw <-tbl_graph(nodes = tibble(node_id = c(A"，B"，C"，D"))，边缘 = tribble(~from, ~to,B"、A"、D"、C"、A"、D"))shortest_path_from_B_to_C <-demo_netw %>%转换(to_shortest_path，node_id ==B"，node_id ==C")shortest_path_from_B_to_C## # 一个 tbl_graph:4 个节点和 3 个边##### # 一棵有根的树##### # 节点数据:4 x 2(活动)## node_id .tidygraph_node_index## <chr><int>## 1 A 1## 2 B 2## 3 C 3## 4 D 4##### # 边缘数据:3 x 3## 从到 .tidygraph_edge_index##<int><int><int>## 1 2 1 1## 2 4 3 2## 3 1 4 3

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

我知道我可以使用 igraph 完成此类任务.

库(igraph)demo_igraph <-demo_netw %>%激活(边缘)%>%as_tibble() %>%graph_from_data_frame()# 我们不能轻易访问 node_id 列，所以我们必须手动制作#映射B"->2"、C"->3"shortest_paths(demo_igraph, "2", "3")$vpath## [[1]]## + 4/4 个顶点，命名，来自 a854191:## [1] 2 1 4 3

然而，由于多种原因，这并不优雅.

• 我正在寻找一种不依赖其他软件包的 tidygraph 解决方案.
• 导出tidygraph边数据时，节点数据列node_id中包含的信息丢失了，所以我必须手动进行映射B"；->2"、C"->3"或者编写更复杂的代码来连接来自节点和边缘数据的信息.
• 我希望输出为 "B"A"D"C"，而不是 2 1 4 3.

是否有一些直接的方法可以直接使用 tidygraph 获取沿最短路径的节点序列?

解决方案

可以使用任何名称作为 node_key 参数，这将导致tbl_graph 的成功构建.但是，将其传递给 igraph 函数仅在节点数据中的列被称为 name 时才起作用.这可能是向 tidygraph 报告的问题.

通过使用 igraph 函数，可以直接使用 tidygraph 执行此操作，考虑以下几点:

1. tbl_graph 对象是 igraph 的子类，因此无需将数据转换为 tibble，然后从数据帧转换为 igraph，您可以直接运行 igraph 函数到 tbl_graph 对象.
2. 可以在构建图形时设置 node_key 参数.这被传递到 igraph 并因此存储在其属性中.但是，像您在示例中所做的那样使用 node_id 将不起作用，因为 igraph 在内部使用相同的名称作为节点索引，因此会以某种方式被覆盖.因此，如果您调用不同于node_id"的节点键列然后，您可以将其设置为您的 node_key 参数.
3. 根据tidygraph，应该可以将列名作为node_key 传递，请参阅此处.

<块引用>

node_key 节点中的列的名称，该列的字符代表列和来自列的字符应与之匹配.如果 NA 总是选择第一列.如果 to 和 from 以整数形式给出，则此设置无效.

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

请参阅下面的相同代码，并在构造过程中进行了这些修改，以及您要求的输出.

library(tidygraph)图书馆(tidyverse)图书馆(igraph)demo_netw <- tbl_graph(nodes = tibble(name = c(A", B", C", D")),边缘 = tribble(~from, ~to,B"、A"、D"、C"、A"、D"))shortest_paths(demo_netw, "B", "C")$vpath#>[[1]]#>+ 4/4 个顶点，命名为 e00d5b2:#>[1] B A D C

I would like to obtain the sequence of nodes along the shortest path between two nodes using tidygraph. Consider this example.

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

The output shows that the nodes A, B, C, and D are on the shortest path, but it does not show that the sequence of nodes is B -> A -> D -> C. The returned edge data does not reveal the sequence of the edges either.

I am aware that I can accomplish such tasks with 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

However, this is inelegant for several reasons.

• I am looking for a tidygraph solution that does not resort to other packages.
• When exporting the tidygraph edge data, the information contained in the node data column node_id is lost, so I must either manually make the mapping "B" -> "2", "C" -> "3" or write much more elaborate code to join the information from the node and edge data.
• I would like the output to be "B" "A" "D" "C", not 2 1 4 3.

Is there some straightforward way to obtain the sequence of nodes along the shortest path directly with tidygraph?

解决方案

EDIT: It is possible to use any name as the node_key parameter, which will result in a successful construction of a tbl_graph. However, passing this onto igraph functions works only when the column is called name within the node data. This might be an issue to report to tidygraph.

It is possible to do this directly with tidygraph, by using igraph functions, considering the following:

1. A tbl_graph object subclasses igraph so there is no need to convert your data to a tibble and then to an igraph from a data frame, you can directly run igraph functions to a tbl_graph object.
2. It is possible to set a node_key argument when constructing your graph. This is passed onto igraph and therefore stored within its attributes. HOWEVER, using node_id as you did in your example will not work, as igraph uses this same name internally for the node indices, and therefore will be somehow overwritten. So if you call the column of your node keys different than "node_id" you can then set this as your node_key parameter.
3. According to tidygraph it should be possible to pass a column name as a node_key, see 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.

If the column with the IDs is called name, then this is also recognized by igraph, and will return named paths when calling a shortest_paths() function. However this seems to fail when passing any other node column as a node_key, so for this example we can call the column name.

See below your same code with these few modifications during construction, and the output you asked for.

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:获取沿最短路径的节点序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！