Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HL-3.2-MonoMigration/HeuristicLab.Constraints/SubOperatorsConstraintAnalyser.cs @ 4075

Last change on this file since 4075 was 431, checked in by gkronber, 16 years ago

removed the 'AllowedSubOperators' variable for functions because the original intention was to cache the list of allowed sub-functions which is actually determined by a tree of constraints. However the original idea was never fully implemented so up to now any function in the library was allowed for any other function as long as it was not a terminal (also defined by constraints on the arity). The 'AllowedSubOperators' variable is not necessary at all when we defined the set via constraints. The SubOperatorsConstraintView allows draging of functions from the library into the constraint.

Next step: automatic adaption of SubOperatorsConstraints of functions in the library when new functions are added or existing entries removed.
(ticket #225)

File size: 5.9 KB
Line 
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
22using System;
23using System.Collections.Generic;
24using System.Text;
25using HeuristicLab.Core;
26using HeuristicLab.Constraints;
27using HeuristicLab.Data;
28
29namespace HeuristicLab.Constraints {
30  public class SubOperatorsConstraintAnalyser {
31    private ICollection<IOperator> allPossibleOperators;
32
33    public ICollection<IOperator> AllPossibleOperators {
34      get { return allPossibleOperators; }
35      set { allPossibleOperators = value; }
36    }
37
38    public IList<IOperator> GetAllowedOperators(IOperator op, int childIndex) {
39      AndConstraint andConstraint = new AndConstraint();
40      foreach(IConstraint constraint in op.Constraints) {
41        andConstraint.Clauses.Add(constraint);
42      }
43     
44      GetAllowedOperatorsVisitor visitor = new GetAllowedOperatorsVisitor(allPossibleOperators, childIndex);
45      andConstraint.Accept(visitor);
46      return visitor.AllowedOperators;
47    }
48
49    #region static set management methods
50    // better to use HashSets from .NET 3.5
51    // however we would need to switch the whole Constraints project to .NET 3.5 for that
52    private static IList<IOperator> Intersect(ICollection<IOperator> a, ICollection<IOperator> b) {
53      if(a.Count > b.Count) {
54        return Intersect(b, a);
55      }
56
57      List<IOperator> intersection = new List<IOperator>(a.Count);
58
59      foreach(IOperator element in a) {
60        if(InSet(element, b)) {
61          intersection.Add(element);
62        }
63      }
64      return intersection;
65    }
66
67    private static IList<IOperator> Union(ICollection<IOperator> a, ICollection<IOperator> b) {
68      List<IOperator> union = new List<IOperator>(a);
69      foreach(IOperator candidateElement in b) {
70        if(!InSet(candidateElement, union)) {
71          union.Add(candidateElement);
72        }
73      }
74
75      return union;
76    }
77
78    private static IList<IOperator> Substract(ICollection<IOperator> minuend, ICollection<IOperator> subtrahend) {
79      List<IOperator> difference = new List<IOperator>();
80      foreach(IOperator element in minuend) {
81        if(!InSet(element, subtrahend)) {
82          difference.Add(element);
83        }
84      }
85
86      return difference;
87    }
88
89    private static bool InSet(IOperator op, ICollection<IOperator> set) {
90      foreach(IOperator element in set) {
91        if(element == op)
92          return true;
93      }
94      return false;
95    }
96    #endregion
97
98    #region visitor
99    /// <summary>
100    /// The visitor builds a set of allowed operators based on a tree of constraints.
101    /// </summary>
102    private class GetAllowedOperatorsVisitor : ConstraintVisitorBase {
103      private IList<IOperator> allowedOperators;
104
105      public IList<IOperator> AllowedOperators {
106        get { return allowedOperators; }
107      }
108      private ICollection<IOperator> possibleOperators;
109      private int childIndex;
110
111      public GetAllowedOperatorsVisitor(ICollection<IOperator> possibleOperators, int childIndex) {
112        // default is that all possible operators are allowed
113        allowedOperators = new List<IOperator>(possibleOperators);
114        this.possibleOperators = possibleOperators;
115        this.childIndex = childIndex;
116      }
117
118      public override void Visit(AndConstraint constraint) {
119        base.Visit(constraint);
120
121        // keep only the intersection of all subconstraints
122        foreach(ConstraintBase clause in constraint.Clauses) {
123          GetAllowedOperatorsVisitor visitor = new GetAllowedOperatorsVisitor(possibleOperators, childIndex);
124          clause.Accept(visitor);
125          allowedOperators = Intersect(allowedOperators, visitor.allowedOperators);
126        }
127      }
128
129      public override void Visit(OrConstraint constraint) {
130        base.Visit(constraint);
131
132        // allowed operators is the union of all allowed operators as defined by the subconstraints
133        allowedOperators.Clear();
134
135        foreach(ConstraintBase clause in constraint.Clauses) {
136          GetAllowedOperatorsVisitor visitor = new GetAllowedOperatorsVisitor(possibleOperators, childIndex);
137          clause.Accept(visitor);
138          allowedOperators = Union(allowedOperators, visitor.allowedOperators);
139        }
140      }
141
142      public override void Visit(NotConstraint constraint) {
143        base.Visit(constraint);
144        GetAllowedOperatorsVisitor visitor = new GetAllowedOperatorsVisitor(possibleOperators, childIndex);
145        constraint.SubConstraint.Accept(visitor);
146
147        allowedOperators = Substract(possibleOperators, visitor.allowedOperators);
148      }
149
150      public override void Visit(AllSubOperatorsTypeConstraint constraint) {
151        base.Visit(constraint);
152
153        allowedOperators = Intersect(possibleOperators, constraint.AllowedSubOperators);
154      }
155
156      public override void Visit(SubOperatorTypeConstraint constraint) {
157        if(childIndex != constraint.SubOperatorIndex.Data) {
158          allowedOperators = new List<IOperator>(possibleOperators);
159        } else {
160          allowedOperators = Intersect(possibleOperators, constraint.AllowedSubOperators);
161        }
162      }
163    }
164    #endregion
165  }
166}
Note: See TracBrowser for help on using the repository browser.