Free cookie consent management tool by TermsFeed Policy Generator

Changeset 324 for trunk


Ignore:
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:
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Functions/BakedFunctionTree.cs

    r323 r324  
    132132    }
    133133
     134    public int Size {
     135      get {
     136        if(treesExpanded) {
     137          int size = 1;
     138          foreach(BakedFunctionTree tree in subTrees) {
     139            size += tree.Size;
     140          }
     141          return size;
     142        } else
     143        return linearRepresentation.Count;
     144      }
     145    }
     146
     147    public int Height {
     148      get {
     149        if(treesExpanded) {
     150          int height = 0;
     151          foreach(IFunctionTree subTree in subTrees) {
     152            int curHeight = subTree.Height;
     153            if(curHeight > height) height = curHeight;
     154          }
     155          return height+1;
     156        } else {
     157          int nextBranchStart;
     158          return BranchHeight(0, out nextBranchStart);
     159        }
     160      }
     161    }
     162
     163    private int BranchHeight(int branchStart, out int nextBranchStart) {
     164      LightWeightFunction f = linearRepresentation[branchStart];
     165      int height = 0;
     166      branchStart++;
     167      for(int i = 0; i < f.arity; i++) {
     168        int curHeight = BranchHeight(branchStart, out nextBranchStart);
     169        if(curHeight > height) height = curHeight;
     170        branchStart = nextBranchStart;
     171      }
     172      nextBranchStart = branchStart;
     173      return height + 1;
     174    }
     175
    134176    public IList<IFunctionTree> SubTrees {
    135177      get {
     
    142184            int length = BranchLength(branchIndex);
    143185            for(int j = branchIndex; j < branchIndex + length; j++) {
    144               subTree.linearRepresentation.Add(linearRepresentation[j].Clone());
     186              subTree.linearRepresentation.Add(linearRepresentation[j]);
    145187            }
    146188            branchIndex += length;
  • trunk/sources/HeuristicLab.Functions/IFunctionTree.cs

    r155 r324  
    2828namespace HeuristicLab.Functions {
    2929  public interface IFunctionTree : IItem {
     30    int Size { get; }
     31    int Height { get; }
    3032    IList<IFunctionTree> SubTrees { get; }
    3133    ICollection<IVariable> LocalVariables { get; }
  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs

    r238 r324  
    9696        // calculate the height and size difference and
    9797        // check if the size of the new tree is still in the allowed bounds
    98         int oldChildSize = gardener.GetTreeSize(selectedChild);
    99         int oldChildHeight = gardener.GetTreeSize(selectedChild);
    100         int newChildSize = gardener.GetTreeSize(newFunctionTree);
    101         int newChildHeight = gardener.GetTreeHeight(newFunctionTree);
     98        int oldChildSize = selectedChild.Size;
     99        int oldChildHeight = selectedChild.Height;
     100        int newChildSize = newFunctionTree.Size;
     101        int newChildHeight = newFunctionTree.Height;
    102102        if((treeHeight.Data - oldChildHeight) + newChildHeight > maxTreeHeight ||
    103103          (treeSize.Data - oldChildSize) + newChildSize > maxTreeSize) {
     
    118118        // update size and height
    119119        treeSize.Data = (treeSize.Data - oldChildSize) + newChildSize;
    120         treeHeight.Data = gardener.GetTreeHeight(root); // must recalculate height because we can't know wether the manipulated branch was the deepest branch
     120        treeHeight.Data = root.Height; // must recalculate height because we can't know wether the manipulated branch was the deepest branch
    121121        // check if whole tree is ok
    122122        Debug.Assert(gardener.IsValidTree(root));
  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs

    r238 r324  
    7474        if (root.SubTrees.Count > 0) {
    7575          root = root.SubTrees[random.Next(root.SubTrees.Count)];
    76           GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    77           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     76          GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     77          GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    7878          // update the variable
    7979          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
     
    8585          IFunctionTree newTree;
    8686          newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1);
    87           GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    88           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
     87          GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
     88          GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
    8989          // update the variable
    9090          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
     
    107107        Debug.Assert(gardener.IsValidTree(root));
    108108        // update the size and height of our tree
    109         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    110         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     109        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     110        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    111111        // don't need to schedule initialization operations
    112112        return null;
     
    118118        parent.RemoveSubTree(childIndex);
    119119        // then determine the number of nodes left over after the child has been removed!
    120         int remainingNodes = gardener.GetTreeSize(root);
     120        int remainingNodes = root.Size;
    121121        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
    122122        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel);
    123123        parent.InsertSubTree(childIndex, newFunctionTree);
    124         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    125         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     124        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     125        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    126126        Debug.Assert(gardener.IsValidTree(root));
    127127        // schedule an initialization operation for the new function-tree
  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs

    r238 r324  
    6464        Debug.Assert(gardener.IsValidTree(newTree));
    6565        // update sizes to match the new tree
    66         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    67         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
     66        GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
     67        GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
    6868        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
    6969
     
    8686
    8787        Debug.Assert(gardener.IsValidTree(root));
    88         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    89         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     88        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     89        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    9090        // root hasn't changed so don't need to update 'FunctionTree' variable
    9191        return null;
     
    9797        parent.InsertSubTree(childIndex, newFunctionTree);
    9898        Debug.Assert(gardener.IsValidTree(root));
    99         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    100         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     99        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     100        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    101101        // again the root hasn't changed so we don't need to update the 'FunctionTree' variable
    102102        // but we have to return an initialization operation for the newly created tree
  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs

    r238 r324  
    6565
    6666        // update the variables in the scope with the new values
    67         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    68         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
     67        GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
     68        GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
    6969        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
    7070       
     
    8686        int parentLevel = gardener.GetBranchLevel(root, parent);
    8787        int maxSubTreeHeight = maxTreeHeight - parentLevel;
    88         int maxSubTreeSize = maxTreeSize - (treeSize - gardener.GetTreeSize(parent.SubTrees[childIndex]));
     88        int maxSubTreeSize = maxTreeSize - (treeSize - parent.SubTrees[childIndex].Size);
    8989
    9090        // create a random function tree
     
    9595        Debug.Assert(gardener.IsValidTree(root));
    9696        // update the values of treeSize and treeHeight
    97         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    98         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     97        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
     98        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
    9999        // the root hasn't changed so we don't need to update
    100100        // return a CompositeOperation that randomly initializes all nodes of the new subtree
  • trunk/sources/HeuristicLab.StructureIdentification/ProbabilisticTreeCreator.cs

    r286 r324  
    5858      IFunctionTree root = gardener.PTC2(random, treeSize, maxTreeHeight);
    5959
    60       int actualTreeSize = gardener.GetTreeSize(root);
    61       int actualTreeHeight = gardener.GetTreeHeight(root);
     60      int actualTreeSize = root.Size;
     61      int actualTreeHeight = root.Height;
    6262
    6363      scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), root));
  • trunk/sources/HeuristicLab.StructureIdentification/RampedTreeCreator.cs

    r286 r324  
    6363      }
    6464
    65       int actualTreeSize = gardener.GetTreeSize(root);
    66       int actualTreeHeight = gardener.GetTreeHeight(root);
     65      int actualTreeSize = root.Size;
     66      int actualTreeHeight = root.Height;
    6767
    6868      scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), root));
  • trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs

    r238 r324  
    8989
    9090
    91       int newTreeSize = gardener.GetTreeSize(newTree);
    92       int newTreeHeight = gardener.GetTreeHeight(newTree);
     91      int newTreeSize = newTree.Size;
     92      int newTreeHeight = newTree.Height;
    9393      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
    9494      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
     
    133133
    134134        // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
    135         tree1Size = gardener.GetTreeSize(tree1);
    136         tree1Height = gardener.GetTreeHeight(tree1);
     135        tree1Size = tree1.Size;
     136        tree1Height = tree1.Height;
    137137
    138138        List<int> possibleChildIndices = new List<int>();
     
    143143        // find the list of allowed indices (regarding allowed sub-trees, maxTreeSize and maxTreeHeight)
    144144        for(int i = 0; i < tree0.SubTrees.Count; i++) {
    145           int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
     145          int subTreeSize = tree0.SubTrees[i].Size;
    146146
    147147          // the index is ok when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
     
    170170            // go down in node2:
    171171            tree1 = tree1.SubTrees[random.Next(tree1.SubTrees.Count)];
    172             tree1Size = gardener.GetTreeSize(tree1);
    173             tree1Height = gardener.GetTreeHeight(tree1);
     172            tree1Size = tree1.Size;
     173            tree1Height = tree1.Height;
    174174          } else {
    175175            // could neither go up or down ... don't know what to do ... give up
     
    180180          possibleChildIndices.Clear();
    181181          for(int i = 0; i < tree0.SubTrees.Count; i++) {
    182             int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
     182            int subTreeSize = tree0.SubTrees[i].Size;
    183183
    184184            // when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
  • trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

    r289 r324  
    241241
    242242    #region tree information gathering
    243     internal int GetTreeSize(IFunctionTree tree) {
    244       return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
    245     }
    246 
    247     internal int GetTreeHeight(IFunctionTree tree) {
    248       if(tree.SubTrees.Count == 0) return 1;
    249       return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
    250     }
     243    //internal int GetTreeSize(IFunctionTree tree) {
     244    //  return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
     245    //}
     246
     247    //internal int GetTreeHeight(IFunctionTree tree) {
     248    //  if(tree.SubTrees.Count == 0) return 1;
     249    //  return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
     250    //}
    251251
    252252    internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {
Note: See TracChangeset for help on using the changeset viewer.