Changeset 180

Timestamp:

04/24/08 14:29:31 (17 years ago)

Author:

gkronber

Message:

• minor refactoring of TreeGardener
• added descriptive comments for tree-creation methods

Location:

trunk/sources/HeuristicLab.StructureIdentification

Files:

• Manipulation/ChangeNodeTypeManipulation.cs (modified) (1 diff)
• TreeGardener.cs (modified) (4 diffs)

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

@@ -128 +128 @@
 
     private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
-      IList<IFunction> allowedChildren;
+      IList<IFunction> allowedTerminals;
       if (parent == null) {
-        allowedChildren = gardener.Terminals;
+        allowedTerminals = gardener.Terminals;
       } else {
-        allowedChildren = new List<IFunction>();
+        allowedTerminals = new List<IFunction>();
         var allAllowedChildren = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
         foreach(IFunction c in allAllowedChildren) {
-          if(gardener.IsTerminal(c)) allowedChildren.Add(c);
+          if(gardener.IsTerminal(c)) allowedTerminals.Add(c);
         }
       }
       // selecting from the terminals should always work since the current child was also a terminal
       // so in the worst case we will just create a new terminal of the same type again.
-      return gardener.CreateRandomTree(allowedChildren[random.Next(allowedChildren.Count)], 1, 1, false);
+      return gardener.CreateRandomTree(allowedTerminals, 1, 1);
     }
 

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -50 +50 @@
     }
 
+    #region constructors
     internal TreeGardener(IRandom random, GPOperatorLibrary funLibrary) {
       this.random = random;
@@ -69 +70 @@
       }
     }
+    #endregion
 
     #region random initialization
+    /// <summary>
+    /// Creates a random balanced tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
+    /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
+    /// </summary>
+    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
+    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
+    /// <returns></returns>
     internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
+      IFunctionTree root = CreateRandomRoot(maxTreeSize, maxTreeHeight);
+      MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+      return root;
+    }
+
+    /// <summary>
+    /// Creates a random (unbalanced) tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
+    /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
+    /// </summary>
+    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
+    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
+    /// <returns></returns>
+    internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
+      IFunctionTree root = CreateRandomRoot(maxTreeSize, maxTreeHeight);
+      MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+      return root;
+    }
+
+    /// <summary>
+    /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
+    /// </summary>
+    /// <param name="allowedFunctions">Set of allowed functions.</param>
+    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
+    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
+    /// <returns>New random unbalanced tree</returns>
+    internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
+      // default is non-balanced trees
+      return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false);
+    }
+
+    /// <summary>
+    /// selects a random function from allowedFunctions and creates a (un)balanced random tree with maximal size and height.
+    /// </summary>
+    /// <param name="allowedFunctions">Set of allowed functions.</param>
+    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
+    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
+    /// <param name="balanceTrees">Flag determining whether the tree should be balanced or not.</param>
+    /// <returns>New random tree</returns>
+    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)
+        maxTreeHeight = minTreeHeight;
+
+      int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
+      if(minTreeSize > maxTreeSize)
+        maxTreeSize = minTreeSize;
+
+      int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
+      int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
+
+      IFunction[] possibleFunctions = allowedFunctions.Where(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
+        ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
+      IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
+
+      IFunctionTree root = new FunctionTree(selectedFunction);
+      if(balanceTrees) {
+        MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+      } else {
+        MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+      }
+      return root;
+    }
+
+    internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
+      // needed for the parameter shaking operation
+      CompositeOperation initializationOperation = new CompositeOperation();
+      Scope tempScope = new Scope("Temp. initialization scope");
+
+      var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
+      foreach(IFunctionTree tree in parametricTrees) {
+        // enqueue an initialization operation for each operator with local variables 
+        IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
+        Scope initScope = new Scope();
+        // copy the local variables into a temporary scope used for initialization
+        foreach(IVariable variable in tree.LocalVariables) {
+          initScope.AddVariable(variable);
+        }
+        tempScope.AddSubScope(initScope);
+        initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
+      }
+      Scope backupScope = new Scope("backup");
+      foreach(Scope subScope in scope.SubScopes) {
+        backupScope.AddSubScope(subScope);
+      }
+      scope.AddSubScope(tempScope);
+      scope.AddSubScope(backupScope);
+      // add an operation to remove the temporary scopes        
+      initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
+      return initializationOperation;
+    }
+    #endregion
+
+    #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 IFunctionTree GetRandomParentNode(IFunctionTree tree) {
+      List<IFunctionTree> parentNodes = new List<IFunctionTree>();
+
+      // add null for the parent of the root node
+      parentNodes.Add(null);
+
+      TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
+        if(possibleParentNode.SubTrees.Count > 0) {
+          parentNodes.Add(possibleParentNode);
+        }
+      });
+
+      return parentNodes[random.Next(parentNodes.Count)];
+    }
+
+    internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
+      List<IFunctionTree> allTrees = new List<IFunctionTree>();
+      TreeForEach(root, t => { allTrees.Add(t); });
+      return allTrees;
+    }
+
+    /// <summary>
+    /// returns the height level of branch in the tree
+    /// if the branch == tree => 1
+    /// if branch is in the sub-trees of tree => 2
+    /// ...
+    /// if branch is not found => -1
+    /// </summary>
+    /// <param name="tree">root of the function tree to process</param>
+    /// <param name="branch">branch that is searched in the tree</param>
+    /// <returns></returns>
+    internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
+      return GetBranchLevelHelper(tree, branch, 1);
+    }
+
+    // 'tail-recursive' helper
+    private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
+      if(branch == tree) return level;
+
+      foreach(IFunctionTree subTree in tree.SubTrees) {
+        int result = GetBranchLevelHelper(subTree, branch, level + 1);
+        if(result != -1) return result;
+      }
+
+      return -1;
+    }
+
+    internal bool IsValidTree(IFunctionTree tree) {
+      foreach(IConstraint constraint in tree.Function.Constraints) {
+        if(constraint is NumberOfSubOperatorsConstraint) {
+          int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
+          int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
+          if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
+            return false;
+        }
+      }
+      foreach(IFunctionTree subTree in tree.SubTrees) {
+        if(!IsValidTree(subTree)) return false;
+      }
+      return true;
+    }
+
+    // returns a random branch from the specified level in the tree
+    internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
+      if(level == 0) return tree;
+      List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
+      return branches[random.Next(branches.Count)];
+    }
+    #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)) {
+          result.Add(f);
+        }
+      }
+      return result;
+    }
+
+    private bool IsPossibleParent(IFunction f, List<IFunction> children) {
+      int minArity;
+      int maxArity;
+      GetMinMaxArity(f, out minArity, out maxArity);
+
+      // note: we can't assume that the operators in the children list have different types!
+
+      // 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()) {
+        return false;
+      }
+      int nSlots = Math.Max(minArity, children.Count);
+
+      SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
+      analyzer.AllPossibleOperators = children.Cast<IOperator>().ToArray<IOperator>();
+
+      List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
+
+      // we iterate through all slots for sub-trees and calculate the set of 
+      // 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++) {
+        HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
+        if(functionSet.Count() > 0) {
+          slotSets.Add(functionSet);
+        }
+      }
+
+      // ok at the end of this operation we know how many slots of the parent can actually
+      // hold one of our children.
+      // if the number of slots is smaller than the number of children we can be sure that
+      // 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()) {
+        return false;
+      }
+
+      // finally we sort the sets by size and beginning from the first set select one
+      // function for the slot and thus remove it as possible sub-tree from the remaining sets.
+      // when we can successfully assign all available children to a slot the function is a valid parent
+      // when only a subset of all children can be assigned to slots the function is no valid parent
+      slotSets.Sort((p, q) => p.Count() - q.Count());
+
+      int assignments = 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++) {
+            slotSets[j].Remove(selected);
+          }
+        }
+      }
+
+      // sanity check 
+      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 IFunctionTree CreateRandomRoot(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 &&
+        IFunction[] possibleFunctions = allFunctions.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);
-    }
-
-    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)
-        maxTreeHeight = minTreeHeight;
-
-      int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
-      if(minTreeSize > maxTreeSize)
-        maxTreeSize = minTreeSize;
-
-      int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
-      int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
-
-      IFunction[] possibleFunctions = allowedFunctions.Where(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
-        ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
-      IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
-
-      return CreateRandomTree(selectedFunction, treeSize, treeHeight, balanceTrees);
-    }
-
-    internal IFunctionTree CreateRandomTree(IFunction rootFunction, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
-      IFunctionTree root = new FunctionTree(rootFunction);
-      if(balanceTrees) {
-        MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-      } else {
-        MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-      }
-      if(GetTreeSize(root) > maxTreeSize ||
-         GetTreeHeight(root) > maxTreeHeight) {
-        throw new InvalidProgramException();
-      }
-      return root;
+        return new FunctionTree(selectedFunction);
+      }
     }
 
@@ -158 +404 @@
     // 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;
       int minArity;
       int maxArity;
@@ -191 +437 @@
     }
 
-    internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
-      // needed for the parameter shaking operation
-      CompositeOperation initializationOperation = new CompositeOperation();
-      Scope tempScope = new Scope("Temp. initialization scope");
-
-      var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
-
-      foreach(IFunctionTree tree in parametricTrees) {
-        // enqueue an initialization operation for each operator with local variables 
-        IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
-        Scope initScope = new Scope();
-
-        // copy the local variables into a temporary scope used for initialization
-        foreach(IVariable variable in tree.LocalVariables) {
-          initScope.AddVariable(variable);
-        }
-
-        tempScope.AddSubScope(initScope);
-        initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
-      }
-
-      Scope backupScope = new Scope("backup");
-      foreach(Scope subScope in scope.SubScopes) {
-        backupScope.AddSubScope(subScope);
-      }
-
-      scope.AddSubScope(tempScope);
-      scope.AddSubScope(backupScope);
-
-      // add an operation to remove the temporary scopes        
-      initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
-      return initializationOperation;
-    }
-    #endregion
-
-    #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 IFunctionTree GetRandomParentNode(IFunctionTree tree) {
-      List<IFunctionTree> parentNodes = new List<IFunctionTree>();
-
-      // add null for the parent of the root node
-      parentNodes.Add(null);
-
-      TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
-        if(possibleParentNode.SubTrees.Count > 0) {
-          parentNodes.Add(possibleParentNode);
-        }
-      });
-
-      return parentNodes[random.Next(parentNodes.Count)];
-    }
-
-    internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
-      List<IFunctionTree> allTrees = new List<IFunctionTree>();
-      TreeForEach(root, t => { allTrees.Add(t); });
-      return allTrees;
-    }
-
-    /// <summary>
-    /// returns the height level of branch in the tree
-    /// if the branch == tree => 1
-    /// if branch is in the sub-trees of tree => 2
-    /// ...
-    /// if branch is not found => -1
-    /// </summary>
-    /// <param name="tree">root of the function tree to process</param>
-    /// <param name="branch">branch that is searched in the tree</param>
-    /// <returns></returns>
-    internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
-      return GetBranchLevelHelper(tree, branch, 1);
-    }
-
-    // 'tail-recursive' helper
-    private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
-      if(branch == tree) return level;
-
-      foreach(IFunctionTree subTree in tree.SubTrees) {
-        int result = GetBranchLevelHelper(subTree, branch, level + 1);
-        if(result != -1) return result;
-      }
-
-      return -1;
-    }
-
-    internal bool IsValidTree(IFunctionTree tree) {
-      foreach(IConstraint constraint in tree.Function.Constraints) {
-        if(constraint is NumberOfSubOperatorsConstraint) {
-          int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
-          int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
-          if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
-            return false;
-        }
-      }
-      foreach(IFunctionTree subTree in tree.SubTrees) {
-        if(!IsValidTree(subTree)) return false;
-      }
-      return true;
-    }
-
-    // returns a random branch from the specified level in the tree
-    internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
-      if(level == 0) return tree;
-      List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
-      return branches[random.Next(branches.Count)];
-    }
-    #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)) {
-          result.Add(f);
-        }
-      }
-      return result;
-    }
-
-    private bool IsPossibleParent(IFunction f, List<IFunction> children) {
-      int minArity;
-      int maxArity;
-      GetMinMaxArity(f, out minArity, out maxArity);
-
-      // note: we can't assume that the operators in the children list have different types!
-
-      // 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()) {
-        return false;
-      }
-      int nSlots = Math.Max(minArity, children.Count);
-
-      SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
-      analyzer.AllPossibleOperators = children.Cast<IOperator>().ToArray<IOperator>();
-
-      List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
-
-      // we iterate through all slots for sub-trees and calculate the set of 
-      // 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++) {
-        HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
-        if(functionSet.Count() > 0) {
-          slotSets.Add(functionSet);
-        }
-      }
-
-      // ok at the end of this operation we know how many slots of the parent can actually
-      // hold one of our children.
-      // if the number of slots is smaller than the number of children we can be sure that
-      // 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()) {
-        return false;
-      }
-
-      // finally we sort the sets by size and beginning from the first set select one
-      // function for the slot and thus remove it as possible sub-tree from the remaining sets.
-      // when we can successfully assign all available children to a slot the function is a valid parent
-      // when only a subset of all children can be assigned to slots the function is no valid parent
-      slotSets.Sort((p, q) => p.Count() - q.Count());
-
-      int assignments = 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++) {
-            slotSets[j].Remove(selected);
-          }
-        }
-      }
-
-      // sanity check 
-      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;