MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: copying a variable

I still don't understand completely what you are doing, but I will try
to give some suggestions below.  I hope they will be useful.

On Sat, Sep 27, 2008 at 18:06, ramiro <ramiro.barrantes at> wrote:
> Hi Szabolcs,
> I just tried with expressions and it looks great.  I think I was just
> treating the DownValues as a kind of hash table (inspired a bit by the
> mathematica paclets)   I think this is an important step in defining how I
> will work with tree (I work with evolutionary trees in biology).  So here
> are two questions as I'm afraid I'm missing mathematica tricks:
> 1) If I want to find out the ancestor of a node, would it be best to a) just
> traverse the tree every time (maybe the speed won't be an issue), b) do some
> combination of Position, etc.  to figure it out; c) keep a separate record
> of definitions (like the one I had) of who's the ancestor and the children
> of who.

The easiest (but not necessarily fastest) way to do this is to
traverse the complete tree and use pattern matching:

Let us define an example tree to work on:

tree = "a"["b"["A", "B"], "C", "c"["d"["D"], "E"], "F"]

This is what it looks like (I'm assuming that you have Mathematica 6):


This function finds parents of all occurrences of a node:

allParents[tree_, node_] :=
 Cases[tree, par_[___, node, ___] :> par, {0, Infinity}]

Perhaps every node has only a single occurrence, so it would be better
to stop searching as soon as we find it:

firstParent[tree_, node_] :=
 First@Cases[tree, par_[___, node, ___] :> par, {0, Infinity}, 1]

This is the list of all child nodes:

In[23]:= children = Level[tree, {-1}]
Out[23]= {"A", "B", "C", "D", "E", "F"}

And these are their parents:

In[24]:= firstParent[tree, #] & /@ children
Out[24]= {"b", "b", "a", "d", "c", "a"}

If you need to find certain child nodes very frequently by their
names, you could create an index of their positions:

In[25]:= (# -> First@Position[tree, #] &) /@ children
Out[25]= {"A" -> {1, 1}, "B" -> {1, 2}, "C" -> {2}, "D" -> {3, 1, 1},
"E" -> {3, 2}, "F" -> {4}}

For a large tree we can make a dispatch table (see Dispatch) of this
list of rules for fast lookup.

Here I treated the end child nodes differently from those nodes that
can have children themselves.  If they should be equivalent, then you
could work with expressions like "a"["b"[], "c"["d"[], "e"[]]]

> 2) What if I want to do an operation on a tree, I was thinking about reading
> the tree and then making "definitions" of children, ancestors, etc.  (just
> because I am going to use those many times), then making the operation
> somehow and outputting the tree again as an expression. e.g.
> reroot[treeX_]:=Module[{definitions},
>  definition = "read all the tree data, ancestors, children, root, etc."
> based on treeX
>  .... reroot the tree
>  make a new expression based on rerooted tree
>  output expression
> ]

You can use Delete, Insert, ReplacePart, Cases, DeleteCases, Replace,
etc. to manipulate trees.

For example, ReplacePart[tree, 0 -> "x"] replaces the root of the tree with "x".

"x"[tree] attaches tree to a new root "x".

> Thanks for helping. Any suggestions or comments much appreciated.

  • Prev by Date: Re: How to debug init.m?
  • Next by Date: Re: copying a variable
  • Previous by thread: Re: copying a variable
  • Next by thread: Re: copying a variable