Changeset 15821 for branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

Timestamp:

02/28/18 14:44:25 (7 years ago)

Author:

lkammere

Message:

#2886 Move code for visualization and logging of sentences to separate classes.

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (12 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
-using System.IO;
 using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using HeuristicLab.Collections;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -30 +29 @@
     private readonly string DistinctSentencesName = "Distinct Sentences";
     private readonly string PhraseExpansionsName = "Phrase Expansions";
-    private readonly string AverageTreeLengthName = "Avg. Sentence Length among Distinct";
-    private readonly string GeneratedEqualSentencesName = "Generated equal sentences";
+    private readonly string AverageSentenceLengthName = "Avg. Sentence Length among Distinct";
+    private readonly string OverwrittenSentencesName = "Sentences overwritten";
+    private readonly string AnalyzersParameterName = "Analyzers";
 
 
@@ -64 +64 @@
     }
 
+    public IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>> AnalyzersParameter {
+      get { return (IFixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>)Parameters[AnalyzersParameterName]; }
+    }
+
+    public ICheckedItemCollection<IGrammarEnumerationAnalyzer> Analyzers {
+      get { return AnalyzersParameter.Value; }
+    }
+
     public SymbolString BestTrainingSentence;
 
     #endregion
 
-    public Dictionary<int, SymbolString> DistinctSentences { get; private set; }  // Semantically distinct sentences in a run.
-    public Dictionary<int, List<SymbolString>> AllSentences { get; private set; } // All sentences ever generated in a run.
+    public Dictionary<int, int> DistinctSentencesLength { get; private set; }  // Semantically distinct sentences and their length in a run.
     public HashSet<int> ArchivedPhrases { get; private set; }
-
-    internal SearchDataStore OpenPhrases { get; private set; }                    // Stack/Queue/etc. for fetching the next node in the search tree.  
-
-    public int EqualGeneratedSentences { get; private set; } // It is not guaranteed that shorter solutions are found first. 
-                                                             // When longer solutions are overwritten with shorter ones, 
-                                                             // this counter is increased.
-    public int Expansions { get; private set; }              // Number, how many times a nonterminal symbol is replaced with a production rule.
+    internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  
+
+    #region execution stats
+    public int AllGeneratedSentencesCount { get; private set; }
+
+    public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first. 
+                                                               // When longer solutions are overwritten with shorter ones, 
+                                                               // this counter is increased.
+    public int PhraseExpansionCount { get; private set; }      // Number, how many times a nonterminal symbol is replaced with a production rule.
+    #endregion
+
     public Grammar Grammar { get; private set; }
 
-    private readonly string dotFileName = Environment.GetFolderPath(System.Environment.SpecialFolder.DesktopDirectory) + @"\searchgraph.dot";
+    private readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
 
     #region ctors
@@ -95 +106 @@
       Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(1000)));
       Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));
+
+      var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
+        new SearchGraphVisualizer(),
+        new SentenceLogger()
+      };
+      Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>(
+        AnalyzersParameterName,
+        new CheckedItemCollection<IGrammarEnumerationAnalyzer>(availableAnalyzers).AsReadOnly()));
+
+      foreach (var analyzer in Analyzers) {
+        Analyzers.SetItemCheckedState(analyzer, false);
+      }
+      Analyzers.CheckedItemsChanged += AnalyzersOnCheckedItemsChanged;
     }
 
@@ -104 +128 @@
       InitResults();
 
-      AllSentences = new Dictionary<int, List<SymbolString>>();
       ArchivedPhrases = new HashSet<int>();
 
-      DistinctSentences = new Dictionary<int, SymbolString>();
-      Expansions = 0;
-      EqualGeneratedSentences = 0;
+      DistinctSentencesLength = new Dictionary<int, int>();
+      AllGeneratedSentencesCount = 0;
+      OverwrittenSentencesCount = 0;
+      PhraseExpansionCount = 0;
 
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
@@ -118 +142 @@
       #endregion
 
-      using (TextWriterTraceListener dotFileTrace = new TextWriterTraceListener(new FileStream(dotFileName, FileMode.Create))) {
-        LogSearchGraph(dotFileTrace, "digraph searchgraph { pad=0.02; nodesep=0.3; ranksep=0.02;ratio=0.5625;");
-
-        OpenPhrases.Store(phrase0Hash, phrase0);
-        while (OpenPhrases.Count > 0) {
-          if (cancellationToken.IsCancellationRequested) break;
-
-          StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
-          SymbolString currPhrase = fetchedPhrase.SymbolString;
-#if DEBUG
-          LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} [label=\"{Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString)}\"];");
-#endif
-          ArchivedPhrases.Add(fetchedPhrase.Hash);
-
-          // expand next nonterminal symbols
-          int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
-          NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
-
-          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
-            SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
-            newPhrase.AddRange(currPhrase);
-            newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
-            newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
-
-            Expansions++;
-            if (newPhrase.Count <= MaxTreeSize) {
-              var phraseHash = Grammar.CalcHashCode(newPhrase);
-#if DEBUG
-              LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} -> {phraseHash} [label=\"{expandedSymbol.StringRepresentation} + &rarr; {productionAlternative}\"];");
-#endif
-              if (newPhrase.IsSentence()) {
-                // Sentence was generated.
-                SaveToAllSentences(phraseHash, newPhrase);
-
-                if (!DistinctSentences.ContainsKey(phraseHash) || DistinctSentences[phraseHash].Count > newPhrase.Count) {
-                  if (DistinctSentences.ContainsKey(phraseHash)) EqualGeneratedSentences++; // for analysis only
-
-                  DistinctSentences[phraseHash] = newPhrase;
-                  EvaluateSentence(newPhrase);
-
-#if DEBUG
-                  LogSearchGraph(dotFileTrace, $"{phraseHash} [label=\"{Grammar.PostfixToInfixParser(newPhrase)}\", style=\"filled\", fillcolor=\"#f79423\", color=\"#f79423\"];");
-#endif
-                }
-                UpdateView();
-
-              } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
-                OpenPhrases.Store(phraseHash, newPhrase);
+      OpenPhrases.Store(phrase0Hash, phrase0);
+      while (OpenPhrases.Count > 0) {
+        if (cancellationToken.IsCancellationRequested) break;
+
+        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
+        SymbolString currPhrase = fetchedPhrase.SymbolString;
+
+        OnPhraseFetched(fetchedPhrase.Hash, currPhrase);
+
+        ArchivedPhrases.Add(fetchedPhrase.Hash);
+
+        // expand next nonterminal symbols
+        int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
+        NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
+
+        foreach (Production productionAlternative in expandedSymbol.Alternatives) {
+          PhraseExpansionCount++;
+
+          SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
+          newPhrase.AddRange(currPhrase);
+          newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
+          newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
+
+          if (newPhrase.Count <= MaxTreeSize) {
+            var phraseHash = Grammar.CalcHashCode(newPhrase);
+
+            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
+
+            if (newPhrase.IsSentence()) {
+              AllGeneratedSentencesCount++;
+
+              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
+
+              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count) {
+                if (DistinctSentencesLength.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
+
+                DistinctSentencesLength[phraseHash] = newPhrase.Count;
+                EvaluateSentence(newPhrase);
+
+                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
               }
+              UpdateView();
+
+            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
+              OpenPhrases.Store(phraseHash, newPhrase);
             }
           }
         }
-#if DEBUG
-        // Overwrite formatting of start search node and best found solution.
-        //LogSearchGraph(dotFileTrace, $"{Grammar.CalcHashCode(BestTrainingSentence)} [label=\"{Grammar.PostfixToInfixParser(BestTrainingSentence)}\", shape=Mcircle, style=\"filled,bold\"];");
-        LogSearchGraph(dotFileTrace, $"{phrase0Hash} [label=\"{Grammar.PostfixToInfixParser(phrase0)}\", shape=doublecircle];}}");
-        dotFileTrace.Flush();
-#endif
       }
 
@@ -182 +196 @@
     }
 
-    // Store sentence to "MultiDictionary"
-    private void SaveToAllSentences(int hash, SymbolString sentence) {
-      if (AllSentences.ContainsKey(hash))
-        AllSentences[hash].Add(sentence);
-      else
-        AllSentences[hash] = new List<SymbolString> { sentence }; //TODO: here we store all sentences even if they have the same hash value, this is not strictly necessary
-    }
-
-#region Evaluation of generated models.
+    #region Evaluation of generated models.
 
     // Evaluate sentence within an algorithm run.
@@ -198 +204 @@
         Problem.ProblemData.TargetVariable,
         tree,
-        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+        expressionTreeLinearInterpreter);
 
       var probData = Problem.ProblemData;
@@ -214 +220 @@
     }
 
-#endregion
-
-#region Visualization in HL
+    #endregion
+
+    #region Visualization in HL
     // Initialize entries in result set.
     private void InitResults() {
@@ -228 +234 @@
       Results.Add(new Result(DistinctSentencesName, new IntValue(0)));
       Results.Add(new Result(PhraseExpansionsName, new IntValue(0)));
-      Results.Add(new Result(GeneratedEqualSentencesName, new IntValue(0)));
-      Results.Add(new Result(AverageTreeLengthName, new DoubleValue(1.0)));
+      Results.Add(new Result(OverwrittenSentencesName, new IntValue(0)));
+      Results.Add(new Result(AverageSentenceLengthName, new DoubleValue(1.0)));
     }
 
@@ -238 +244 @@
 
       if (force || updates % GuiUpdateInterval == 1) {
-        var allGeneratedEnum = AllSentences.Values.SelectMany(x => x).ToArray();
         ((IntValue)Results[GeneratedPhrasesName].Value).Value = ArchivedPhrases.Count;
         ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
-        ((IntValue)Results[GeneratedSentencesName].Value).Value = allGeneratedEnum.Length;
-        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentences.Count;
-        ((IntValue)Results[PhraseExpansionsName].Value).Value = Expansions;
-        ((IntValue)Results[GeneratedEqualSentencesName].Value).Value = EqualGeneratedSentences;
-        ((DoubleValue)Results[AverageTreeLengthName].Value).Value = allGeneratedEnum.Select(sentence => sentence.Count).Average();
+        ((IntValue)Results[GeneratedSentencesName].Value).Value = AllGeneratedSentencesCount;
+        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesLength.Count;
+        ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
+        ((DoubleValue)Results[AverageSentenceLengthName].Value).Value = DistinctSentencesLength.Select(pair => pair.Value).Average();
+        ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
       }
     }
@@ -259 +264 @@
       IRegressionSolution bestTrainingSolution = new RegressionSolution(model, Problem.ProblemData);
       Results.AddOrUpdateResult(BestTrainingSolutionName, bestTrainingSolution);
-
-      // Print generated sentences.
-      string[,] sentencesMatrix = new string[AllSentences.Values.SelectMany(x => x).Count(), 3];
-
-      int i = 0;
-      foreach (var sentenceSet in AllSentences) {
-        foreach (var sentence in sentenceSet.Value) {
-          sentencesMatrix[i, 0] = sentence.ToString();
-          sentencesMatrix[i, 1] = Grammar.PostfixToInfixParser(sentence).ToString();
-          sentencesMatrix[i, 2] = sentenceSet.Key.ToString();
-          i++;
+    }
+    #endregion
+
+    #region events
+    private void AnalyzersOnCheckedItemsChanged(object sender, CollectionItemsChangedEventArgs<IGrammarEnumerationAnalyzer> collectionItemsChangedEventArgs) {
+      foreach (IGrammarEnumerationAnalyzer grammarEnumerationAnalyzer in collectionItemsChangedEventArgs.Items) {
+        if (Analyzers.ItemChecked(grammarEnumerationAnalyzer)) {
+          grammarEnumerationAnalyzer.Register(this);
+        } else {
+          grammarEnumerationAnalyzer.Deregister(this);
         }
       }
-      Results.Add(new Result("All generated sentences", new StringMatrix(sentencesMatrix)));
-
-      string[,] distinctSentencesMatrix = new string[DistinctSentences.Count, 3];
-      i = 0;
-      foreach (KeyValuePair<int, SymbolString> distinctSentence in DistinctSentences) {
-        distinctSentencesMatrix[i, 0] = distinctSentence.Key.ToString();
-        distinctSentencesMatrix[i, 1] = Grammar.PostfixToInfixParser(distinctSentence.Value).ToString();
-        distinctSentencesMatrix[i, 2] = distinctSentence.Key.ToString();
-        i++;
-      }
-      Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentencesMatrix)));
-    }
-
-    private void LogSearchGraph(TraceListener listener, string msg) {
-      listener.Write(msg);
-    }
-#endregion
+    }
+
+    public event EventHandler<PhraseEventArgs> PhraseFetched;
+    private void OnPhraseFetched(int hash, SymbolString symbolString) {
+      if (PhraseFetched != null) {
+        PhraseFetched(this, new PhraseEventArgs(hash, symbolString));
+      }
+    }
+
+    public event EventHandler<PhraseAddedEventArgs> PhraseDerived;
+    private void OnPhraseDerived(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
+      if (PhraseDerived != null) {
+        PhraseDerived(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
+      }
+    }
+
+    public event EventHandler<PhraseAddedEventArgs> SentenceGenerated;
+    private void OnSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
+      if (SentenceGenerated != null) {
+        SentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
+      }
+    }
+
+    public event EventHandler<PhraseAddedEventArgs> DistinctSentenceGenerated;
+    private void OnDistinctSentenceGenerated(int parentHash, SymbolString parentSymbolString, int addedHash, SymbolString addedSymbolString, Symbol expandedSymbol, Production expandedProduction) {
+      if (DistinctSentenceGenerated != null) {
+        DistinctSentenceGenerated(this, new PhraseAddedEventArgs(parentHash, parentSymbolString, addedHash, addedSymbolString, expandedSymbol, expandedProduction));
+      }
+    }
+
+    #endregion
 
   }
+
+  #region events for analysis
+
+  public class PhraseEventArgs : EventArgs {
+    public int Hash { get; }
+
+    public SymbolString Phrase { get; }
+
+    public PhraseEventArgs(int hash, SymbolString phrase) {
+      Hash = hash;
+      Phrase = phrase;
+    }
+  }
+
+  public class PhraseAddedEventArgs : EventArgs {
+    public int ParentHash { get; }
+    public int NewHash { get; }
+
+    public SymbolString ParentPhrase { get; }
+    public SymbolString NewPhrase { get; }
+
+    public Symbol ExpandedSymbol { get; }
+
+    public Production ExpandedProduction { get; }
+
+    public PhraseAddedEventArgs(int parentHash, SymbolString parentPhrase, int newHash, SymbolString newPhrase, Symbol expandedSymbol, Production expandedProduction) {
+      ParentHash = parentHash;
+      ParentPhrase = parentPhrase;
+      NewHash = newHash;
+      NewPhrase = newPhrase;
+      ExpandedSymbol = expandedSymbol;
+      ExpandedProduction = expandedProduction;
+    }
+  }
+
+  #endregion
 }