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

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);
    }

    /* 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);
    }*/
  }
}