Re: [igraph] What is the fast way to find the maximum out-component in a erdos-renyi random graph

[Gábor Csárdi]

First measure what exactly is slow with Rprof(). 

Gabor

On Wed, Feb 26, 2014 at 9:41 PM, address@hidden <address@hidden> 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

---

address@hidden

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help