Changeset 16157 for branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

Timestamp:

09/20/18 11:12:57 (6 years ago)

Author:

bburlacu

Message:

#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:

• branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs (modified) (2 diffs)

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -1 @@
-using System.Linq;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -146 +148 @@
     }
 
-    /* DEPRECATED; SINCE WE DO NOT ALLOW COMPOUND DIVISIONS
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void CompoundInverseCancellationToSingleInverse() {
-      SymbolList s1 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv, grammar.Inv });
-      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreEqual(hash1, hash2);
-    }
-
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void CompoundInverseCancellationToDivisor() {
-      SymbolList s1 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv });
-      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreEqual(hash1, hash2);
-    }
-
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void UncancelableCompoundInverse() {
-      // 1 / ( 1/b + sin(a*c) )
-      SymbolList s1 = new SymbolList(new Symbol[] { varB, grammar.Inv, varA, varC, grammar.Multiplication, grammar.Sin, grammar.Addition, grammar.Inv });
-      // b + sin(a*c)
-      SymbolList s2 = new SymbolList(new Symbol[] { varB, varA, varC, grammar.Multiplication, grammar.Sin, grammar.Addition });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreNotEqual(hash1, hash2);
-    }*/
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void EnumerateGrammarTest() {
+      //const int nvars = 1;
+      //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
+      var variables = new[] { "b", "a" };
+      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
+
+      int hash(SymbolList s) => grammar.Hasher.CalcHashCode(s);
+
+      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
+      Console.WriteLine($"Breadth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
+      Console.WriteLine($"Breadth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
+      Console.WriteLine($"Depth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
+      Console.WriteLine($"Depth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+    }
+
+    private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
+      var phrases = new Queue<SymbolList>();
+      phrases.Enqueue(new SymbolList(grammar.StartSymbol));
+      var sentences = new List<SymbolList>();
+      var archive = new HashSet<int>();
+
+      while (phrases.Any()) {
+        var phrase = phrases.Dequeue();
+
+        if (phrase.Count > length)
+          continue;
+
+        if (phrase.IsSentence()) {
+          sentences.Add(phrase);
+          continue;
+        }
+
+        if (hashPhrases && !archive.Add(grammar.Hasher.CalcHashCode(phrase))) {
+          continue;
+        }
+
+        var idx = phrase.NextNonterminalIndex();
+        var productions = grammar.Productions[phrase[idx]];
+        var derived = productions.Select(p => phrase.DerivePhrase(idx, p)).Where(p => p.Count <= length);
+        foreach (var d in derived)
+          phrases.Enqueue(d);
+      }
+      return sentences;
+    }
+
+    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, bool hashPhrases = true) {
+      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, hashPhrases ? new HashSet<int>() : null);
+    }
+
+    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, HashSet<int> visited) {
+      if (phrase.Count > maxLength) {
+        yield break;
+      }
+
+      if (phrase.IsSentence()) {
+        yield return phrase;
+        yield break;
+      }
+
+      if (visited != null && !visited.Add(grammar.Hasher.CalcHashCode(phrase))) {
+        yield break;
+      }
+
+      var i = phrase.NextNonterminalIndex();
+      var productions = grammar.Productions[phrase[i]];
+
+      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, visited)))
+        yield return s;
+    }
   }
 }