在R中的图中寻找线性路径段

Question

我需要将一个非循环图划分为线性部分。每个部分将是由至少一个节点组成的线性路径。线性部分不能包含任何分支。

例如，下面是一个示例图表：

library(igraph); 
dor = data.frame( from = c(1, 1, 2, 3, 4, 5, 6), 
    to = c(2, 3, 4, 5, 6, 6, 7) )
g = graph_from_data_frame(dor)
plot(g)

​

​

在此图中，有4个线性部分：

1
3 -> 5
2 -> 4
6 -> 7

如何将图划分为线性路径部分？

Answer 1

我认为你想要做的是这样的。如果节点有多条传入边，请删除所有传入边。如果节点有多条传出边，请删除所有传出边。所以我提出的解决方案。对关联边进行计数，如果关联边太多，则将其删除。

## Your original data
library(igraph)
dor = data.frame( from = c(1, 1, 2, 3, 4, 5, 6), 
    to = c(2, 3, 4, 5, 6, 6, 7) )
g = graph_from_data_frame(dor)


g2 = g
TooManyOut = which(sapply(incident_edges(g2, V(g2), mode="out"), length) > 1)
for(TMO in TooManyOut) {
    g2 = delete_edges(g2, attr(incident_edges(g2, V(g2), mode="out")[[TMO]], "vnames"))
}
TooManyIn = which(sapply(incident_edges(g2, V(g2), mode="in"), length) > 1)
for(TMI in TooManyIn) {
    g2 = delete_edges(g2, attr(incident_edges(g2, V(g2), mode="in")[[TMI]], "vnames"))
}
plot(g2)

​

​

当然，您可以使用components获取连接的节点。