Visualization of Tree Structures

Examples from Genetic Programming and A Model of Tree Growth
3 March 2004

Jason M. Daida, Adam M. Hilss, David J. Ward, and Stephen L. Long

The University of Michigan
Center for the Study of Complex Systems and the Space Physics Research Laboratory
2455 Hayward Avenue
Ann Arrbor, Michigan USA 48109-2143
daida@eecs.umich.edu

Abstract

This Mathematica notebook supports two papers that were presented at GECCO 2003:

Daida, J.M., A.M. Hilss, D.J. Ward, and S.L. Long, “Visualizing Tree Structures in Genetic Programming,”in Proceedings of GECCO 2003. (A long version of the paper appears in the Journal of Genetic Programming and Evolvable Machines.) This paper presents methods to visualize the structure of trees that occur in genetic programming. These methods allow for the inspection of structure of entire trees even though several thousand of nodes may be involved. The methods also scale to allow for the inspection of structure for entire populations and for complete trials even though millions of nodes may be involved. Examples are given that demonstrate how this new way of “seeing” can afford a potentially rich way of understanding dynamics that underpin genetic programming. The examples indicate further studies that might be enabled by visualizing structure at these scales.

Daida, J.M. and A.M. Hilss, “Identifying Structural Mechanisms in Genetic Programming,”in Proceedings of GECCO 2003. This paper presents a hypothesis about an undiscovered class of mechanisms that exist in standard GP. Rather than being intentionally designed, these mechanisms would be an unintended consequence of using trees as information structures. A model is described that predicts outcomes in GP that would arise solely from such mechanisms. Comparisons with empirical results from GP lend support to the existence of these mechanisms.

This notebook includes much of the Mathematica code that was used in the preparation of these papers. As in any Mathematica notebook, you can experiment with the code by executing (shift-return or enter, depending on platform) the bolded mono-space font that looks like this.

Code

The code here will execute when any of code in the section entitled “Visualization and Simulation Examples”is run. An alternative is to select this entire section and evaluate it before the examples are run.

Note that the current convention in the published papers for root node is at depth = 0.

Visualization Code

TreeElementLocations[nodes] -> coordinates, graphics

TreeElementLocations::usage=
"TreeElementLocations[nodes] returns the 2D coordinates that corresponds to each element in the given set of nodes. Note that nodes refers to a set of node indices, where 1 denotes the root of the binomial tree. The indexing convention is starting from the root at the top to the leaves on the bottom. All node indices that are powers of two are on the left of the binomial tree. Example: For a full tree of Depth = 1, nodes = {1, 2, 3}."; 


TreeElementLocations[nodes_] :=

Module[{i, locations, theta, radius},
    (* ----------*)
    (* MACROs *)
    
    (* This macro computes for possible angles at a particular depth *)
    Phi[D_, n_] :=  N[Mod[(90 + (360 / 2^D) + (n (360 / 2^(D-1)))),360] Degree];
    
    (* This macro computes the coordinates based on phi and depth *)
    RingElement[theta_] := {N[Cos[theta]], N[Sin[theta]]};    
        
    (* -------------------------------------------------------------------*)

	
	(* Allocate memory for coordinates *)
	locations = Table[{0,0},{Length[nodes]}];
		
	(* Convert node elements to locations *)
	Do[
	   radius = Ceiling[Log[2, nodes[[i]]+1]] - 1;
	   theta  = Phi[radius+1, nodes[[i]]];
	   locations[[i]] = radius RingElement[theta];,	
	{i, Length[nodes]}];
	
 	Return[locations];
 	     
]

GraphTreeTwo[ nodes] -> graphics

GraphTreeTwo::usage=
"GraphTreeTwo[nodes] generates a plot of a binary tree as a function of nodes and tree element locations. Note that nodes refers to a set of node indices, where 1 denotes the root of the binomial tree. The indexing convention is starting from the root at the top to the leaves on the bottom. All node indices that are powers of two are on the left of the binomial tree. Example: For a full tree of Depth = 1, nodes = {1, 2, 3}.";


GraphTreeTwo[nodes_] :=

Module[{treeLine, evenNodes, i},
    
    (******************************************************************)
    (*  The construction of the tree starts from the leaves and works *)
    (*  down to the root. In this way, all one needs to do is to      *)
    (*  identify only the even numbered nodes.                        *)
    (******************************************************************)


	(* identification of even nodes ----------------------------------*)
	treeLine = {AbsoluteThickness[0.5]};
	evenNodes = Select[nodes, EvenQ];
	i = Length[evenNodes];
	
	
	(* iteration of even nodes ---------------------------------------*)
	While[i > 0, 
 	     treeLine = Append[treeLine,
 	     LineElementTwo[evenNodes[[i]] ]]; i--;];
 	     
 	Return[Graphics[treeLine]];
 	     
 ]



(*====================================================================*)

LineElementTwo::usage=
"LineElementTwo[nodeElement] LineElement does the line primitives for the smallest possible subtree with Depth > 1.";


LineElementTwo[nodeElement_] :=

Module[{linePair, pointOne, pointTwo, pointThree, radius, theta},


    (* ****************************************************************)
    (* MACROs --------------------------------------------------------*)
    
    
    (* This macro computes for possible angles at a particular depth  *)
    
    Phi[D_, n_] :=  N[Mod[(90 + (360 / 2^D) + (n (360 / 2^(D-1)))),360] 						Degree];
 
    
    (* This macro computes the coordinates based on phi and depth     *)
    
    RingElement[theta_] := {N[Cos[theta]], N[Sin[theta]]};    
    
    
    (* END MACROs ----------------------------------------------------*)
    (* ****************************************************************)
    
    
    
    (* calculation for leftmost point --------------------------------*)
    radius = Ceiling[Log[2, nodeElement+1]] - 1;
	theta  = Phi[radius+1, nodeElement];
	pointTwo = radius RingElement[theta];
	
	
	(* calculation for rightmost point -------------------------------*)
	theta  = Phi[radius+1, nodeElement+1];
	pointThree = radius RingElement[theta];	


    (* calculation for apex point ------------------------------------*)
    radius = radius - 1;
	theta  = Phi[radius+1, nodeElement/2];
    pointOne = radius RingElement[theta];

	
	(* making lines --------------------------------------------------*)
	linePair = {Line[{pointOne, pointTwo}],
                Line[{pointOne, pointThree}]};

 	     
 	Return[linePair];
 	     
]

GraphTreeNodesTwo[ nodes] -> graphics plot

GraphTreeNodesTwo::usage=
"GraphTreeNodesTwo[nodes] generates a graphic of just the nodes for a binomial tree. Note that nodes refers to a set of node indices, where 1 denotes the root of the binomial tree. The indexing convention is starting from the root at the top to the leaves on the bottom. All node indices that are powers of two are on the left of the binomial tree. Example: For a full tree of Depth = 1, nodes = {1, 2, 3}.";


GraphTreeNodesTwo[locations_] :=

Module[{treeNodes},    
    
	treeNodes = {PointSize[0.01],
	             Thread[Point[locations]]};

 	Return[Graphics[treeNodes]];
 	     
]

BinomialLattice[depth ] -> lattice

BinomialLattice::usage=
"BinomialLattice[depth] returns a circular lattice of (x,y)  coordinates, which are used to plot binomial trees. Note: computation of these points can be fairly time consuming beyond depth = 17. The smallest possible depth for a non-Null lattice is 1.";

BinomialLattice[depth_] :=

Module[{d},

(**********************************************************************)
(*  phi[] computes angle of lattice point to the x-axis. Note that    *)
(*  the starting angle is always the first angle from the y-axis.     *)                                              
(**********************************************************************)
	
	phi[D_, n_] := N[Mod[(90+(360/ 2^D) + (n (360/ 2^(D-1)))),360] 
	Degree];
	
	
(**********************************************************************)
(*  RingElement[] transforms the lattice point angle to a x,y         *)
(*  coordinate on the unit circle.                                    *)
(**********************************************************************)

	RingElement[theta_] := {N[Cos[theta]], N[Sin[theta]]};


(**********************************************************************)
(* Ring[] computes the lattice points for a particular depth          *)
(**********************************************************************)
	
    Ring[D_] := 
      Thread[(D - 1) *   
      RingElement[First[Array[phi,{1, 2^(D-1)}, {D, 0}]]]];
      
    
(**********************************************************************)
(* The following creates the lattice                                  *)
(**********************************************************************)

	lattice = {{0,0}};
    Do[lattice = 
       Partition[Flatten[Append[lattice, Ring[d]]],2], 
       {d, 2, depth}];
       
       
    
    Return[lattice];
    
]

GraphTreeNodes[ nodes, lattice] -> graphics plot

GraphTreeNodes::usage=
"GraphTreeNodes[nodes, lattice] generates a graphic of just the nodes for a binomial tree. Note that nodes refers to a set of node indices, where 1 denotes the root of the binomial tree. The indexing convention is starting from the root at the top to the leaves on the bottom. All node indices that are powers of two are on the left of the binomial tree. Example: For a full tree of Depth = 1, nodes = {1, 2, 3}. Assume that lattice is one that is generated from BinomialLattice[], although any lattice with the same indexing scheme can be used.";


GraphTreeNodes[nodes_, lattice_] :=

Module[{treeNodes},    

    (* error checking ------------------------------------------------*)
    If[Max[nodes] > Length[lattice],
       Print["PlotTree Error: Lattice is too small to show all nodes.
             Try using a larger lattice (i.e., use BinomialLattice with 
             a larger value of Depth."];
   
       Return[];

      ];    
    
	
	(* generation of graphics ----------------------------------------*)
	treeNodes = {PointSize[0.01],
	             Thread[Point[lattice[[nodes]]]]};

 	Return[Graphics[treeNodes]];
 	     
]

IdentifyLeafs[ nodes] -> leaf nodes only

IdentifyLeafs::usage=
"IdentifyLeafs[nodes] returns leaf nodes that exist in nodes.";


IdentifyLeafs[nodes_] :=

Module[{maxDepth, depth, leafs, leafsTmp, evenLeafs,
        innerNodes,remainingNodes},
   
    (* This algorithm searches for leafs by depth --------------------*)
	maxDepth = Ceiling[Log[2, Max[nodes]+1]];


	(* check for single-node tree ------------------------------------*)
	If[maxDepth == 1, Return[nodes]];
	

	(* calculations --------------------------------------------------*)
	leafs = Select[nodes, #1 >= 2^(maxDepth-1)&];
	

	(* check for unwed leafs -----------------------------------------*)
	If[ Not[EvenQ[Length[leafs]]],
		    Print["IdentifyLeaf Warning: The tree has an odd number of 							nodes at depth = ",maxDepth];
	  ];
	
	
	(* calculations continued ----------------------------------------*)
	evenLeafs = Select[leafs, EvenQ];
	innerNodes = evenLeafs/2;
	remainingNodes = Complement[nodes, leafs];
	
	If[maxDepth == 2, Return[leafs]];


	(* iteration for trees of depth greater than two -----------------*)	
	For[depth=maxDepth-1, depth > 1, depth--,

        (**************************************************************)
	    (*  note that the ordering is somewhat different from the     *)
	    (*  case depth = 2                                            *)
	    (**************************************************************)
	
	
		leafsTmp = Select[remainingNodes, #1 >= 2^(depth-1)&];


		(* check for null layers -------------------------------------*)
		If[leafsTmp == {},
		   Print["IdentifyLeaf Warning: The tree has a null layer at
		   depth = ",depth];
		  ];
		
		
		(* check for unwed nodes -------------------------------------*)
		If[ Not[EvenQ[Length[leafsTmp]]],
		    Print["IdentifyLeaf Warning: The tree has an odd number of 							nodes at depth = ",depth];
		  ];
	
	
		(* calculations ----------------------------------------------*)
		evenLeafs = Select[leafsTmp, EvenQ];		
		remainingNodes = Complement[remainingNodes, leafsTmp];
		leafsTmp = Complement[leafsTmp,innerNodes];
		leafs = Union[leafs, leafsTmp];
		
		
		innerNodes = evenLeafs/2;
	
	   ];


	Return[leafs];	
 	     
]

NodesToRGTform[ nodes] -> nodesRGT

NodesToRGTform::usage=
"NodesToRGTform[nodes] returns the list of nodes in a format that RandomGrowTree[] can use.The format is basically in a two element list, where the first element is a list of internal nodes, while the second element is a list of leafs. Note that nodes are assumed to be ordered from lowest to highest, starting from 1.";


NodesToRGTform[nodes_] :=

Module[{leafs, internalNodes, rgtFormattedNodes},
	leafs = IdentifyLeafs[nodes];
	internalNodes = Complement[nodes, leafs];
	rgtFormattedNodes = {internalNodes, leafs};
	Return[rgtFormattedNodes];     
]

RGTtoNodesForm[nodesRGT ] -> nodes

RGTtoNodesForm::usage=
"RGTtoNodesForm[nodesRGT] returns the list of nodes in a format that PlotTree[] can use.";


RGTtoNodesForm[nodesRGT_] := Sort[Flatten[nodesRGT]]

Routine for generating node summaries for a population (SummarizePopulation)

This routine reads in the .nod files from Hilss and prepares them for use with GrayscaleTrees. Note that each nod file corresponds to one tree.