Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs @ 16157

Last change on this file since 16157 was 16157, checked in by bburlacu, 6 years ago

#2886: Update IGrammarEnumerationEvaluator interface (add Evaluate method accepting an ISymbolicExpressionTree for the case when the constants have already been optimized in the tree, add boolean OptimizeConstants flag), small refactor in GrammarEnumeration/GrammarEnumerationAlgorithm.cs, add unit tests

File size: 8.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
5using Microsoft.VisualStudio.TestTools.UnitTesting;
6
7namespace Test {
8  [TestClass]
9  public class TreeHashingTest {
10
11    private Grammar grammar;
12    private TerminalSymbol varA;
13    private TerminalSymbol varB;
14    private TerminalSymbol varC;
15    private TerminalSymbol c;
16
17    [TestInitialize]
18    public void InitTest() {
19      grammar = new Grammar(new[] { "a", "b", "c" });
20
21      varA = grammar.VarTerminals.First(s => s.StringRepresentation == "a");
22      varB = grammar.VarTerminals.First(s => s.StringRepresentation == "b");
23      varC = grammar.VarTerminals.First(s => s.StringRepresentation == "c");
24      c = grammar.Const;
25    }
26
27    [TestMethod]
28    [TestCategory("TreeHashing")]
29    public void SimpleEqualityAddition() {
30      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
31      SymbolList s2 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
32
33      int hash1 = grammar.Hasher.CalcHashCode(s1);
34      int hash2 = grammar.Hasher.CalcHashCode(s2);
35
36      Assert.AreEqual(hash1, hash2);
37    }
38
39    [TestMethod]
40    [TestCategory("TreeHashing")]
41    public void SimpleInequalityAddition() {
42      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
43      SymbolList s2 = new SymbolList(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });
44
45      int hash1 = grammar.Hasher.CalcHashCode(s1);
46      int hash2 = grammar.Hasher.CalcHashCode(s2);
47
48      Assert.AreNotEqual(hash1, hash2);
49    }
50
51    [TestMethod]
52    [TestCategory("TreeHashing")]
53    public void CommutativityAddition() {
54      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition });
55      SymbolList s2 = new SymbolList(new[] { varB, varA, grammar.Addition });
56
57      int hash1 = grammar.Hasher.CalcHashCode(s1);
58      int hash2 = grammar.Hasher.CalcHashCode(s2);
59
60      Assert.AreEqual(hash1, hash2);
61    }
62
63    [TestMethod]
64    [TestCategory("TreeHashing")]
65    public void AssociativityAddition() {
66      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varA, grammar.Addition });
67      SymbolList s2 = new SymbolList(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });
68
69      int hash1 = grammar.Hasher.CalcHashCode(s1);
70      int hash2 = grammar.Hasher.CalcHashCode(s2);
71
72      Assert.AreEqual(hash1, hash2);
73    }
74
75    [TestMethod]
76    [TestCategory("TreeHashing")]
77    public void RepeatedAddition() {
78      SymbolList s1 = new SymbolList(new[] { varA, varA, grammar.Addition, varA, grammar.Addition });
79      SymbolList s2 = new SymbolList(new[] { varA });
80
81      int hash1 = grammar.Hasher.CalcHashCode(s1);
82      int hash2 = grammar.Hasher.CalcHashCode(s2);
83
84      Assert.AreEqual(hash1, hash2);
85    }
86
87    [TestMethod]
88    [TestCategory("TreeHashing")]
89    public void ComplexInequality() {
90      SymbolList s1 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Multiplication });
91      SymbolList s2 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });
92
93      int hash1 = grammar.Hasher.CalcHashCode(s1);
94      int hash2 = grammar.Hasher.CalcHashCode(s2);
95
96      Assert.AreNotEqual(hash1, hash2);
97    }
98
99    [TestMethod]
100    [TestCategory("TreeHashing")]
101    public void NonterminalHashing() {
102      SymbolList s1 = new SymbolList(new Symbol[] { varA, varA, grammar.Expr, grammar.Addition, grammar.Addition });
103      SymbolList s2 = new SymbolList(new Symbol[] { varA, grammar.Expr, grammar.Addition });
104
105      int hash1 = grammar.Hasher.CalcHashCode(s1);
106      int hash2 = grammar.Hasher.CalcHashCode(s2);
107
108      Assert.AreEqual(hash1, hash2);
109    }
110
111    [TestMethod]
112    [TestCategory("TreeHashing")]
113    public void InverseFactorCancelationSimple() {
114      // 1/a * b * a * a
115      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
116      // a * b
117      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Multiplication });
118
119      int hash1 = grammar.Hasher.CalcHashCode(s1);
120      int hash2 = grammar.Hasher.CalcHashCode(s2);
121
122      Assert.AreEqual(hash1, hash2);
123    }
124
125    [TestMethod]
126    [TestCategory("TreeHashing")]
127    public void InverseFactorCancelationComplex() {
128      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Sin, varA, varA, grammar.Multiplication, varA, grammar.Addition, grammar.Sin, grammar.Addition });
129      SymbolList s2 = new SymbolList(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
130
131      int hash1 = grammar.Hasher.CalcHashCode(s1);
132      int hash2 = grammar.Hasher.CalcHashCode(s2);
133
134      Assert.AreEqual(hash1, hash2);
135    }
136
137    // Constants
138    [TestMethod]
139    [TestCategory("TreeHashing")]
140    public void SimpleConst() {
141      SymbolList s1 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, grammar.Addition });
142      SymbolList s2 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, varA, grammar.Multiplication, grammar.Addition, c, grammar.Addition });
143
144      int hash1 = grammar.Hasher.CalcHashCode(s1);
145      int hash2 = grammar.Hasher.CalcHashCode(s2);
146
147      Assert.AreEqual(hash1, hash2);
148    }
149
150    [TestMethod]
151    [TestCategory("TreeHashing")]
152    public void EnumerateGrammarTest() {
153      //const int nvars = 1;
154      //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
155      var variables = new[] { "b", "a" };
156      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
157
158      int hash(SymbolList s) => grammar.Hasher.CalcHashCode(s);
159
160      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
161      Console.WriteLine($"Breadth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
162
163      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
164      Console.WriteLine($"Breadth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
165
166      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
167      Console.WriteLine($"Depth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
168
169      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
170      Console.WriteLine($"Depth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
171    }
172
173    private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
174      var phrases = new Queue<SymbolList>();
175      phrases.Enqueue(new SymbolList(grammar.StartSymbol));
176      var sentences = new List<SymbolList>();
177      var archive = new HashSet<int>();
178
179      while (phrases.Any()) {
180        var phrase = phrases.Dequeue();
181
182        if (phrase.Count > length)
183          continue;
184
185        if (phrase.IsSentence()) {
186          sentences.Add(phrase);
187          continue;
188        }
189
190        if (hashPhrases && !archive.Add(grammar.Hasher.CalcHashCode(phrase))) {
191          continue;
192        }
193
194        var idx = phrase.NextNonterminalIndex();
195        var productions = grammar.Productions[phrase[idx]];
196        var derived = productions.Select(p => phrase.DerivePhrase(idx, p)).Where(p => p.Count <= length);
197        foreach (var d in derived)
198          phrases.Enqueue(d);
199      }
200      return sentences;
201    }
202
203    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, bool hashPhrases = true) {
204      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, hashPhrases ? new HashSet<int>() : null);
205    }
206
207    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, HashSet<int> visited) {
208      if (phrase.Count > maxLength) {
209        yield break;
210      }
211
212      if (phrase.IsSentence()) {
213        yield return phrase;
214        yield break;
215      }
216
217      if (visited != null && !visited.Add(grammar.Hasher.CalcHashCode(phrase))) {
218        yield break;
219      }
220
221      var i = phrase.NextNonterminalIndex();
222      var productions = grammar.Productions[phrase[i]];
223
224      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, visited)))
225        yield return s;
226    }
227  }
228}
Note: See TracBrowser for help on using the repository browser.