Tracking leaf nodes of a tree

[ses1984]

I am looking at working with the networkx package in a project, but
I'm not sure if it's the best package for me.

I have a project based on a lot of existing data which can be modeled
as a forest of acyclic trees, but has not been, yet. I would first use
networkx to verify that I do indeed have a forest of acyclic trees,
then use it for validation of new data and analysis of the data set in
general.

One operation that I will have to do very frequently is to examine all
the leaf nodes of a tree, but I don't see any methods that do
something like this in the reference material. I was thinking of using
a DiGraph to implement my own tree class that keeps track of leaf
nodes (and the root node), so that I wouldn't have to traverse the
tree every time I wanted to look at the leaves.

I would appreciate a little guidance, because I have a feeling I'm
doing it Wrong. With a capital W.

[Aric Hagberg]

On Tue, Sep 14, 2010 at 7:56 AM, ses1984 <ses...@gmail.com> wrote:
> I am looking at working with the networkx package in a project, but
> I'm not sure if it's the best package for me.
>
> I have a project based on a lot of existing data which can be modeled
> as a forest of acyclic trees, but has not been, yet. I would first use
> networkx to verify that I do indeed have a forest of acyclic trees,
> then use it for validation of new data and analysis of the data set in
> general.
>
> One operation that I will have to do very frequently is to examine all
> the leaf nodes of a tree, but I don't see any methods that do
> something like this in the reference material. I was thinking of using
> a DiGraph to implement my own tree class that keeps track of leaf
> nodes (and the root node), so that I wouldn't have to traverse the
> tree every time I wanted to look at the leaves.

That would work. Or since you are considering using a directed graph
you could get the leaves by inspecting the out-degree. Something like,

In [1]: import networkx as nx

In [2]: G=nx.DiGraph()

In [3]: G.add_path(range(4))

In [4]: leaves=[n for n,d in G.out_degree().items() if d==0]

In [5]: leaves
Out[5]: [3]

or actually better if you just need to iterate over the leaves,

In [9]: leaves=(n for n,d in G.out_degree_iter() if d==0)

In [10]: leaves
Out[10]: <generator object <genexpr> at 0x2d98410>

In [11]: list(leaves)
Out[11]: [3]

Aric

[ses1984]

That is excellent. Thanks.

On Sep 14, 11:41 am, Aric Hagberg <ahagb...@gmail.com> wrote: