Re: Help !!!!!!! (Tree Package included)

• To: mathgroup at smc.vnet.net
• Subject: [mg13315] Re: Help !!!!!!! (Tree Package included)
• From: Daniel Reeves <dreeves at flip.eecs.umich.edu>
• Date: Mon, 20 Jul 1998 02:49:29 -0400
• Organization: University of Michigan EECS
• References: <6llcf5\$dh5@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```I have a package for trees that makes your problem more straightforward.
(The package is included at the end of this message.)

Needs["Tree`"];

A=
{{1,2},{1,3},{2,4},{2,5},{4,6},{4,7},{5,8},{5,9},{6,10},{6,11},{7,12},{7,13},{10,14},{10,15},{10,16},{11,17},{11,18},{11,19},{12,20},{12,21}};

T= parChildListToTree[1,A]

B= treeMap[({parents[#][[1]],#})&,T]//Rest

(* that's it; we can use printTree now to visualize it better *)

printTree[Prepend[B,"(this is the root -- 1)"]]

(this is the root -- 1)
{1, 2}
{2, 4}
{4, 6}
{6, 10}
{10, 14}
{10, 15}
{10, 16}
{6, 11}
{11, 17}
{11, 18}
{11, 19}
{4, 7}
{7, 12}
{12, 20}
{12, 21}
{7, 13}
{2, 5}
{5, 8}
{5, 9}
{1, 3}

Hope this is useful.  If anyone has comments or suggestions on my tree
package, I'd very much like to hear them.

Thanks,
Daniel

--
Daniel Reeves  dreeves at umich.edu
http://ai.eecs.umich.edu/people/dreeves

(***********************************************************************
This file is intended to be loaded into the Mathematica kernel using
the package loading commands Get or Needs.
***********************************************************************)

BeginPackage["Tree`"];

children::usage="children[node_] returns a list of the children of
node.";

parents::usage=
"parents[node_] returns a list of the parents of node... this is not
well \ thought out... the idea was that a node could appear in
different places in a \ tree but in that case we'd have to have it's
whole ancestry to make it \ unique... TODO!   For now, all the nodes
have to be unique.";

tree::usage=
"tree[root_] returns a list representation of the tree rooted at root.
A \ tree is represented as {root, subtree1, subtree2, ...} A leaf is
just \ {root}.";

processParChild::usage=
"processParChild[{parent_,child_}] takes the parent-child pair and
sets the \ 'pointers' appropriately.";

parChildListToTree::usage=
"parChildListToTree[root_,{{parent,child}1, {parent,child}2, ...}]
creates \ a tree from the parent-child pairs and returns the list
representation of the \ tree.  See tree.";

parChildListToTreeList::usage=
"similar to parChildListToTree but you don't specify a root.  Instead
it \ finds all the roots for you and returns a list of trees.  See
tree.";

treeMap::usage=
"treeMap[function_,tree_] takes a function and a tree (see tree) and \
applies the function to each node in the tree, returning the new
tree.";

printTree::usage=
"printTree[tree_] does what it says.  See tree for what to pass in.";

Begin["`Private`"];

Off[General::spell1];

children[_]={};    (* defaults *)
parents[_]={};

tree[root_]:={root}/;children[root]=={}
tree[root_]:=Prepend[tree/@children[root],root]

processParChild[{parent_,child_}]:=(
children[parent]=children[parent]\[Union]{child};
parents[child]=parents[child]\[Union]{parent})

parChildListToTreeList[parChildList_]:=
(
processParChild/@parChildList;
tree/@Union[

Select[(#\[LeftDoubleBracket]1\[RightDoubleBracket]&)/@parChildList,
parents[#]=={}&]]
)

parChildListToTree[root_,parChildList_]:=
(
processParChild/@parChildList;
tree[root]
)

treeMap[f_,{root_}]:={f[root]}
treeMap[f_,{root_,subtrees__}]:=Prepend[treeMap[f,#]&/@{subtrees},f[root]]

printTree[{root_},indent_:0]:=
WriteString[\$Output,Nest[StringJoin[#,"  "]&,"",indent],root,"\n"]
printTree[{root_,subtrees__},indent_:0]:=(printTree[{root},indent];
printTree[#,indent+1]&/@{subtrees};)

End[];   (* Private context *)

EndPackage[];

```

• Prev by Date: Re: Fast help for circle problem
• Next by Date: RE: Fast help for circle problem
• Previous by thread: output to a plain text file
• Next by thread: Boom!