基于具有正确顺序的路径对图进行子集化

Question

给出的是下图：

g= graph.formula(A -+ B,
                 B -+ C,
                 A -+ C,
                 B -+ D,
                 C -+ D
)
plot(g)

总体目标是将图拆分成所有简单的子图。在我目前的方法中，我收集了从根 "A" 到离开 "D" 的所有简单路径。

paths= all_simple_paths(g, from = "A", to = "D")

然后我根据 paths.

生成图 g 的所有子图

sg= lapply(paths, function(x) induced_subgraph(g, x))

虽然 paths[[1]] 包含路径 "A" "B" "C" "D" 的顶点序列，但第一个子图 sg[[1]] 并不完全遵循路径的序列：

IGRAPH DN-- 4 5 -- 
+ attr: name (v/c)
+ edges (vertex names):
[1] A->B A->C B->C B->D C->D

问题：

sg[[1]] 包含 2 个边 A->C, B->D 太多。我理解 igraphs induced_subgraph() 函数在选择提供的顶点时可以正常工作，同时忽略作为进一步约束的序列。

问题：

如何根据完全遵循顶点序列的 paths 将 g 子集化为所有简单图形？

评论：

我无法通过 get.all.shortest.paths() 实现将图拆分为所有简单子图的总体目标，因为它找不到 paths[[1]] 和 "A" "B" "C" "D"。

Answer 1

试试这个

library(igraph)
set.seed(1)
g= graph.formula(A -+ B,
                 B -+ C,
                 A -+ C,
                 B -+ D,
                 C -+ D
)
coords <- layout.auto(g)
rownames(coords) <- V(g)$name

paths <- all_simple_paths(g, from = "A", to = "D")
sg <- lapply(paths, function(x) subgraph.edges(g, get.edge.ids(g, x[tail(head(rep(seq(x), each = 2), -1), -1)])))

par(mfrow = c(2, 2))
invisible(lapply(c(list(g), sg), function(x) plot(x, layout = coords[V(x)$name, ])))

基于具有正确顺序的路径对图进行子集化

Subsetting graph based on a path with correct sequence

r

igraph