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