如何获取图中强连通分量的边列表？

Question

我有一个带有几个循环的加权定向多图。使用 igraph 包中的 clusters 函数，我可以获得属于强连接组件的节点。但是我需要形成一个循环的节点的path/order。

编辑在@josilber 的回复后

我有一个非常密集的图，有 30 个节点和大约 2000 条边。所以 graph.get.subisomorphisms.vf2 在我的例子中运行花费的时间太长了。

我不熟悉图算法，但我想也许对原始图或反向图进行 DFS 并使用 order 或 order.out 可能有效，但不确定。

或任何其他使运行更快的想法都欢迎！

例子

library(igraph)
set.seed(123)
graph <-graph(c(1,2,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,8,10,9,10,9,10,10,11,10,5,11,12,12,13,13,14,14,15,14,20,15,16, 16,17,17,18,18,19,19,20,20,21,21,1,22,23,22,23,23,22),directed=T)
E(graph)$weight= runif(ecount(graph),0,10)

> clusters(graph, "strong")
$membership
 [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1

$csize
[1]  2 21

$no
[1] 2

如何获取这里权重最高的循环的边列表？谢谢！

Answer 1

假设每个强连接组件中的所有节点都形成一个循环，并且您只对这个大循环感兴趣（例如，在您的示例中，您只对节点 1:21 和节点的循环感兴趣循环与节点 22:23), 然后你可以提取形成循环的节点顺序, 抓取边上的权重, 并计算循环的总权重。

# Compute the node order of the cycle for each component by performing an
# isomorphism with a same-sized directed ring graph
clusts <- clusters(graph, "strong")
(cycles <- lapply(1:clusts$no, function(x) {
  sg <- induced.subgraph(graph, clusts$membership == x)
  n <- sum(clusts$membership == x)
  col <- rep(c(1, 0), c(1, n-1))  # Used to grab isomorphism starting at 1
  sg.idx <- graph.get.subisomorphisms.vf2(sg, graph.ring(n, directed=TRUE), col, col)[[1]]
  which(clusts$membership == x)[sg.idx]
}))
# [[1]]
# [1] 22 23
# 
# [[2]]
#  [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21

现在您可以获取每个循环的边权重之和：

sapply(cycles, function(x) sum(graph[from=x, to=c(tail(x, -1), x[1])]))
# [1]   8.833018 129.959437

请注意，这通常是 NP 难的，因为在一般图中找到哈密顿循环是 NP 难的。因此，对于大型图，graph.get.subisomorphisms.vf2 调用可能会非常慢。

如何获取图中强连通分量的边列表？

How to get the edge list of a strongly connected components in a graph?

r

algorithm

graph

cycle

igraph