Btw. if the maximum out-component is defined as the out-component of the
largest strongly connected component (what if there is no largest, btw?),
then all you need to do is to do a BFS from the vertices of the largest
strongly connected component:
library(igraph)
ER2 <- erdos.renyi.game(100000, 200000, "gnm", directed=TRUE)
scc <- clusters(ER2, mode="strong")
largest_scc_v <- which(scc$membership == which.max(scc$csize))
scc_bfs <- graph.bfs(ER2, root=largest_scc_v, neimode="out",
unreachable=FALSE)
reachable <- na.omit(scc_bfs$order)
out_comp <- setdiff(reachable, largest_scc_v)
This whole thing takes less than a second on my laptop.
Gabor
On Wed, Feb 26, 2014 at 9:59 PM, Gábor Csárdi <[email protected]>wrote:
> First measure what exactly is slow with Rprof().
>
> Gabor
>
>
> On Wed, Feb 26, 2014 at 9:41 PM, [email protected]
> <[email protected]>wrote:
>
>> Hi!
>>
>> Iam trying to find the maximum out-component in a erdos-renyi random
>> graph.
>>
>> Using the array GSCCnod to record the vertices in the maximum strongly
>> connected component,
>> Goutnod to record that if a vertice is in the maximum out-component:
>> Goutnod[i]==-1 means that vertice i is not in the maximum out-component
>> and Goutnod[i]==1 means that vertice i is in the maximum out-component.
>>
>> But the graph contains too many vertices. It takes too much time to
>> compute Goutnod. How can I make it faster.
>>
>> Here is the source code:
>>
>> ER2 <- erdos.renyi.game(100000, 200000, "gnm", TRUE)
>>
>> SGer2_CluMem=clusters(ER2, "strong")$membership
>> SGer2_CluSiz=clusters(ER2, "strong")$csize
>> SGer2_CluNum=clusters(ER2, "strong")$no
>>
>> Nummax <-0
>> for (i in 1:SGer2_CluNum)
>> {
>> if (SGer2_CluSiz[i] > Nummax)
>> {
>> Nummax <- SGer2_CluSiz[i]
>> Maxmem <- i
>> }
>> }
>>
>> GSCCnod <- rep(0, Nummax)
>> j <- 1
>> for (i in 1:100000)
>> {
>> if (SGer2_CluMem[i] == Maxmem)
>> {
>> GSCCnod[j] <- i
>> j <- j + 1
>> }
>> }
>>
>> Goutnod <- rep(-1,100000)
>> for (i in 1:Nummax)
>> {
>> gout <- subcomponent(ER2, GSCCnod[i], "out")
>> len <- length(gout)
>> for (k in 1: len)
>> Goutnod[gout[k]] <- 1
>> }
>>
>>
>> Thank you
>> Best
>> Xueming
>> ------------------------------
>> [email protected]
>>
>> _______________________________________________
>> igraph-help mailing list
>> [email protected]
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
