igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] Quick way to find leaves


From: Ken Williams
Subject: [igraph] Quick way to find leaves
Date: Mon, 24 May 2010 15:12:38 -0500
User-agent: Microsoft-Entourage/12.24.0.100205

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





reply via email to

[Prev in Thread] Current Thread [Next in Thread]