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[];