Re: [igraph] Quick way to find leaves

[Ken Williams]

I wasn't aware igraph 0.6 was available yet, http://igraph.sourceforge.net/
still says 0.5.3.  Is it still in pre-release?


Here's my version info:

> sessionInfo()
R version 2.10.1 (2009-12-14)
i386-apple-darwin9.8.0

locale:
[1] en_US.UTF-8/en_US.UTF-8/C/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats4    stats     graphics  grDevices utils     datasets  methods
base     

other attached packages:
[1] igraph_0.5.3

loaded via a namespace (and not attached):
[1] tools_2.10.1


Here's my edgelist, the graph was created by doing graph.edgelist(el):

> dput(el)
structure(c(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 11, 12, 6, 14, 15,
16, 5, 18, 19, 20, 20, 22, 23, 23, 25, 26, 27, 28, 29, 26, 25,
32, 33, 34, 32, 36, 37, 22, 39, 40, 41, 42, 41, 41, 45, 46, 47,
48, 49, 46, 1, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 60,
64, 65, 59, 67, 68, 69, 58, 71, 72, 73, 73, 75, 76, 76, 78, 79,
80, 81, 82, 79, 78, 85, 86, 87, 85, 89, 90, 75, 92, 93, 94, 95,
94, 94, 98, 99, 100, 101, 102, 99, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73,
74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104
), .Dim = c(104L, 2L))


Thanks,

 -Ken


On 5/24/10 3:24 PM, "Marcel Salathé" <address@hidden> wrote:

> Ken
> 
> Can you give us a reproducible example? What version of igraph are you using?
> 
> Things work fine for me in igraph 0.6:
> 
> g <- erdos.renyi.game(100, 1/100,directed=T)
>> summary(g)
> Vertices: 100 
> Edges: 87 
> Directed: TRUE 
> No graph attributes.
> No vertex attributes.
> No edge attributes.
>> system.time(for(i in 1:100) {
> +     leaves <- V(g)[degree(g, mode="out")==0]
> +  })
>    user  system elapsed
>   0.039   0.001   0.039
>> system.time(for(i in 1:100) {
> +     n <- vcount(g)-1; leaves <- which(!0:n %in% get.edgelist(g)[,1])-1
> +  })
>    user  system elapsed
>   0.020   0.001   0.022
> 
> 
>> sessionInfo()
> R version 2.10.1 (2009-12-14)
> i386-apple-darwin9.8.0
> 
> locale:
> [1] en_US.UTF-8/en_US.UTF-8/C/C/en_US.UTF-8/en_US.UTF-8
> 
> attached base packages:
> [1] grid      stats     graphics  grDevices utils     datasets  methods   base
> 
> other attached packages:
> [1] igraph_0.6    ggplot2_0.8.7 digest_0.4.2  reshape_0.8.3 plyr_0.1.9
> proto_0.3-8  
> 
> loaded via a namespace (and not attached):
> [1] RColorBrewer_1.0-2 tools_2.10.1
>> 
> 
> Cheers
> marcel
> 
> 
> On May 24, 2010, at 1:12 PM, Ken Williams wrote:
> 
>> Hi,
>> 
>> I have a tree in igraph, and I wanted a good way to find all the leaves
>> (nodes where outdegree = 0).  I noticed that using V() and degree() seems to
>> be several orders of magnitude slower than doing the calculation "by hand"
>> in a fairly brute-force way:
>> 
>>> system.time(for(i in 1:100) {
>>     n <- vcount(g)-1; leaves <- which(!0:n %in% get.edgelist(g)[,1])-1
>>  })
>>   user  system elapsed
>>  0.027   0.001   0.031
>> 
>>> system.time(for(i in 1:100) {
>>     leaves <- V(g)[degree(g, mode="out")==0]
>>  })
>>   user  system elapsed
>> 12.974  15.557  28.374
>> 
>> 
>> The graph I'm working with here is a toy example subset of my data, with
>> only 105 nodes & 104 edges.
>> 
>> Any other recommended way I haven't thought of?
>> 
>> 
>> -- 
>> Ken Williams
>> Sr. Research Scientist
>> Thomson Reuters
>> Phone: 651-848-7712
>> address@hidden
>> 
>> 
>> 
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
> 

-- 
Ken Williams
Sr. Research Scientist
Thomson Reuters
Phone: 651-848-7712
address@hidden