Re: [igraph] Quick way to find leaves

[Marcel Salathé]

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