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

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Test {
  [TestClass]
  public class TreeHashingTest {

    private Grammar grammar;
    private TerminalSymbol varA;
    private TerminalSymbol varB;
    private TerminalSymbol varC;
    private TerminalSymbol c;

    [TestInitialize]
    public void InitTest() {
      grammar = new Grammar(new[] { "a", "b", "c" });

      varA = grammar.VarTerminals.First(s => s.StringRepresentation == "a");
      varB = grammar.VarTerminals.First(s => s.StringRepresentation == "b");
      varC = grammar.VarTerminals.First(s => s.StringRepresentation == "c");
      c = grammar.Const;
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleEqualityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleInequalityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreNotEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void CommutativityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varB, varA, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void AssociativityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varA, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void RepeatedAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varA, grammar.Addition, varA, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void ComplexInequality() {
      SymbolList s1 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Multiplication });
      SymbolList s2 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreNotEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void NonterminalHashing() {
      SymbolList s1 = new SymbolList(new Symbol[] { varA, varA, grammar.Expr, grammar.Addition, grammar.Addition });
      SymbolList s2 = new SymbolList(new Symbol[] { varA, grammar.Expr, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void InverseFactorCancelationSimple() {
      // 1/a * b * a * a
      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
      // a * b
      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Multiplication });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void InverseFactorCancelationComplex() {
      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Sin, varA, varA, grammar.Multiplication, varA, grammar.Addition, grammar.Sin, grammar.Addition });
      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 });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(hash1, hash2);
    }

    // Constants
    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleConst() {
      SymbolList s1 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, grammar.Addition });
      SymbolList s2 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, varA, grammar.Multiplication, grammar.Addition, c, grammar.Addition });

      int hash1 = grammar.Hasher.CalcHashCode(s1);
      int hash2 = grammar.Hasher.CalcHashCode(s2);

      Assert.AreEqual(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[] { "x", "y", "z", "w" };
      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());

      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);

      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
      Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
      Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).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;
    }
  }
}