Changeset 14427

Timestamp:

11/28/16 17:55:52 (8 years ago)

Author:

bburlacu

Message:

#1772: Extract common methods (used by the schema creator and the schema frequency analyzer) in static SchemaUtil class. Make AnyNode constructor public.

Location:

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• Symbols/Wildcards/AnyNodeSymbol.cs (modified) (1 diff)
• Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs (modified) (8 diffs)
• Tracking/SchemaDiversification/SchemaCreator.cs (modified) (5 diffs)
• Tracking/SchemaDiversification/SchemaEvaluator.cs (modified) (1 diff)
• Tracking/SchemaDiversification/SchemaUtil.cs (added)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -317 +317 @@
     <Compile Include="Tracking\SchemaDiversification\SchemaEvaluator.cs" />
     <Compile Include="Tracking\SchemaDiversification\SchemaCreator.cs" />
+    <Compile Include="Tracking\SchemaDiversification\SchemaUtil.cs" />
     <Compile Include="Tracking\SchemaDiversification\UpdateQualityOperator.cs" />
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs" />

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/Wildcards/AnyNodeSymbol.cs

@@ -41 +41 @@
     }
 
-    private AnyNodeSymbol() : base("=", "A wildcard symbol that can match any node of the same type (function or leaf node)") { }
+    public AnyNodeSymbol() : base("=", "A wildcard symbol that can match any node of the same type (function or leaf node)") { }
 
     public AnyNodeSymbol(int minimumArity, int maximumArity)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using System.Threading.Tasks;
 using HeuristicLab.Common;
@@ -34 +33 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tracking.Analyzers {
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [Item("SymbolicDataAnalysisSchemaFrequencyAnalyzer", "An analyzer which counts schema frequencies in the population.")]
   [StorableClass]
@@ -157 +156 @@
       var generation = Generation.Value;
 
-      var population = PopulationGraph.GetByRank(generation).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
+      var population = PopulationGraph.Vertices.Where(x => x.InDegree == 2 && x.Rank > generation - 1).ToList();
       var vertices = population.Where(x => x.InDegree == 2).OrderByDescending(x => x.Quality).ToList();
       ResultCollection resultCollection;
@@ -182 +181 @@
       }
       var schemas = SchemaCreator.GenerateSchemas(vertices, MinimumSchemaLength, StrictSchemaMatching).ToList();
-      var schemaStrings = schemas.Select(x => SubtreeToString(x.Root.GetSubtree(0).GetSubtree(0), StrictSchemaMatching)).ToList();
+      var schemaStrings = schemas.Select(x => x.Root.GetSubtree(0).GetSubtree(0).FormatToString(StrictSchemaMatching)).ToList();
       int[][] matchingIndices;
       if (ExecuteInParallel) {
@@ -188 +187 @@
         Parallel.For(0, schemas.Count, new ParallelOptions { MaxDegreeOfParallelism = MaximumDegreeOfParallelism }, i => {
           var schema = schemas[i];
-          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v].Root, schema.Root)).ToArray();
+          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v], schema)).ToArray();
         });
       } else {
-        matchingIndices = schemas.Select(x => Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v].Root, x.Root)).ToArray()).ToArray();
+        matchingIndices = schemas.Select(x => Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v], x)).ToArray()).ToArray();
       }
 
@@ -230 +229 @@
       if (!schemaStatistics.Any()) return base.Apply(); // shouldn't ever happen
       var columnNames = new[] { "Count", "Avg Quality", "Avg Length", "Avg Genotype Similarity", "Avg Phenotype Similarity", "Avg Population Quality" };
-      var mostFrequent = new DoubleMatrix(schemaStatistics.Count, schemaStatistics[0].Item2.Length);
-      mostFrequent.SortableView = true;
+      var mostFrequent = new DoubleMatrix(schemaStatistics.Count, schemaStatistics[0].Item2.Length) {
+        SortableView = true
+      };
       schemaStatistics.Sort((a, b) => { if (a.Item2[0].Equals(b.Item2[0])) return b.Item2[1].CompareTo(a.Item2[1]); return b.Item2[0].CompareTo(a.Item2[0]); });
-      mostFrequentPerGeneration.Add(new Tuple<string, double[]>(schemaStatistics[0].Item1, new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray()));
+      mostFrequentPerGeneration.Add(Tuple.Create(schemaStatistics[0].Item1, new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray()));
       mostFrequent.RowNames = schemaStatistics.Select(x => x.Item1);
       mostFrequent.ColumnNames = columnNames;
@@ -301 +301 @@
         for (int j = i + 1; j < indices.Length; ++j) {
           var b = indices[j];
-          if (double.IsNaN(similarityMatrix[a, b])) similarityMatrix[a, b] = similarityFunction(trees[a], trees[b]);
+          if (double.IsNaN(similarityMatrix[a, b]))
+            similarityMatrix[a, b] = similarityFunction(trees[a], trees[b]);
           agg += similarityMatrix[a, b];
         }
@@ -307 +308 @@
       return agg / count;
     }
-
-    private static string SubtreeToString(ISymbolicExpressionTreeNode node, bool strict = false) {
-      StringBuilder strBuilder = new StringBuilder();
-      // internal nodes or leaf nodes?
-      if (node is AnySubtree)
-        return "# ";
-
-      if (node.SubtreeCount > 0) {
-        strBuilder.Append("(");
-        // symbol on same line as '('
-        string label = string.Empty;
-        if (node is AnyNode)
-          label = "=";
-        else {
-          var name = node.Symbol.Name;
-          label = ShortNames.ContainsKey(name) ? ShortNames[name] : name;
-        }
-        strBuilder.Append(label + " ");
-        // each subtree expression on a new line
-        // and closing ')' also on new line
-        foreach (var subtree in node.Subtrees) {
-          strBuilder.Append(SubtreeToString(subtree, strict));
-        }
-        strBuilder.Append(") ");
-      } else {
-        // symbol in the same line with as '(' and ')'
-        var v = node as VariableTreeNode;
-        var c = node as ConstantTreeNode;
-        var w = node as AnyNode; // wildcard
-        string label = string.Empty;
-        if (w != null)
-          label = "=";
-        else if (v != null)
-          label = strict ? string.Format("{0:0.00}_{1}", v.Weight, v.VariableName) : string.Format("{0}", v.VariableName);
-        else if (c != null)
-          label = strict ? string.Format("{0:0.00}", c.Value) : "C";
-        strBuilder.Append(label);
-        if (node.Parent != null && node != node.Parent.Subtrees.Last())
-          strBuilder.Append(" ");
-      }
-      return strBuilder.ToString();
-    }
   }
 }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -202 +201 @@
                      select v;
 
-      var schemas = new List<ISymbolicExpressionTree>(GenerateSchemas(vertices, MinimumSchemaLength, StrictSchemaMatching));
+      var schemas = GenerateSchemas(vertices, MinimumSchemaLength, StrictSchemaMatching).ToList();
 
       #region create schemas and add subscopes representing the individuals
@@ -226 +225 @@
     public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, bool strict = true) {
       var anySubtreeSymbol = new AnySubtreeSymbol();
-      //            var anyNodeSymbol = new AnyNodeSymbol();
-      var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
+      var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count());
       var hash = new HashSet<string>();
-      //      var formatter = new SymbolicExpressionTreeStringFormatter { Indent = false, AppendNewLines = false };
       foreach (var g in groups) {
         var parent = g.Key;
@@ -237 +234 @@
         var schema = (ISymbolicExpressionTree)parent.Data.Clone();
         var nodes = schema.IterateNodesPrefix().ToList();
-        var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
-        var indices = (from arc in arcs
-                       let fragment = (IFragment<ISymbolicExpressionTreeNode>)arc.Data
-                       select fragment.Index1).Distinct().ToArray();
-        var levels = indices.Select(x => schema.Root.GetBranchLevel(nodes[x])).ToArray();
-        Array.Sort(levels, indices);
-        // order nodes by their depth so that cutpoints are replaced with wildcards from the bottom up
-        var nodesToReplace = indices.Select(x => nodes[x]).ToList();
-        for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
-          var node = nodesToReplace[i];
-
+        var fragments = g.Select(x => x.InArcs.Last().Data).Where(x => x != null).Cast<IFragment<ISymbolicExpressionTreeNode>>();
+        var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
+        foreach (var i in indices) {
+          var node = nodes[i];
           // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
-          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
-            continue;
-
-          var replacement = anySubtreeSymbol.CreateTreeNode();
-          ReplaceSubtree(node, replacement, false);
+          //          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
+          //            continue;
+          ISymbolicExpressionTreeNode replacement;
+          if (node.SubtreeCount > 0) {
+            var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
+            replacement = anyNodeSymbol.CreateTreeNode();
+          } else {
+            replacement = anySubtreeSymbol.CreateTreeNode();
+          }
+          SchemaUtil.ReplaceSubtree(node, replacement, true);
           //          var replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MinimumArity).CreateTreeNode();
           //          ReplaceSubtree(node, replacement, true);
@@ -259 +254 @@
         }
         if (replaced) {
-          //          var str = formatter.Format(schema.Root.GetSubtree(0).GetSubtree(0));
-          var str = SubtreeToString(schema.Root.GetSubtree(0).GetSubtree(0), strict);
-          if (hash.Contains(str)) continue;
-          yield return schema;
-          hash.Add(str);
+          var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
+          if (hash.Add(str))
+            yield return schema;
         }
       }
     }
-
-    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement, bool preserveChildren = true) {
-      var parent = original.Parent;
-      if (parent == null)
-        throw new ArgumentException("Parent cannot be null for node " + original);
-      var index = parent.IndexOfSubtree(original);
-      parent.RemoveSubtree(index);
-      parent.InsertSubtree(index, replacement);
-
-      if (preserveChildren) {
-        var subtrees = original.Subtrees.ToList();
-
-        for (int i = subtrees.Count - 1; i >= 0; --i)
-          original.RemoveSubtree(i);
-
-        for (int i = 0; i < subtrees.Count; ++i) {
-          replacement.AddSubtree(subtrees[i]);
-        }
-      }
-    }
-
-    private static string SubtreeToString(ISymbolicExpressionTreeNode node, bool strict = false) {
-      StringBuilder strBuilder = new StringBuilder();
-      // internal nodes or leaf nodes?
-      if (node is AnySubtree)
-        return "# ";
-
-      if (node.SubtreeCount > 0) {
-        strBuilder.Append("(");
-        // symbol on same line as '('
-        string label = string.Empty;
-        if (node is AnyNode)
-          label = "=";
-        else {
-          label = node.Symbol.Name;
-        }
-        strBuilder.Append(label + " ");
-        // each subtree expression on a new line
-        // and closing ')' also on new line
-        foreach (var subtree in node.Subtrees) {
-          strBuilder.Append(SubtreeToString(subtree, strict));
-        }
-        strBuilder.Append(") ");
-      } else {
-        // symbol in the same line with as '(' and ')'
-        var v = node as VariableTreeNode;
-        var c = node as ConstantTreeNode;
-        var w = node as AnyNode; // wildcard
-        string label = string.Empty;
-        if (w != null)
-          label = "=";
-        else if (v != null)
-          label = strict ? string.Format("{0:0.00}_{1}", v.Weight, v.VariableName) : string.Format("{0}", v.VariableName);
-        else if (c != null)
-          label = strict ? string.Format("{0:0.00}", c.Value) : "C";
-        strBuilder.Append(label);
-        if (node.Parent != null && node != node.Parent.Subtrees.Last())
-          strBuilder.Append(" ");
-        //strBuilder.Append(")");
-      }
-      return strBuilder.ToString();
-    }
   }
 }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

@@ -234 +234 @@
         var t = trees[i];
         var tRoot = t.Root.GetSubtree(0).GetSubtree(0);
-        if (t.Length < s.Length || !qm.Comparer.Equals(tRoot, sRoot)) continue;
+        if (t.Length < s.Length || !qm.EqualityComparer.Equals(tRoot, sRoot)) continue;
         filtered.Add(i);
       }