CODEWITHSUNDEEP
ralgorithmgraphcycleigraph
qshng
qshng

Reputation: 887

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

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.

EDIT after @josilber's response

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.

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!

Example

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!

Upvotes: 1

Views: 1505

Answers (1)

josliber
josliber

Reputation: 44330

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

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.

Upvotes: 1

Related Questions