Changeset 179 for trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

Timestamp:

04/24/08 14:10:03 (16 years ago)

Author:

gkronber

Message:

minor refactoring in TreeGardener and related classes

File:

• trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs (modified) (20 diffs)

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -39 +39 @@
     private GPOperatorLibrary funLibrary;
     private List<IFunction> functions;
+
     private List<IFunction> terminals;
-
     internal IList<IFunction> Terminals {
-      get { return terminals.AsReadOnly(); }
-    }
+      get { return terminals; }
+    }
+
     private List<IFunction> allFunctions;
-
     internal IList<IFunction> AllFunctions {
-      get { return allFunctions.AsReadOnly(); }
+      get { return allFunctions; }
     }
 
@@ -57 +57 @@
       functions = new List<IFunction>();
       // init functions and terminals based on constraints
-      foreach (IFunction fun in funLibrary.Group.Operators) {
+      foreach(IFunction fun in funLibrary.Group.Operators) {
         int maxA, minA;
         GetMinMaxArity(fun, out minA, out maxA);
-        if (maxA == 0) {
+        if(maxA == 0) {
           terminals.Add(fun);
+          allFunctions.Add(fun);
         } else {
           functions.Add(fun);
-        }
-      }
-      allFunctions.AddRange(functions);
-      allFunctions.AddRange(terminals);
+          allFunctions.Add(fun);
+        }
+      }
     }
 
     #region random initialization
+    internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
+      if(maxTreeHeight == 1 || maxTreeSize == 1) {
+        IFunction selectedTerminal = terminals[random.Next(terminals.Count())];
+        return new FunctionTree(selectedTerminal);
+      } else {
+        IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
+          GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
+        IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
+        FunctionTree root = new FunctionTree(selectedFunction);
+        MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+        return root;
+      }
+    }
+
+    internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
+      IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
+        GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
+      IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
+      FunctionTree root = new FunctionTree(selectedFunction);
+      MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+      return root;
+    }
+
     internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
       // default is non-balanced trees
-      return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false); 
-    }
+      return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false);
+    }
+
     internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
 
       int minTreeHeight = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min();
-      if (minTreeHeight > maxTreeHeight)
+      if(minTreeHeight > maxTreeHeight)
         maxTreeHeight = minTreeHeight;
 
       int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
-      if (minTreeSize > maxTreeSize)
+      if(minTreeSize > maxTreeSize)
         maxTreeSize = minTreeSize;
 
@@ -95 +119 @@
     }
 
-    internal IFunctionTree CreateRandomTree(int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
-      if (balanceTrees) {
-        if (maxTreeHeight == 1 || maxTreeSize==1) {
-          IFunction selectedTerminal = terminals[random.Next(terminals.Count())];
-          return new FunctionTree(selectedTerminal);
-        } else {
-          IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
-            GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
-          IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
-          FunctionTree root = new FunctionTree(selectedFunction);
-          MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-          return root;
-        }
-
-      } else {
-        IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
-          GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
-        IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
-        FunctionTree root = new FunctionTree(selectedFunction);
-        MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-        return root;
-      }
-    }
-
     internal IFunctionTree CreateRandomTree(IFunction rootFunction, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
       IFunctionTree root = new FunctionTree(rootFunction);
-      if (balanceTrees) {
+      if(balanceTrees) {
         MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
       } else {
         MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
       }
-      if (GetTreeSize(root) > maxTreeSize ||
+      if(GetTreeSize(root) > maxTreeSize ||
          GetTreeHeight(root) > maxTreeHeight) {
         throw new InvalidProgramException();
@@ -133 +133 @@
     }
 
-
     private void MakeUnbalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
-      if (maxTreeHeight == 0 || maxTreeSize == 0) return;
+      if(maxTreeHeight == 0 || maxTreeSize == 0) return;
       int minArity;
       int maxArity;
       GetMinMaxArity(parent.Function, out minArity, out maxArity);
-      if (maxArity >= maxTreeSize) {
+      if(maxArity >= maxTreeSize) {
         maxArity = maxTreeSize;
       }
       int actualArity = random.Next(minArity, maxArity + 1);
-      if (actualArity > 0) {
+      if(actualArity > 0) {
         int maxSubTreeSize = maxTreeSize / actualArity;
-        for (int i = 0; i < actualArity; i++) {
+        for(int i = 0; i < actualArity; i++) {
           IFunction[] possibleFunctions = GetAllowedSubFunctions(parent.Function, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
             GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
@@ -159 +158 @@
     // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
     private void MakeBalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
-      if (maxTreeHeight == 0 || maxTreeSize == 0) return; // should never happen anyway
+      if(maxTreeHeight == 0 || maxTreeSize == 0) return; // should never happen anyway
       int minArity;
       int maxArity;
       GetMinMaxArity(parent.Function, out minArity, out maxArity);
-      if (maxArity >= maxTreeSize) {
+      if(maxArity >= maxTreeSize) {
         maxArity = maxTreeSize;
       }
       int actualArity = random.Next(minArity, maxArity + 1);
-      if (actualArity > 0) {
+      if(actualArity > 0) {
         int maxSubTreeSize = maxTreeSize / actualArity;
-        for (int i = 0; i < actualArity; i++) {
-          if (maxTreeHeight == 1 || maxSubTreeSize == 1) {
+        for(int i = 0; i < actualArity; i++) {
+          if(maxTreeHeight == 1 || maxSubTreeSize == 1) {
             IFunction[] possibleTerminals = GetAllowedSubFunctions(parent.Function, i).Where(
               f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
@@ -199 +198 @@
       var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
 
-      foreach (IFunctionTree tree in parametricTrees) {
+      foreach(IFunctionTree tree in parametricTrees) {
         // enqueue an initialization operation for each operator with local variables 
         IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
@@ -205 +204 @@
 
         // copy the local variables into a temporary scope used for initialization
-        foreach (IVariable variable in tree.LocalVariables) {
+        foreach(IVariable variable in tree.LocalVariables) {
           initScope.AddVariable(variable);
         }
@@ -214 +213 @@
 
       Scope backupScope = new Scope("backup");
-      foreach (Scope subScope in scope.SubScopes) {
+      foreach(Scope subScope in scope.SubScopes) {
         backupScope.AddSubScope(subScope);
       }
@@ -233 +232 @@
 
     internal int GetTreeHeight(IFunctionTree tree) {
-      if (tree.SubTrees.Count == 0) return 1;
+      if(tree.SubTrees.Count == 0) return 1;
       return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
     }
@@ -244 +243 @@
 
       TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
-        if (possibleParentNode.SubTrees.Count > 0) {
+        if(possibleParentNode.SubTrees.Count > 0) {
           parentNodes.Add(possibleParentNode);
         }
@@ -250 +249 @@
 
       return parentNodes[random.Next(parentNodes.Count)];
-    }
-
-    internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
-      if (f == null) {
-        return allFunctions;
-      } else {
-        ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
-        List<IFunction> result = new List<IFunction>();
-        foreach(IFunction function in (ItemList)slotList[index]) {
-          result.Add(function);
-        }
-        return result;
-      }
-    }
-    internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {
-      foreach (IConstraint constraint in f.Constraints) {
-        NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
-        if (theConstraint != null) {
-          minArity = theConstraint.MinOperators.Data;
-          maxArity = theConstraint.MaxOperators.Data;
-          return;
-        }
-      }
-      // the default arity is 2
-      minArity = 2;
-      maxArity = 2;
-    }
-    internal bool IsTerminal(IFunction f) {
-      int minArity;
-      int maxArity;
-      GetMinMaxArity(f, out minArity, out maxArity);
-      return minArity == 0 && maxArity == 0;
-    }
-
-    internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
-      List<IFunction> parents = new List<IFunction>();
-      foreach (IFunction function in functions) {
-        ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
-        if (allowedSubFunctions.Contains(child)) {
-          parents.Add(function);
-        }
-      }
-      return parents;
     }
 
@@ -317 +273 @@
     // 'tail-recursive' helper
     private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
-      if (branch == tree) return level;
-
-      foreach (IFunctionTree subTree in tree.SubTrees) {
+      if(branch == tree) return level;
+
+      foreach(IFunctionTree subTree in tree.SubTrees) {
         int result = GetBranchLevelHelper(subTree, branch, level + 1);
-        if (result != -1) return result;
+        if(result != -1) return result;
       }
 
@@ -332 +288 @@
           int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
           int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
-          if(tree.SubTrees.Count < min || tree.SubTrees.Count > max) 
+          if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
             return false;
         }
@@ -344 +300 @@
     // returns a random branch from the specified level in the tree
     internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
-      if (level == 0) return tree;
+      if(level == 0) return tree;
       List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
       return branches[random.Next(branches.Count)];
@@ -350 +306 @@
     #endregion
 
-    #region private utility methods
-
-    private int GetMinimalTreeHeight(IOperator op) {
-      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
-    }
-
-    private int GetMinimalTreeSize(IOperator op) {
-      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
-    }
-
-    private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
-      action(tree);
-      foreach (IFunctionTree subTree in tree.SubTrees) {
-        TreeForEach(subTree, action);
-      }
-    }
-
-    private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) {
-      if (level == 1) return new List<IFunctionTree>(tree.SubTrees);
-
-      List<IFunctionTree> branches = new List<IFunctionTree>();
-      foreach (IFunctionTree subTree in tree.SubTrees) {
-        branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
-      }
-      return branches;
-    }
-
-
-    #endregion
-
+    #region function information (arity, allowed childs and parents)
     internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
       List<IFunction> result = new List<IFunction>();
-      foreach (IFunction f in functions) {
-        if (IsPossibleParent(f, list)) {
+      foreach(IFunction f in functions) {
+        if(IsPossibleParent(f, list)) {
           result.Add(f);
         }
@@ -399 +326 @@
       // when the maxArity of this function is smaller than the list of operators that
       // should be included as sub-operators then it can't be a parent
-      if (maxArity < children.Count()) {
+      if(maxArity < children.Count()) {
         return false;
       }
@@ -412 +339 @@
       // allowed functions for this slot.
       // we only count those slots that can hold at least one of the children that we should combine
-      for (int slot = 0; slot < nSlots; slot++) {
+      for(int slot = 0; slot < nSlots; slot++) {
         HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
-        if (functionSet.Count() > 0) {
+        if(functionSet.Count() > 0) {
           slotSets.Add(functionSet);
         }
@@ -424 +351 @@
       // we can never combine all children as sub-trees of the function and thus the function
       // can't be a parent.
-      if (slotSets.Count() < children.Count()) {
+      if(slotSets.Count() < children.Count()) {
         return false;
       }
@@ -435 +362 @@
 
       int assignments = 0;
-      for (int i = 0; i < slotSets.Count() - 1; i++) {
-        if (slotSets[i].Count > 0) {
+      for(int i = 0; i < slotSets.Count() - 1; i++) {
+        if(slotSets[i].Count > 0) {
           IFunction selected = slotSets[i].ElementAt(0);
           assignments++;
-          for (int j = i + 1; j < slotSets.Count(); j++) {
+          for(int j = i + 1; j < slotSets.Count(); j++) {
             slotSets[j].Remove(selected);
           }
@@ -446 +373 @@
 
       // sanity check 
-      if (assignments > children.Count) throw new InvalidProgramException();
+      if(assignments > children.Count) throw new InvalidProgramException();
       return assignments == children.Count - 1;
     }
+    internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
+      List<IFunction> parents = new List<IFunction>();
+      foreach(IFunction function in functions) {
+        ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
+        if(allowedSubFunctions.Contains(child)) {
+          parents.Add(function);
+        }
+      }
+      return parents;
+    }
+    internal bool IsTerminal(IFunction f) {
+      int minArity;
+      int maxArity;
+      GetMinMaxArity(f, out minArity, out maxArity);
+      return minArity == 0 && maxArity == 0;
+    }
+    internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
+      if(f == null) {
+        return allFunctions;
+      } else {
+        ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
+        List<IFunction> result = new List<IFunction>();
+        foreach(IFunction function in (ItemList)slotList[index]) {
+          result.Add(function);
+        }
+        return result;
+      }
+    }
+    internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {
+      foreach(IConstraint constraint in f.Constraints) {
+        NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
+        if(theConstraint != null) {
+          minArity = theConstraint.MinOperators.Data;
+          maxArity = theConstraint.MaxOperators.Data;
+          return;
+        }
+      }
+      // the default arity is 2
+      minArity = 2;
+      maxArity = 2;
+    }
+    #endregion
+
+    #region private utility methods
+
+    private int GetMinimalTreeHeight(IOperator op) {
+      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
+    }
+
+    private int GetMinimalTreeSize(IOperator op) {
+      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
+    }
+
+    private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
+      action(tree);
+      foreach(IFunctionTree subTree in tree.SubTrees) {
+        TreeForEach(subTree, action);
+      }
+    }
+
+    private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) {
+      if(level == 1) return new List<IFunctionTree>(tree.SubTrees);
+
+      List<IFunctionTree> branches = new List<IFunctionTree>();
+      foreach(IFunctionTree subTree in tree.SubTrees) {
+        branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
+      }
+      return branches;
+    }
+
+
+    #endregion
+
   }
 }