[Top][All Lists]
[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