Re: [igraph] Quick way to find leaves

[Gábor Csárdi]

Ken,

the V() method should be much faster in the new version of igraph, but
actually the fastest is (imho)

which(degree(g, mode="out")==0)-1

Best,
Gabor

On Mon, May 24, 2010 at 10:12 PM, Ken Williams
<address@hidden> 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
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM