如何得到图中的一个强连通分量的边列表？ [英] How to get the edge list of a strongly connected components in a graph?

问题描述

我有一个权有向重图的几个周期。随着的igraph 包集群功能，我可以得到节点属于强连通分量。但我需要形成一个周期的节点的路径/订单。

I have a weighted directed multigraph with a few cycles. With clusters function in igraph package, I can get the nodes belongs to a strongly connected components. But I need the path/order of the nodes that form a cycle.

修改 @ josilber的响应之后，

EDIT after @josilber's response

我有一个非常密集的图形，具有30个节点，并在2000年左右边缘。因此， graph.get.subisomorphisms.vf2 需要很长时间才能在我的情况下运行。

I have a very dense graph, with 30 nodes and around 2000 edges. So graph.get.subisomorphisms.vf2 takes too long to run in my case.

我不熟悉的图形算法，但我想，也许做一个DFS原来的或相反的图形，并使用序或 order.out 可能的工作，但不知道。

I'm not familiar with graph algorithm, but I'm thinking maybe do a DFS to the original or reverse graph and use the order or order.out might work, but not sure.

或者任何其他的想法，使这个运行速度更快，欢迎！

Or any other ideas to make this run faster are welcomed!

示例

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

我如何得到一个周期这里的权重最高的边列表？谢谢！

How do I get the edge list of a cycle with the highest weight here? Thanks!

推荐答案

假设在每个强连通分量的所有节点形成循环，而你只关心这个大周期（例如，在你的榜样，你只是有兴趣在周期与节点1点21分和周期与节点22时23分），然后就可以提取在形成循环的节点顺序，抓住上边缘的权重，并计算周期的总重量

Assuming that all nodes in each strongly connected component form a cycle and that you're only interested in this large cycle (e.g. in your example you're just interested in the cycle with nodes 1:21 and the cycle with nodes 22:23), then you can extract the node order that forms the cycle, grab the weights on the edges, and compute the total weight of the cycle.

# 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

现在，你可以抓住每一个周期的边缘权重的总和：

Now you can grab the sum of the edge weights for each cycle:

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 调用可能是大图很慢。

Note that this is in general NP-hard, because finding a Hamiltonian cycle in a general graph is NP-hard. Therefore the graph.get.subisomorphisms.vf2 call could be quite slow for large graphs.

这篇关于如何得到图中的一个强连通分量的边列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！