Changeset 15714 for branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration
- Timestamp:
- 02/02/18 18:48:10 (7 years ago)
- Location:
- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs
r15712 r15714 1 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration { 1 using System.Collections; 2 using System.Collections.Generic; 3 using System.ComponentModel; 4 using System.Diagnostics; 5 using System.Linq; 6 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration; 7 using HeuristicLab.Common; 8 9 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration { 2 10 public class Grammar { 3 11 4 12 public Symbol StartSymbol; 5 13 14 #region Symbols 15 public VariableSymbol Var; 16 17 public NonterminalSymbol Expr; 18 public NonterminalSymbol Term; 19 public NonterminalSymbol Factor; 20 21 public TerminalSymbol Addition; 22 public TerminalSymbol Multiplication; 23 #endregion 24 25 6 26 public Grammar(string[] variables) { 7 27 #region Define Symbols 8 Var iableSymbol var= new VariableSymbol("var", variables);28 Var = new VariableSymbol("var", variables); 9 29 10 NonterminalSymbol expr = new NonterminalSymbol("Expr");11 NonterminalSymbol term = new NonterminalSymbol("Expr");12 NonterminalSymbol factor = new NonterminalSymbol("Expr");30 Expr = new NonterminalSymbol("Expr"); 31 Term = new NonterminalSymbol("Term"); 32 Factor = new NonterminalSymbol("Factor"); 13 33 14 TerminalSymbol addition = new TerminalSymbol("+");15 TerminalSymbol multiplication = new TerminalSymbol("*");34 Addition = new TerminalSymbol("+"); 35 Multiplication = new TerminalSymbol("*"); 16 36 #endregion 17 37 18 38 19 39 #region Production ruless 20 StartSymbol = expr;40 StartSymbol = Expr; 21 41 22 expr.AddProduction(term, expr, addition);23 expr.AddProduction(term);42 Expr.AddProduction(Term, Expr, Addition); 43 Expr.AddProduction(Term); 24 44 25 term.AddProduction(factor, term, multiplication);26 term.AddProduction(factor);45 Term.AddProduction(Factor, Term, Multiplication); 46 Term.AddProduction(Factor); 27 47 28 factor.AddProduction(var);48 Factor.AddProduction(Var); 29 49 #endregion 50 } 51 52 public int CalcHashCode(SymbolString sentence) { 53 Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!"); 54 Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!"); 55 56 Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>()); 57 58 int[] subtreeHashes = GetSubtreeHashes(parseStack.Pop(), parseStack); 59 return AggregateHashes(subtreeHashes); 60 } 61 62 private int[] GetSubtreeHashes(TerminalSymbol currentSymbol, Stack<TerminalSymbol> parseStack) { 63 List<int> childHashes = null; 64 65 if (Var.VariableTerminalSymbols.Contains(currentSymbol)) { 66 childHashes = currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToList(); 67 68 } else if (ReferenceEquals(currentSymbol, Multiplication)) { // MULTIPLICATION 69 childHashes = new List<int>(); 70 71 // First subtree 72 TerminalSymbol firstSubtreeRoot = parseStack.Pop(); 73 int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack); 74 75 if (ReferenceEquals(firstSubtreeRoot, Multiplication)) { 76 childHashes.AddRange(firstSubtreeHashes); 77 } else { 78 childHashes.Add(AggregateHashes(firstSubtreeHashes)); 79 } 80 81 // Second subtree 82 TerminalSymbol secondSubtreeRoot = parseStack.Pop(); 83 int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack); 84 85 if (ReferenceEquals(secondSubtreeRoot, Multiplication)) { 86 childHashes.AddRange(secondSubtreeHashes); 87 } else { 88 childHashes.Add(AggregateHashes(secondSubtreeHashes)); 89 } 90 91 // Sort due to commutativity 92 childHashes.Sort(); 93 94 95 96 } else if (ReferenceEquals(currentSymbol, Addition)) { // ADDITION 97 HashSet<int> uniqueChildHashes = new HashSet<int>(); 98 99 TerminalSymbol firstSubtreeRoot = parseStack.Pop(); 100 int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack); 101 102 // First subtree 103 if (ReferenceEquals(firstSubtreeRoot, Addition)) { 104 uniqueChildHashes.UnionWith(firstSubtreeHashes); 105 } else { 106 uniqueChildHashes.Add(AggregateHashes(firstSubtreeHashes)); 107 } 108 109 // Second subtree 110 TerminalSymbol secondSubtreeRoot = parseStack.Pop(); 111 int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack); 112 113 if (ReferenceEquals(secondSubtreeRoot, Addition)) { 114 uniqueChildHashes.UnionWith(secondSubtreeHashes); 115 } else { 116 uniqueChildHashes.Add(AggregateHashes(secondSubtreeHashes)); 117 } 118 119 childHashes = uniqueChildHashes.ToList(); 120 childHashes.Sort(); 121 } 122 123 Debug.Assert(childHashes != null, "Sentence not hashable!"); 124 return childHashes.ToArray(); 125 } 126 127 128 private int AggregateHashes(IEnumerable<int> hashes) { 129 return hashes.Aggregate(0, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode()); 30 130 } 31 131 } -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs
r15712 r15714 1 using System.Collections.Generic; 1 using System; 2 using System.Collections.Generic; 2 3 using System.Collections.ObjectModel; 3 4 using System.Diagnostics; … … 41 42 DoubleValue averageTreeLength = new DoubleValue(); 42 43 Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength)); 43 44 44 45 45 int maxStringLength = 4; -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs
r15712 r15714 1 using System ;2 using System. Collections.Generic;1 using System.Collections.Generic; 2 using System.Linq; 3 3 4 4 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration { 5 5 6 6 public abstract class Symbol { 7 p rivate readonly string stringRepresentation;7 public readonly string StringRepresentation; 8 8 9 9 protected Symbol(string representation) { 10 stringRepresentation = representation;10 StringRepresentation = representation; 11 11 } 12 12 13 13 public override string ToString() { 14 return stringRepresentation;14 return StringRepresentation; 15 15 } 16 16 } … … 33 33 34 34 public class VariableSymbol : NonterminalSymbol { // Convenience class 35 public IEnumerable<TerminalSymbol> VariableTerminalSymbols; 36 35 37 public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) { 38 List<TerminalSymbol> createdSymbols = new List<TerminalSymbol>(); 39 VariableTerminalSymbols = createdSymbols; 40 36 41 foreach (string variableName in variableNames) { 37 AddProduction(new TerminalSymbol("[" + variableName + "]")); 42 TerminalSymbol s = new TerminalSymbol(variableName); 43 createdSymbols.Add(s); 44 AddProduction(s); 38 45 } 39 46 } -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
r15712 r15714 98 98 <Compile Include="GrammarEnumeration\Symbol.cs" /> 99 99 </ItemGroup> 100 <ItemGroup /> 100 101 <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> 101 102 <!-- To modify your build process, add your task inside one of the targets below and uncomment it.
Note: See TracChangeset
for help on using the changeset viewer.