On Thu, Feb 27, 2014 at 2:47 AM, [email protected] <[email protected]>wrote:
> Hi > > Thank you > > It is really fast, but the elements of scc_bfs$order are all NaN. > I set root to other array which with more than one element, the result of > graph.bfs()$order is NaN. > You are probably using an old version of igraph that had a bug in graph.bfs() and considered only the first vertex in 'root'. Please install the latest version. Btw. if you want your example to be reproducible, please include 1) your igraph version, and 2) set the random seed if you are using random graphs. Thanks. Gabor > > > library(igraph) > > ER2 <- erdos.renyi.game(100, 200, "gnm", directed=TRUE) > > graph.bfs(ER2, root=2, neimode="out",unreachable=FALSE)$order > [1] 2 14 59 64 4 23 82 77 85 93 9 58 25 54 32 33 76 > 62 65 74 98 100 41 29 60 > [26] 18 56 80 1 5 86 95 15 89 43 44 52 34 81 84 53 6 > 91 99 49 63 66 72 10 45 > [51] 22 57 21 27 70 97 30 75 40 92 96 11 71 73 87 39 79 > 94 51 61 37 48 47 68 13 > [76] 35 46 16 83 31 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN > NaN NaN NaN NaN NaN NaN NaN NaN > > graph.bfs(ER2, root=c(1, 2), neimode="out",unreachable=FALSE)$order > [1] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN > NaN NaN NaN NaN NaN NaN NaN NaN > [26] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN > NaN NaN NaN NaN NaN NaN NaN NaN > [51] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN > NaN NaN NaN NaN NaN NaN NaN NaN > [76] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN > NaN NaN NaN NaN NaN NaN NaN NaN > > Am I making some other mistakes? > > BTW: Usually, a out-component is defined as the out-component of a > strongly connected component. The giant strongly connected component and > the giant out-component appear at the same time (Ref: Marian Bouguna et al, > Ceneralized percolation in random directed networks, Physic Review E 72, > 016106, 2005). > > best > Xueming > ------------------------------ > [email protected] > > *From:* Gábor Csárdi <[email protected]> > *Date:* 2014-02-27 11:47 > *To:* Help for igraph users <[email protected]> > *Subject:* Re: [igraph] What is the fast way to find the maximum > out-component in a erdos-renyi random graph > 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 > >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
