Changeset 324

Timestamp:

06/18/08 16:20:26 (16 years ago)

Author:

gkronber

Message:

added Size and Height properties to interface IFunctionTree and removed the helper methods from TreeGardener (specific implementations of size and height properties in classes implementing IFunctionTree can be more efficient than the general functions in TreeGardener)

Location:

trunk/sources

Files:

• HeuristicLab.Functions/BakedFunctionTree.cs (modified) (2 diffs)
• HeuristicLab.Functions/IFunctionTree.cs (modified) (1 diff)
• HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs (modified) (2 diffs)
• HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs (modified) (4 diffs)
• HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs (modified) (3 diffs)
• HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs (modified) (3 diffs)
• HeuristicLab.StructureIdentification/ProbabilisticTreeCreator.cs (modified) (1 diff)
• HeuristicLab.StructureIdentification/RampedTreeCreator.cs (modified) (1 diff)
• HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs (modified) (5 diffs)
• HeuristicLab.StructureIdentification/TreeGardener.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Functions/BakedFunctionTree.cs

@@ -132 +132 @@
     }
 
+    public int Size {
+      get {
+        if(treesExpanded) {
+          int size = 1;
+          foreach(BakedFunctionTree tree in subTrees) {
+            size += tree.Size;
+          }
+          return size;
+        } else 
+        return linearRepresentation.Count;
+      }
+    }
+
+    public int Height {
+      get {
+        if(treesExpanded) {
+          int height = 0;
+          foreach(IFunctionTree subTree in subTrees) {
+            int curHeight = subTree.Height;
+            if(curHeight > height) height = curHeight;
+          }
+          return height+1;
+        } else {
+          int nextBranchStart;
+          return BranchHeight(0, out nextBranchStart);
+        }
+      }
+    }
+
+    private int BranchHeight(int branchStart, out int nextBranchStart) {
+      LightWeightFunction f = linearRepresentation[branchStart];
+      int height = 0;
+      branchStart++;
+      for(int i = 0; i < f.arity; i++) {
+        int curHeight = BranchHeight(branchStart, out nextBranchStart);
+        if(curHeight > height) height = curHeight;
+        branchStart = nextBranchStart;
+      }
+      nextBranchStart = branchStart;
+      return height + 1;
+    }
+
     public IList<IFunctionTree> SubTrees {
       get {
@@ -142 +184 @@
             int length = BranchLength(branchIndex);
             for(int j = branchIndex; j < branchIndex + length; j++) {
-              subTree.linearRepresentation.Add(linearRepresentation[j].Clone());
+              subTree.linearRepresentation.Add(linearRepresentation[j]);
             }
             branchIndex += length;

trunk/sources/HeuristicLab.Functions/IFunctionTree.cs

@@ -28 +28 @@
 namespace HeuristicLab.Functions {
   public interface IFunctionTree : IItem {
+    int Size { get; }
+    int Height { get; }
     IList<IFunctionTree> SubTrees { get; }
     ICollection<IVariable> LocalVariables { get; }

trunk/sources/HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs

@@ -96 +96 @@
         // calculate the height and size difference and 
         // check if the size of the new tree is still in the allowed bounds
-        int oldChildSize = gardener.GetTreeSize(selectedChild);
-        int oldChildHeight = gardener.GetTreeSize(selectedChild);
-        int newChildSize = gardener.GetTreeSize(newFunctionTree);
-        int newChildHeight = gardener.GetTreeHeight(newFunctionTree);
+        int oldChildSize = selectedChild.Size;
+        int oldChildHeight = selectedChild.Height;
+        int newChildSize = newFunctionTree.Size;
+        int newChildHeight = newFunctionTree.Height;
         if((treeHeight.Data - oldChildHeight) + newChildHeight > maxTreeHeight ||
           (treeSize.Data - oldChildSize) + newChildSize > maxTreeSize) {
@@ -118 +118 @@
         // update size and height
         treeSize.Data = (treeSize.Data - oldChildSize) + newChildSize;
-        treeHeight.Data = gardener.GetTreeHeight(root); // must recalculate height because we can't know wether the manipulated branch was the deepest branch
+        treeHeight.Data = root.Height; // must recalculate height because we can't know wether the manipulated branch was the deepest branch
         // check if whole tree is ok
         Debug.Assert(gardener.IsValidTree(root));

trunk/sources/HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs

@@ -74 +74 @@
         if (root.SubTrees.Count > 0) {
           root = root.SubTrees[random.Next(root.SubTrees.Count)];
-          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+          GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+          GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
           // update the variable
           scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
@@ -85 +85 @@
           IFunctionTree newTree;
           newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1);
-          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
-          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
+          GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
+          GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
           // update the variable
           scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
@@ -107 +107 @@
         Debug.Assert(gardener.IsValidTree(root));
         // update the size and height of our tree
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
         // don't need to schedule initialization operations
         return null;
@@ -118 +118 @@
         parent.RemoveSubTree(childIndex);
         // then determine the number of nodes left over after the child has been removed!
-        int remainingNodes = gardener.GetTreeSize(root);
+        int remainingNodes = root.Size;
         allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
         IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel);
         parent.InsertSubTree(childIndex, newFunctionTree);
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
         Debug.Assert(gardener.IsValidTree(root));
         // schedule an initialization operation for the new function-tree

trunk/sources/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs

@@ -64 +64 @@
         Debug.Assert(gardener.IsValidTree(newTree));
         // update sizes to match the new tree
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
         scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
 
@@ -86 +86 @@
 
         Debug.Assert(gardener.IsValidTree(root));
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
         // root hasn't changed so don't need to update 'FunctionTree' variable
         return null;
@@ -97 +97 @@
         parent.InsertSubTree(childIndex, newFunctionTree);
         Debug.Assert(gardener.IsValidTree(root));
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
         // again the root hasn't changed so we don't need to update the 'FunctionTree' variable
         // but we have to return an initialization operation for the newly created tree

trunk/sources/HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs

@@ -65 +65 @@
 
         // update the variables in the scope with the new values
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
         scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
         
@@ -86 +86 @@
         int parentLevel = gardener.GetBranchLevel(root, parent);
         int maxSubTreeHeight = maxTreeHeight - parentLevel;
-        int maxSubTreeSize = maxTreeSize - (treeSize - gardener.GetTreeSize(parent.SubTrees[childIndex]));
+        int maxSubTreeSize = maxTreeSize - (treeSize - parent.SubTrees[childIndex].Size);
 
         // create a random function tree
@@ -95 +95 @@
         Debug.Assert(gardener.IsValidTree(root));
         // update the values of treeSize and treeHeight
-        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
-        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
+        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
+        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
         // the root hasn't changed so we don't need to update 
         // return a CompositeOperation that randomly initializes all nodes of the new subtree

trunk/sources/HeuristicLab.StructureIdentification/ProbabilisticTreeCreator.cs

@@ -58 +58 @@
       IFunctionTree root = gardener.PTC2(random, treeSize, maxTreeHeight);
 
-      int actualTreeSize = gardener.GetTreeSize(root);
-      int actualTreeHeight = gardener.GetTreeHeight(root);
+      int actualTreeSize = root.Size;
+      int actualTreeHeight = root.Height;
 
       scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), root));

trunk/sources/HeuristicLab.StructureIdentification/RampedTreeCreator.cs

@@ -63 +63 @@
       }
 
-      int actualTreeSize = gardener.GetTreeSize(root);
-      int actualTreeHeight = gardener.GetTreeHeight(root);
+      int actualTreeSize = root.Size;
+      int actualTreeHeight = root.Height;
 
       scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), root));

trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs

@@ -89 +89 @@
 
 
-      int newTreeSize = gardener.GetTreeSize(newTree);
-      int newTreeHeight = gardener.GetTreeHeight(newTree);
+      int newTreeSize = newTree.Size;
+      int newTreeHeight = newTree.Height;
       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
@@ -133 +133 @@
 
         // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
-        tree1Size = gardener.GetTreeSize(tree1);
-        tree1Height = gardener.GetTreeHeight(tree1);
+        tree1Size = tree1.Size;
+        tree1Height = tree1.Height;
 
         List<int> possibleChildIndices = new List<int>();
@@ -143 +143 @@
         // find the list of allowed indices (regarding allowed sub-trees, maxTreeSize and maxTreeHeight)
         for(int i = 0; i < tree0.SubTrees.Count; i++) {
-          int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
+          int subTreeSize = tree0.SubTrees[i].Size;
 
           // the index is ok when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
@@ -170 +170 @@
             // go down in node2:
             tree1 = tree1.SubTrees[random.Next(tree1.SubTrees.Count)];
-            tree1Size = gardener.GetTreeSize(tree1);
-            tree1Height = gardener.GetTreeHeight(tree1);
+            tree1Size = tree1.Size;
+            tree1Height = tree1.Height;
           } else {
             // could neither go up or down ... don't know what to do ... give up
@@ -180 +180 @@
           possibleChildIndices.Clear();
           for(int i = 0; i < tree0.SubTrees.Count; i++) {
-            int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
+            int subTreeSize = tree0.SubTrees[i].Size;
 
             // when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -241 +241 @@
 
     #region tree information gathering
-    internal int GetTreeSize(IFunctionTree tree) {
-      return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
-    }
-
-    internal int GetTreeHeight(IFunctionTree tree) {
-      if(tree.SubTrees.Count == 0) return 1;
-      return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
-    }
+    //internal int GetTreeSize(IFunctionTree tree) {
+    //  return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
+    //}
+
+    //internal int GetTreeHeight(IFunctionTree tree) {
+    //  if(tree.SubTrees.Count == 0) return 1;
+    //  return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
+    //}
 
     internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {