[2] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Text;
|
---|
| 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Constraints;
|
---|
| 27 | using System.Diagnostics;
|
---|
| 28 | using HeuristicLab.Data;
|
---|
| 29 | using System.Linq;
|
---|
| 30 | using HeuristicLab.Random;
|
---|
| 31 | using HeuristicLab.Operators;
|
---|
| 32 | using HeuristicLab.Selection;
|
---|
[155] | 33 | using HeuristicLab.Functions;
|
---|
| 34 | using System.Collections;
|
---|
[2] | 35 |
|
---|
| 36 | namespace HeuristicLab.StructureIdentification {
|
---|
| 37 | internal class TreeGardener {
|
---|
| 38 | private IRandom random;
|
---|
[155] | 39 | private GPOperatorLibrary funLibrary;
|
---|
| 40 | private List<IFunction> functions;
|
---|
| 41 | private List<IFunction> terminals;
|
---|
[2] | 42 |
|
---|
[155] | 43 | internal IList<IFunction> Terminals {
|
---|
[2] | 44 | get { return terminals.AsReadOnly(); }
|
---|
| 45 | }
|
---|
[155] | 46 | private List<IFunction> allFunctions;
|
---|
[2] | 47 |
|
---|
[155] | 48 | internal IList<IFunction> AllFunctions {
|
---|
| 49 | get { return allFunctions.AsReadOnly(); }
|
---|
[2] | 50 | }
|
---|
| 51 |
|
---|
[155] | 52 | internal TreeGardener(IRandom random, GPOperatorLibrary funLibrary) {
|
---|
[2] | 53 | this.random = random;
|
---|
[155] | 54 | this.funLibrary = funLibrary;
|
---|
| 55 | this.allFunctions = new List<IFunction>();
|
---|
| 56 | terminals = new List<IFunction>();
|
---|
| 57 | functions = new List<IFunction>();
|
---|
[2] | 58 | // init functions and terminals based on constraints
|
---|
[155] | 59 | foreach (IFunction fun in funLibrary.Group.Operators) {
|
---|
[2] | 60 | int maxA, minA;
|
---|
[155] | 61 | GetMinMaxArity(fun, out minA, out maxA);
|
---|
[2] | 62 | if (maxA == 0) {
|
---|
[155] | 63 | terminals.Add(fun);
|
---|
[2] | 64 | } else {
|
---|
[155] | 65 | functions.Add(fun);
|
---|
[2] | 66 | }
|
---|
| 67 | }
|
---|
[155] | 68 | allFunctions.AddRange(functions);
|
---|
| 69 | allFunctions.AddRange(terminals);
|
---|
[2] | 70 | }
|
---|
| 71 |
|
---|
| 72 | #region random initialization
|
---|
[163] | 73 | internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
|
---|
| 74 | // default is non-balanced trees
|
---|
| 75 | return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false);
|
---|
| 76 | }
|
---|
[155] | 77 | internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
|
---|
[2] | 78 |
|
---|
[155] | 79 | int minTreeHeight = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min();
|
---|
[2] | 80 | if (minTreeHeight > maxTreeHeight)
|
---|
| 81 | maxTreeHeight = minTreeHeight;
|
---|
| 82 |
|
---|
[155] | 83 | int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
|
---|
[2] | 84 | if (minTreeSize > maxTreeSize)
|
---|
| 85 | maxTreeSize = minTreeSize;
|
---|
| 86 |
|
---|
| 87 | int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
|
---|
| 88 | int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
|
---|
| 89 |
|
---|
[155] | 90 | IFunction[] possibleFunctions = allowedFunctions.Where(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
|
---|
| 91 | ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
|
---|
| 92 | IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
|
---|
[2] | 93 |
|
---|
[155] | 94 | return CreateRandomTree(selectedFunction, treeSize, treeHeight, balanceTrees);
|
---|
[2] | 95 | }
|
---|
| 96 |
|
---|
[155] | 97 | internal IFunctionTree CreateRandomTree(int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
|
---|
[2] | 98 | if (balanceTrees) {
|
---|
[23] | 99 | if (maxTreeHeight == 1 || maxTreeSize==1) {
|
---|
[155] | 100 | IFunction selectedTerminal = terminals[random.Next(terminals.Count())];
|
---|
| 101 | return new FunctionTree(selectedTerminal);
|
---|
[2] | 102 | } else {
|
---|
[155] | 103 | IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
[2] | 104 | GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
|
---|
[155] | 105 | IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
|
---|
| 106 | FunctionTree root = new FunctionTree(selectedFunction);
|
---|
| 107 | MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 108 | return root;
|
---|
[2] | 109 | }
|
---|
| 110 |
|
---|
| 111 | } else {
|
---|
[155] | 112 | IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
| 113 | GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
|
---|
| 114 | IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
|
---|
| 115 | FunctionTree root = new FunctionTree(selectedFunction);
|
---|
| 116 | MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 117 | return root;
|
---|
[2] | 118 | }
|
---|
| 119 | }
|
---|
| 120 |
|
---|
[155] | 121 | internal IFunctionTree CreateRandomTree(IFunction rootFunction, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
|
---|
| 122 | IFunctionTree root = new FunctionTree(rootFunction);
|
---|
[2] | 123 | if (balanceTrees) {
|
---|
| 124 | MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 125 | } else {
|
---|
| 126 | MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 127 | }
|
---|
| 128 | if (GetTreeSize(root) > maxTreeSize ||
|
---|
| 129 | GetTreeHeight(root) > maxTreeHeight) {
|
---|
| 130 | throw new InvalidProgramException();
|
---|
| 131 | }
|
---|
| 132 | return root;
|
---|
| 133 | }
|
---|
| 134 |
|
---|
| 135 |
|
---|
[155] | 136 | private void MakeUnbalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
|
---|
[2] | 137 | if (maxTreeHeight == 0 || maxTreeSize == 0) return;
|
---|
| 138 | int minArity;
|
---|
| 139 | int maxArity;
|
---|
[155] | 140 | GetMinMaxArity(parent.Function, out minArity, out maxArity);
|
---|
[2] | 141 | if (maxArity >= maxTreeSize) {
|
---|
| 142 | maxArity = maxTreeSize;
|
---|
| 143 | }
|
---|
| 144 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 145 | if (actualArity > 0) {
|
---|
| 146 | int maxSubTreeSize = maxTreeSize / actualArity;
|
---|
| 147 | for (int i = 0; i < actualArity; i++) {
|
---|
[155] | 148 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent.Function, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
| 149 | GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
|
---|
| 150 | IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
|
---|
| 151 | FunctionTree newSubTree = new FunctionTree(selectedFunction);
|
---|
| 152 | MakeUnbalancedTree(newSubTree, maxSubTreeSize - 1, maxTreeHeight - 1);
|
---|
| 153 | parent.InsertSubTree(i, newSubTree);
|
---|
[2] | 154 | }
|
---|
| 155 | }
|
---|
| 156 | }
|
---|
| 157 |
|
---|
| 158 | // NOTE: this method doesn't build fully balanced trees because we have constraints on the
|
---|
[155] | 159 | // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
|
---|
| 160 | private void MakeBalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
|
---|
[2] | 161 | if (maxTreeHeight == 0 || maxTreeSize == 0) return; // should never happen anyway
|
---|
| 162 | int minArity;
|
---|
| 163 | int maxArity;
|
---|
[155] | 164 | GetMinMaxArity(parent.Function, out minArity, out maxArity);
|
---|
[2] | 165 | if (maxArity >= maxTreeSize) {
|
---|
| 166 | maxArity = maxTreeSize;
|
---|
| 167 | }
|
---|
| 168 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 169 | if (actualArity > 0) {
|
---|
| 170 | int maxSubTreeSize = maxTreeSize / actualArity;
|
---|
| 171 | for (int i = 0; i < actualArity; i++) {
|
---|
| 172 | if (maxTreeHeight == 1 || maxSubTreeSize == 1) {
|
---|
[155] | 173 | IFunction[] possibleTerminals = GetAllowedSubFunctions(parent.Function, i).Where(
|
---|
| 174 | f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
| 175 | GetMinimalTreeSize(f) <= maxSubTreeSize &&
|
---|
| 176 | IsTerminal(f)).ToArray();
|
---|
| 177 | IFunction selectedTerminal = possibleTerminals[random.Next(possibleTerminals.Length)];
|
---|
| 178 | IFunctionTree newTree = new FunctionTree(selectedTerminal);
|
---|
| 179 | parent.InsertSubTree(i, newTree);
|
---|
[2] | 180 | } else {
|
---|
[155] | 181 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent.Function, i).Where(
|
---|
| 182 | f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
| 183 | GetMinimalTreeSize(f) <= maxSubTreeSize &&
|
---|
| 184 | !IsTerminal(f)).ToArray();
|
---|
| 185 | IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];
|
---|
| 186 | FunctionTree newTree = new FunctionTree(selectedFunction);
|
---|
| 187 | parent.InsertSubTree(i, newTree);
|
---|
| 188 | MakeBalancedTree(newTree, maxSubTreeSize - 1, maxTreeHeight - 1);
|
---|
[2] | 189 | }
|
---|
| 190 | }
|
---|
| 191 | }
|
---|
| 192 | }
|
---|
| 193 |
|
---|
[155] | 194 | internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
|
---|
[2] | 195 | // needed for the parameter shaking operation
|
---|
| 196 | CompositeOperation initializationOperation = new CompositeOperation();
|
---|
| 197 | Scope tempScope = new Scope("Temp. initialization scope");
|
---|
| 198 |
|
---|
[155] | 199 | var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
|
---|
[2] | 200 |
|
---|
[155] | 201 | foreach (IFunctionTree tree in parametricTrees) {
|
---|
[2] | 202 | // enqueue an initialization operation for each operator with local variables
|
---|
[155] | 203 | IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
|
---|
[2] | 204 | Scope initScope = new Scope();
|
---|
| 205 |
|
---|
| 206 | // copy the local variables into a temporary scope used for initialization
|
---|
[155] | 207 | foreach (IVariable variable in tree.LocalVariables) {
|
---|
| 208 | initScope.AddVariable(variable);
|
---|
[2] | 209 | }
|
---|
| 210 |
|
---|
| 211 | tempScope.AddSubScope(initScope);
|
---|
| 212 | initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
|
---|
| 213 | }
|
---|
| 214 |
|
---|
| 215 | Scope backupScope = new Scope("backup");
|
---|
| 216 | foreach (Scope subScope in scope.SubScopes) {
|
---|
| 217 | backupScope.AddSubScope(subScope);
|
---|
| 218 | }
|
---|
| 219 |
|
---|
| 220 | scope.AddSubScope(tempScope);
|
---|
| 221 | scope.AddSubScope(backupScope);
|
---|
| 222 |
|
---|
| 223 | // add an operation to remove the temporary scopes
|
---|
| 224 | initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
|
---|
| 225 | return initializationOperation;
|
---|
| 226 | }
|
---|
| 227 | #endregion
|
---|
| 228 |
|
---|
| 229 | #region tree information gathering
|
---|
[155] | 230 | internal int GetTreeSize(IFunctionTree tree) {
|
---|
| 231 | return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
|
---|
[2] | 232 | }
|
---|
| 233 |
|
---|
[155] | 234 | internal int GetTreeHeight(IFunctionTree tree) {
|
---|
| 235 | if (tree.SubTrees.Count == 0) return 1;
|
---|
| 236 | return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
|
---|
[2] | 237 | }
|
---|
| 238 |
|
---|
[155] | 239 | internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {
|
---|
| 240 | List<IFunctionTree> parentNodes = new List<IFunctionTree>();
|
---|
[2] | 241 |
|
---|
| 242 | // add null for the parent of the root node
|
---|
| 243 | parentNodes.Add(null);
|
---|
| 244 |
|
---|
[155] | 245 | TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
|
---|
| 246 | if (possibleParentNode.SubTrees.Count > 0) {
|
---|
| 247 | parentNodes.Add(possibleParentNode);
|
---|
[2] | 248 | }
|
---|
| 249 | });
|
---|
| 250 |
|
---|
| 251 | return parentNodes[random.Next(parentNodes.Count)];
|
---|
| 252 | }
|
---|
| 253 |
|
---|
[155] | 254 | internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
|
---|
| 255 | if (f == null) {
|
---|
| 256 | return allFunctions;
|
---|
[2] | 257 | } else {
|
---|
[155] | 258 | ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
|
---|
| 259 | List<IFunction> result = new List<IFunction>();
|
---|
| 260 | foreach(IFunction function in (ItemList)slotList[index]) {
|
---|
| 261 | result.Add(function);
|
---|
| 262 | }
|
---|
| 263 | return result;
|
---|
[2] | 264 | }
|
---|
| 265 | }
|
---|
[155] | 266 | internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {
|
---|
| 267 | foreach (IConstraint constraint in f.Constraints) {
|
---|
[2] | 268 | NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
|
---|
| 269 | if (theConstraint != null) {
|
---|
| 270 | minArity = theConstraint.MinOperators.Data;
|
---|
| 271 | maxArity = theConstraint.MaxOperators.Data;
|
---|
| 272 | return;
|
---|
| 273 | }
|
---|
| 274 | }
|
---|
| 275 | // the default arity is 2
|
---|
| 276 | minArity = 2;
|
---|
| 277 | maxArity = 2;
|
---|
| 278 | }
|
---|
[155] | 279 | internal bool IsTerminal(IFunction f) {
|
---|
[2] | 280 | int minArity;
|
---|
| 281 | int maxArity;
|
---|
| 282 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
| 283 | return minArity == 0 && maxArity == 0;
|
---|
| 284 | }
|
---|
| 285 |
|
---|
[155] | 286 | internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
|
---|
| 287 | List<IFunction> parents = new List<IFunction>();
|
---|
| 288 | foreach (IFunction function in functions) {
|
---|
| 289 | ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
|
---|
| 290 | if (allowedSubFunctions.Contains(child)) {
|
---|
[2] | 291 | parents.Add(function);
|
---|
| 292 | }
|
---|
| 293 | }
|
---|
| 294 | return parents;
|
---|
| 295 | }
|
---|
| 296 |
|
---|
[155] | 297 | internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
|
---|
| 298 | List<IFunctionTree> allTrees = new List<IFunctionTree>();
|
---|
| 299 | TreeForEach(root, t => { allTrees.Add(t); });
|
---|
| 300 | return allTrees;
|
---|
[2] | 301 | }
|
---|
| 302 |
|
---|
| 303 | /// <summary>
|
---|
[155] | 304 | /// returns the height level of branch in the tree
|
---|
| 305 | /// if the branch == tree => 1
|
---|
| 306 | /// if branch is in the sub-trees of tree => 2
|
---|
[2] | 307 | /// ...
|
---|
[155] | 308 | /// if branch is not found => -1
|
---|
[2] | 309 | /// </summary>
|
---|
[155] | 310 | /// <param name="tree">root of the function tree to process</param>
|
---|
| 311 | /// <param name="branch">branch that is searched in the tree</param>
|
---|
[2] | 312 | /// <returns></returns>
|
---|
[155] | 313 | internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
|
---|
| 314 | return GetBranchLevelHelper(tree, branch, 1);
|
---|
[2] | 315 | }
|
---|
| 316 |
|
---|
[155] | 317 | // 'tail-recursive' helper
|
---|
| 318 | private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
|
---|
| 319 | if (branch == tree) return level;
|
---|
[2] | 320 |
|
---|
[155] | 321 | foreach (IFunctionTree subTree in tree.SubTrees) {
|
---|
| 322 | int result = GetBranchLevelHelper(subTree, branch, level + 1);
|
---|
[2] | 323 | if (result != -1) return result;
|
---|
| 324 | }
|
---|
| 325 |
|
---|
| 326 | return -1;
|
---|
| 327 | }
|
---|
| 328 |
|
---|
[155] | 329 | internal bool IsValidTree(IFunctionTree tree) {
|
---|
| 330 | foreach(IConstraint constraint in tree.Function.Constraints) {
|
---|
| 331 | if(constraint is NumberOfSubOperatorsConstraint) {
|
---|
| 332 | int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
|
---|
| 333 | int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
|
---|
| 334 | if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
|
---|
| 335 | return false;
|
---|
| 336 | }
|
---|
[2] | 337 | }
|
---|
[155] | 338 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 339 | if(!IsValidTree(subTree)) return false;
|
---|
| 340 | }
|
---|
[2] | 341 | return true;
|
---|
| 342 | }
|
---|
| 343 |
|
---|
[155] | 344 | // returns a random branch from the specified level in the tree
|
---|
| 345 | internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
|
---|
[2] | 346 | if (level == 0) return tree;
|
---|
[155] | 347 | List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
|
---|
| 348 | return branches[random.Next(branches.Count)];
|
---|
[2] | 349 | }
|
---|
| 350 | #endregion
|
---|
| 351 |
|
---|
| 352 | #region private utility methods
|
---|
| 353 |
|
---|
| 354 | private int GetMinimalTreeHeight(IOperator op) {
|
---|
| 355 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
|
---|
| 356 | }
|
---|
| 357 |
|
---|
| 358 | private int GetMinimalTreeSize(IOperator op) {
|
---|
| 359 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
|
---|
| 360 | }
|
---|
| 361 |
|
---|
[155] | 362 | private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
|
---|
[2] | 363 | action(tree);
|
---|
[155] | 364 | foreach (IFunctionTree subTree in tree.SubTrees) {
|
---|
| 365 | TreeForEach(subTree, action);
|
---|
[2] | 366 | }
|
---|
| 367 | }
|
---|
| 368 |
|
---|
[155] | 369 | private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) {
|
---|
| 370 | if (level == 1) return new List<IFunctionTree>(tree.SubTrees);
|
---|
[2] | 371 |
|
---|
[155] | 372 | List<IFunctionTree> branches = new List<IFunctionTree>();
|
---|
| 373 | foreach (IFunctionTree subTree in tree.SubTrees) {
|
---|
| 374 | branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
|
---|
[2] | 375 | }
|
---|
[155] | 376 | return branches;
|
---|
[2] | 377 | }
|
---|
| 378 |
|
---|
| 379 |
|
---|
| 380 | #endregion
|
---|
| 381 |
|
---|
[155] | 382 | internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
|
---|
| 383 | List<IFunction> result = new List<IFunction>();
|
---|
| 384 | foreach (IFunction f in functions) {
|
---|
| 385 | if (IsPossibleParent(f, list)) {
|
---|
| 386 | result.Add(f);
|
---|
[2] | 387 | }
|
---|
| 388 | }
|
---|
| 389 | return result;
|
---|
| 390 | }
|
---|
| 391 |
|
---|
[155] | 392 | private bool IsPossibleParent(IFunction f, List<IFunction> children) {
|
---|
[2] | 393 | int minArity;
|
---|
| 394 | int maxArity;
|
---|
[155] | 395 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
[2] | 396 |
|
---|
| 397 | // note: we can't assume that the operators in the children list have different types!
|
---|
| 398 |
|
---|
| 399 | // when the maxArity of this function is smaller than the list of operators that
|
---|
| 400 | // should be included as sub-operators then it can't be a parent
|
---|
| 401 | if (maxArity < children.Count()) {
|
---|
| 402 | return false;
|
---|
| 403 | }
|
---|
| 404 | int nSlots = Math.Max(minArity, children.Count);
|
---|
| 405 |
|
---|
| 406 | SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
|
---|
[155] | 407 | analyzer.AllPossibleOperators = children.Cast<IOperator>().ToArray<IOperator>();
|
---|
[2] | 408 |
|
---|
[155] | 409 | List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
|
---|
[2] | 410 |
|
---|
[155] | 411 | // we iterate through all slots for sub-trees and calculate the set of
|
---|
| 412 | // allowed functions for this slot.
|
---|
[2] | 413 | // we only count those slots that can hold at least one of the children that we should combine
|
---|
| 414 | for (int slot = 0; slot < nSlots; slot++) {
|
---|
[155] | 415 | HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
|
---|
| 416 | if (functionSet.Count() > 0) {
|
---|
| 417 | slotSets.Add(functionSet);
|
---|
[2] | 418 | }
|
---|
| 419 | }
|
---|
| 420 |
|
---|
| 421 | // ok at the end of this operation we know how many slots of the parent can actually
|
---|
| 422 | // hold one of our children.
|
---|
| 423 | // if the number of slots is smaller than the number of children we can be sure that
|
---|
[155] | 424 | // we can never combine all children as sub-trees of the function and thus the function
|
---|
[2] | 425 | // can't be a parent.
|
---|
| 426 | if (slotSets.Count() < children.Count()) {
|
---|
| 427 | return false;
|
---|
| 428 | }
|
---|
| 429 |
|
---|
| 430 | // finally we sort the sets by size and beginning from the first set select one
|
---|
[155] | 431 | // function for the slot and thus remove it as possible sub-tree from the remaining sets.
|
---|
| 432 | // when we can successfully assign all available children to a slot the function is a valid parent
|
---|
| 433 | // when only a subset of all children can be assigned to slots the function is no valid parent
|
---|
[2] | 434 | slotSets.Sort((p, q) => p.Count() - q.Count());
|
---|
| 435 |
|
---|
| 436 | int assignments = 0;
|
---|
| 437 | for (int i = 0; i < slotSets.Count() - 1; i++) {
|
---|
| 438 | if (slotSets[i].Count > 0) {
|
---|
[155] | 439 | IFunction selected = slotSets[i].ElementAt(0);
|
---|
[2] | 440 | assignments++;
|
---|
| 441 | for (int j = i + 1; j < slotSets.Count(); j++) {
|
---|
| 442 | slotSets[j].Remove(selected);
|
---|
| 443 | }
|
---|
| 444 | }
|
---|
| 445 | }
|
---|
| 446 |
|
---|
| 447 | // sanity check
|
---|
| 448 | if (assignments > children.Count) throw new InvalidProgramException();
|
---|
| 449 | return assignments == children.Count - 1;
|
---|
| 450 | }
|
---|
| 451 | }
|
---|
| 452 | }
|
---|