Services & ResourcesWolfram ForumsMathGroup Archive

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

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