Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs @ 15480

Last change on this file since 15480 was 14355, checked in by bburlacu, 8 years ago

#2685: Add correction step to account for grammar cycles. Update unit test/
File size: 14.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Linq;
23using Microsoft.VisualStudio.TestTools.UnitTesting;
24
25namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Tests {
26  [TestClass]
27  public class GrammarsTest {
28    [TestMethod]
29    [TestCategory("Encodings.SymbolicExpressionTree")]
30    [TestProperty("Time", "short")]
31    public void MinimumExpressionLengthTest() {
32      {
33        var grammar = CreateTestGrammar1();
34
35        var prs = grammar.ProgramRootSymbol;
36        var ss = grammar.StartSymbol;
37        var x = grammar.Symbols.First(s => s.Name == "<x>");
38
39        Assert.AreEqual(8, grammar.GetMinimumExpressionLength(prs));
40        Assert.AreEqual(7, grammar.GetMinimumExpressionLength(ss));
41        Assert.AreEqual(6, grammar.GetMinimumExpressionLength(x));
42      }
43
44      {
45        var grammar = CreateTestGrammar2();
46
47        var prs = grammar.ProgramRootSymbol;
48        var ss = grammar.StartSymbol;
49        var x = grammar.Symbols.First(s => s.Name == "<x>");
50
51        Assert.AreEqual(13, grammar.GetMinimumExpressionLength(prs));
52        Assert.AreEqual(12, grammar.GetMinimumExpressionLength(ss));
53        Assert.AreEqual(11, grammar.GetMinimumExpressionLength(x));
54      }
55
56      {
57        var grammar = CreateTestGrammar3();
58        var prs = grammar.ProgramRootSymbol;
59        var ss = grammar.StartSymbol;
60        var x = grammar.Symbols.First(s => s.Name == "<x>");
61        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
62        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
63        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
64      }
65
66      {
67        var grammar = CreateTestGrammar4();
68        var prs = grammar.ProgramRootSymbol;
69        var ss = grammar.StartSymbol;
70        var x = grammar.Symbols.First(s => s.Name == "<x>");
71        var y = grammar.Symbols.First(s => s.Name == "<y>");
72        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
73        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
74        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
75        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(y));
76      }
77
78      {
79        var grammar = CreateTestGrammar5();
80        var prs = grammar.ProgramRootSymbol;
81        var ss = grammar.StartSymbol;
82        var x = grammar.Symbols.First(s => s.Name == "<x>");
83        var y = grammar.Symbols.First(s => s.Name == "<y>");
84        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(prs));
85        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(ss));
86        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(x));
87        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
88      }
89
90      {
91        var grammar = CreateTestGrammar6();
92        var prs = grammar.ProgramRootSymbol;
93        var ss = grammar.StartSymbol;
94        var x = grammar.Symbols.First(s => s.Name == "<x>");
95        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
96        var a = grammar.Symbols.First(s => s.Name == "<a>");
97        var b = grammar.Symbols.First(s => s.Name == "<b>");
98        var c = grammar.Symbols.First(s => s.Name == "<c>");
99        var d = grammar.Symbols.First(s => s.Name == "<d>");
100        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
101        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(ss));
102        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(x));
103        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(s_));
104        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
105        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
106        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(c));
107        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(d));
108      }
109    }
110
111    [TestMethod]
112    [TestCategory("Encodings.SymbolicExpressionTree")]
113    [TestProperty("Time", "short")]
114    public void MinimumExpressionDepthTest() {
115      {
116        var grammar = CreateTestGrammar1();
117
118        var prs = grammar.ProgramRootSymbol;
119        var ss = grammar.StartSymbol;
120        var a = grammar.Symbols.First(s => s.Name == "<a>");
121        var b = grammar.Symbols.First(s => s.Name == "<b>");
122        var c = grammar.Symbols.First(s => s.Name == "<c>");
123        var d = grammar.Symbols.First(s => s.Name == "<d>");
124        var x = grammar.Symbols.First(s => s.Name == "x");
125        var y = grammar.Symbols.First(s => s.Name == "y");
126
127        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
128        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
129        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
130        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
131        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
132        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
133        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
134        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
135      }
136
137      {
138        var grammar = CreateTestGrammar2();
139
140        var prs = grammar.ProgramRootSymbol;
141        var ss = grammar.StartSymbol;
142        var a = grammar.Symbols.First(s => s.Name == "<a>");
143        var b = grammar.Symbols.First(s => s.Name == "<b>");
144        var c = grammar.Symbols.First(s => s.Name == "<c>");
145        var d = grammar.Symbols.First(s => s.Name == "<d>");
146        var x = grammar.Symbols.First(s => s.Name == "x");
147        var y = grammar.Symbols.First(s => s.Name == "y");
148
149        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
150        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
151        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
152        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
153        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
154        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
155        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
156        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
157      }
158
159      {
160        var grammar = CreateTestGrammar3();
161        var prs = grammar.ProgramRootSymbol;
162        var ss = grammar.StartSymbol;
163        var x = grammar.Symbols.First(s => s.Name == "<x>");
164        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
165        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
166        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
167      }
168
169      {
170        var grammar = CreateTestGrammar4();
171        var prs = grammar.ProgramRootSymbol;
172        var ss = grammar.StartSymbol;
173        var x = grammar.Symbols.First(s => s.Name == "<x>");
174        var y = grammar.Symbols.First(s => s.Name == "<y>");
175        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
176        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
177        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
178        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(y));
179      }
180
181      {
182        var grammar = CreateTestGrammar5();
183        var prs = grammar.ProgramRootSymbol;
184        var ss = grammar.StartSymbol;
185        var x = grammar.Symbols.First(s => s.Name == "<x>");
186        var y = grammar.Symbols.First(s => s.Name == "<y>");
187        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
188        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
189        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(x));
190        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
191      }
192
193      {
194        var grammar = CreateTestGrammar6();
195        var prs = grammar.ProgramRootSymbol;
196        var ss = grammar.StartSymbol;
197        var x = grammar.Symbols.First(s => s.Name == "<x>");
198        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
199        var a = grammar.Symbols.First(s => s.Name == "<a>");
200        var b = grammar.Symbols.First(s => s.Name == "<b>");
201        var c = grammar.Symbols.First(s => s.Name == "<c>");
202        var d = grammar.Symbols.First(s => s.Name == "<d>");
203        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
204        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(ss));
205        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(x));
206        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(s_));
207        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
208        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
209        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(c));
210        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(d));
211      }
212    }
213
214    private static ISymbolicExpressionGrammar CreateTestGrammar1() {
215      var grammar = new SimpleSymbolicExpressionGrammar();
216      var x = new SimpleSymbol("<x>", 1);
217      var z = new SimpleSymbol("<z>", 6);
218      var a = new SimpleSymbol("<a>", 1);
219      var b = new SimpleSymbol("<b>", 1);
220      var c = new SimpleSymbol("<c>", 1);
221      var d = new SimpleSymbol("<d>", 1);
222
223      var _x = new SimpleSymbol("x", 0);
224      var _y = new SimpleSymbol("y", 0);
225
226      grammar.AddSymbol(x);
227      grammar.AddSymbol(z);
228      grammar.AddSymbol(a);
229      grammar.AddSymbol(b);
230      grammar.AddSymbol(c);
231      grammar.AddSymbol(d);
232      grammar.AddSymbol(_x);
233      grammar.AddSymbol(_y);
234
235      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
236      //uncommenting the line below changes the minimum expression length for the symbol <x>
237      grammar.AddAllowedChildSymbol(x, z);
238      grammar.AddAllowedChildSymbol(z, _x);
239      grammar.AddAllowedChildSymbol(x, a);
240      grammar.AddAllowedChildSymbol(a, b);
241      grammar.AddAllowedChildSymbol(b, c);
242      grammar.AddAllowedChildSymbol(c, d);
243      grammar.AddAllowedChildSymbol(d, _y);
244
245      return grammar;
246    }
247
248    private static ISymbolicExpressionGrammar CreateTestGrammar2() {
249      var grammar = new SimpleSymbolicExpressionGrammar();
250      var x = new SimpleSymbol("<x>", 2);
251      var z = new SimpleSymbol("<z>", 6);
252      var a = new SimpleSymbol("<a>", 1);
253      var b = new SimpleSymbol("<b>", 1);
254      var c = new SimpleSymbol("<c>", 1);
255      var d = new SimpleSymbol("<d>", 1);
256
257      var _x = new SimpleSymbol("x", 0);
258      var _y = new SimpleSymbol("y", 0);
259
260      grammar.AddSymbol(x);
261      grammar.AddSymbol(z);
262      grammar.AddSymbol(a);
263      grammar.AddSymbol(b);
264      grammar.AddSymbol(c);
265      grammar.AddSymbol(d);
266      grammar.AddSymbol(_x);
267      grammar.AddSymbol(_y);
268
269      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
270      //uncommenting the line below changes the minimum expression length for the symbol <x>
271      grammar.AddAllowedChildSymbol(x, z);
272      grammar.AddAllowedChildSymbol(z, _x);
273      grammar.AddAllowedChildSymbol(x, a);
274      grammar.AddAllowedChildSymbol(a, b);
275      grammar.AddAllowedChildSymbol(b, c);
276      grammar.AddAllowedChildSymbol(c, d);
277      grammar.AddAllowedChildSymbol(d, _y);
278
279      return grammar;
280    }
281
282    private static ISymbolicExpressionGrammar CreateTestGrammar3() {
283      var grammar = new SimpleSymbolicExpressionGrammar();
284      var x = new SimpleSymbol("<x>", 1);
285
286      grammar.AddSymbol(x);
287
288      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
289      grammar.AddAllowedChildSymbol(x, x);
290      return grammar;
291    }
292
293
294    private static ISymbolicExpressionGrammar CreateTestGrammar4() {
295      var grammar = new SimpleSymbolicExpressionGrammar();
296      var x = new SimpleSymbol("<x>", 1);
297      var y = new SimpleSymbol("<y>", 1);
298
299      grammar.AddSymbol(x);
300      grammar.AddSymbol(y);
301
302      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
303      grammar.AddAllowedChildSymbol(x, x);
304      grammar.AddAllowedChildSymbol(x, y);
305      grammar.AddAllowedChildSymbol(y, x);
306      grammar.AddAllowedChildSymbol(y, y);
307      return grammar;
308    }
309
310    private static ISymbolicExpressionGrammar CreateTestGrammar5() {
311      var grammar = new SimpleSymbolicExpressionGrammar();
312      var x = new SimpleSymbol("<x>", 1);
313      var y = new SimpleSymbol("<y>", 1);
314      var _x = new SimpleSymbol("x", 0);
315
316      grammar.AddSymbol(x);
317      grammar.AddSymbol(y);
318      grammar.AddSymbol(_x);
319
320      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
321      grammar.AddAllowedChildSymbol(x, x);
322      grammar.AddAllowedChildSymbol(x, y);
323      grammar.AddAllowedChildSymbol(y, x);
324      grammar.AddAllowedChildSymbol(y, y);
325      grammar.AddAllowedChildSymbol(y, _x);
326      return grammar;
327    }
328
329    private static ISymbolicExpressionGrammar CreateTestGrammar6() {
330      var grammar = new SimpleSymbolicExpressionGrammar();
331      var x = new SimpleSymbol("<x>", 1);
332      var s = new SimpleSymbol("<s>", 1);
333      var a = new SimpleSymbol("<a>", 1);
334      var b = new SimpleSymbol("<b>", 1);
335      var c = new SimpleSymbol("<c>", 1);
336      var d = new SimpleSymbol("<d>", 1);
337      var e = new SimpleSymbol("<e>", 1);
338
339      var _x = new SimpleSymbol("x", 0);
340      var _y = new SimpleSymbol("y", 0);
341
342      grammar.AddSymbol(x);
343      grammar.AddSymbol(s);
344      grammar.AddSymbol(a);
345      grammar.AddSymbol(b);
346      grammar.AddSymbol(c);
347      grammar.AddSymbol(d);
348      grammar.AddSymbol(e);
349      grammar.AddSymbol(_x);
350      grammar.AddSymbol(_y);
351
352      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
353      grammar.AddAllowedChildSymbol(x, s);
354      grammar.AddAllowedChildSymbol(x, _x);
355      grammar.AddAllowedChildSymbol(s, a);
356      grammar.AddAllowedChildSymbol(a, b);
357      grammar.AddAllowedChildSymbol(a, c);
358      grammar.AddAllowedChildSymbol(b, x);
359      grammar.AddAllowedChildSymbol(c, d);
360      grammar.AddAllowedChildSymbol(d, e);
361      grammar.AddAllowedChildSymbol(e, _y);
362
363      return grammar;
364    }
365  }
366}
Note: See TracBrowser for help on using the repository browser.