Tidygraph: obtain sequence of nodes along shortest path

Question

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?

Answer 1

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

可以tidygraph通过使用igraph函数直接使用 来执行此操作，请考虑以下因素：

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

node_key节点中的列名称，该字符代表与列之间的匹配。如果不适用，则始终选择第一列。如果 to 和 from 以整数形式给出，则此设置无效。

如果具有 ID 的列被调用name，那么它也会被 识别igraph，并且在调用函数时将返回命名路径shortest_paths()。然而，当将任何其他节点列作为 a 传递时，这似乎会失败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