Changeset 9419 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers

Timestamp:

05/02/13 13:18:57 (11 years ago)

Author:

bburlacu

Message:

#1772: Refactoring of directed graph components, added code for correctly serializing vertices and edges. Added specific building blocks analyzers and new population diversity analyzer which correctly integrates with the parallel engine.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers

Files:

• BuildingBlocks (added)
• BuildingBlocks/Poly10BuildingBlocksAnalyzer.cs (added)
• BuildingBlocks/RelevantBuildingBlocksAnalyzer.cs (added)
• SymbolicExpressionTreeFrequentPatternsAnalyzer.cs (modified) (3 diffs)
• SymbolicExpressionTreePopulationDiversityAnalyzer.cs (modified) (10 diffs)
• SymbolicExpressionTreeShapeAnalyzer.cs (copied) (copied from branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs) (8 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFrequentPatternsAnalyzer.cs

@@ -204 +204 @@
         var grammar = trees[0].Root.Grammar;
 
-        // bring trees to a canonical form to eliminate permuted fragments
-        var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
-        foreach (var t in trees)
-          canonicalSorter.SortSubtrees(t);
-
         var graph = Results["SymbolGraph"].Value as SymbolGraph;
 
@@ -217 +212 @@
         // subtree-sort fragments to bring them to a canonical form
         // var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
-        foreach (var fragment in fragments)
-          canonicalSorter.SortSubtrees(fragment.Root);
 
         if (!Results.ContainsKey(CommonFragmentsParameterName)) {
@@ -342 +335 @@
         int minCount = grammar.GetMinimumSubtreeCount(node.Symbol);
         var arity = random.Next(enforceGrammarArity ? minCount : 1, maxCount + 1);
-        var possibleChildConnections = new List<Arc>();
+        var possibleChildConnections = new List<SymbolArc>();
 
         if (depthLimit <= 2 || lengthLimit <= maxCount) { // if we are near the depth limit then we want to add leafs on the next level

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreePopulationDiversityAnalyzer.cs

@@ -44 +44 @@
   public sealed class SymbolicExpressionTreePopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer {
     #region Parameter names
+    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
     private const string UpdateIntervalParameterName = "UpdateInterval";
@@ -56 +57 @@
     private const string SortSubtreesParameterName = "SortSubtrees";
     private const string SimilarityValuesParmeterName = "Similarity";
-    // population graph
-    private const string PopulationGraphParameterName = "PopulationGraph";
     // clone map
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
@@ -64 +63 @@
 
     #region Parameters
+    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
+    }
 
     public ValueParameter<IntValue> UpdateIntervalParameter {
@@ -116 +118 @@
 
     #region Parameter properties
+    public IntValue MaximumSymbolicExpressionTreeDepth {
+      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
+    }
 
     public IntValue UpdateInterval {
@@ -164 +169 @@
       Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
       Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
-      Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names."));
-      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights."));
-      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values."));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
       Parameters.Add(new ValueParameter<BoolValue>(SortSubtreesParameterName, "Specifies whether the subtrees of a tree should be sorted before comparison."));
       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
       Parameters.Add(new ValueParameter<BoolValue>(StoreHistoryParameterName, "True if the tree lengths history of the population should be stored.", new BoolValue(false)));
       Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
+      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
       UpdateCounterParameter.Hidden = true;
       UpdateIntervalParameter.Hidden = true;
@@ -177 +183 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
+      if (!Parameters.ContainsKey(MaximumSymbolicExpressionTreeDepthParameterName)) {
+        Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
+      }
     }
 
     #region IStatefulItem members
     public override void InitializeState() {
+      UpdateCounter.Value = 0;
       base.InitializeState();
-      UpdateCounter.Value = 0;
-    }
-
-    public override void ClearState() {
-      base.ClearState();
-      UpdateCounter.Value = 0;
     }
     #endregion
@@ -199 +203 @@
         UpdateCounter.Value++;
         if (UpdateCounter.Value != UpdateInterval.Value) return base.Apply();
-
         UpdateCounter.Value = 0;
         var trees = SymbolicExpressionTreeParameter.ActualValue.ToList();
@@ -208 +211 @@
 
         SimilarityParameter.ActualValue = new DoubleValue();
+        // needed only with the old (and inefficient) geneticitem-based similarity measure
+        //        var geneticItems = trees.ToDictionary(tree => tree, tree => tree.GetGeneticItems(1, MaximumSymbolicExpressionTreeDepth.Value - 2).ToArray());
 
         var comp = new SymbolicExpressionTreeNodeSimilarityComparer {
@@ -217 +222 @@
         var operations = new OperationCollection { Parallel = true };
         foreach (var tree in trees) {
-          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator { CurrentSymbolicExpressionTree = tree, SimilarityComparer = comp };
+          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator { CurrentSymbolicExpressionTree = tree, SimilarityComparer = comp, MaximumTreeDepth = MaximumSymbolicExpressionTreeDepth.Value };
           var operation = ExecutionContext.CreateChildOperation(op, ExecutionContext.Scope);
           operations.Add(operation);
@@ -256 +261 @@
       relativeSelectionCountsTable.Rows["SelectedIndividuals"].Values.Add(relativeSelectionCount);
 
-      // build a selection frequencies histogram
-      var graph = (SymbolicExpressionTreeGenealogyGraph)results[PopulationGraphParameterName].Value;
-      // get graph nodes corresponding to individuals of the previous generation
-      var prevGen = graph.Nodes.Where(node => node.Rank.IsAlmost(Generations.Value - 1)).OrderByDescending(n => n.Quality).ToList();
-      var frequencies = new double[SymbolicExpressionTreeParameter.ActualValue.Length];
-      for (int i = 0; i != prevGen.Count; ++i) {
-        int selFreq = GlobalCloneMap.Values.Count(t => t == prevGen[i].SymbolicExpressionTree);
-        frequencies[i] = selFreq;
-      }
-      DataTable selectionFrequenciesTable;
-      if (!results.ContainsKey("SelectionFrequencies")) {
-        selectionFrequenciesTable = new DataTable("Selection Frequencies") { VisualProperties = { YAxisTitle = "Selection Count" } };
-        results.Add(new Result("SelectionFrequencies", selectionFrequenciesTable));
-      }
-      selectionFrequenciesTable = (DataTable)results["SelectionFrequencies"].Value;
-      DataRow histoRow;
-      if (!selectionFrequenciesTable.Rows.ContainsKey("SelectionFrequencies")) {
-        histoRow = new DataRow("SelectionFrequencies") { VisualProperties = { StartIndexZero = true } };
-        selectionFrequenciesTable.Rows.Add(histoRow);
-      }
-      histoRow = selectionFrequenciesTable.Rows["SelectionFrequencies"];
-      histoRow.Values.Replace(frequencies);
-
-      bool storeHistory = StoreHistory.Value;
-      if (storeHistory) {
-        DataTableHistory selectionFrequenciesHistory;
-        if (!results.ContainsKey("SelectionFrequenciesHistory")) {
-          selectionFrequenciesHistory = new DataTableHistory();
-          results.Add(new Result("SelectionFrequenciesHistory", selectionFrequenciesHistory));
-        }
-        selectionFrequenciesHistory = (DataTableHistory)results["SelectionFrequenciesHistory"].Value;
-        selectionFrequenciesHistory.Add((DataTable)selectionFrequenciesTable.Clone());
-      }
       return base.Apply();
     }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeShapeAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -30 +29 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.DataAnalysis;
-using HeuristicLab.Problems.DataAnalysis.Symbolic;
-// type definitions for convenience
-using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
-using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
-using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
 
 namespace HeuristicLab.EvolutionaryTracking {
@@ -44 +37 @@
   [Item("SymbolicExpressionTreeFragmentsAnalyzer", "An operator that provides statistics about crossover fragments")]
   [StorableClass]
-  public abstract class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
+  public sealed class SymbolicExpressionTreeShapeAnalyzer : SingleSuccessorOperator, IAnalyzer {
     #region Parameter names
-    protected const string UpdateIntervalParameterName = "UpdateInterval";
-    protected const string UpdateCounterParameterName = "UpdateCounter";
-    protected const string ResultsParameterName = "Results";
-    protected const string SecondaryTraceMapParameterName = "SecondaryTraceMap";
-    protected const string SecondaryFragmentMapParameterName = "SecondaryFragmentMap";
-    protected const string SecondaryCloneMapParameterName = "SecondaryCloneMap";
-    protected const string GlobalTraceMapParameterName = "GlobalTraceMap";
-    protected const string GlobalTraceMapParameterDescription = "Global map of trees and their parents.";
-    protected const string GlobalCloneMapParameterName = "GlobalCloneMap";
-    protected const string GlobalCloneMapParameterDescription = "Global map of trees and their clones";
-    protected const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
-    protected const string GlobalFragmentMapParameterDescription = "Global map of trees and their respective fragments.";
-    protected const string GenerationsParameterName = "Generations";
-    protected const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
-    protected const string SymbolicRegressionProblemDataParameterName = "ProblemData";
+    private const string UpdateIntervalParameterName = "UpdateInterval";
+    private const string UpdateCounterParameterName = "UpdateCounter";
+    private const string ResultsParameterName = "Results";
+    private const string GenerationsParameterName = "Generations";
     #endregion
-
-    // impact values calculator
-    private readonly SymbolicRegressionSolutionImpactValuesCalculator calculator = new SymbolicRegressionSolutionImpactValuesCalculator();
 
     #region Parameter properties
@@ -78 +57 @@
     public LookupParameter<IntValue> GenerationsParameter {
       get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
-    }
-    // tracking structures
-    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
-      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
-    }
-    // auxiliary structures for tracking fragments and individuals from the previous generation
-    // (this is needed because tracking is done in connection to the current generation, i.e., for 
-    // counting "successful" offspring and fragments
-    public LookupParameter<TraceMapType> SecondaryTraceMapParameter {
-      get { return (LookupParameter<TraceMapType>)Parameters[SecondaryTraceMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> SecondaryFragmentMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[SecondaryFragmentMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> SecondaryCloneMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[SecondaryCloneMapParameterName]; }
-    }
-    // problem data, interpreter and evaluator
-    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
-      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
-    }
-    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
-      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
     }
     #endregion
@@ -123 +73 @@
       get { return ResultsParameter.ActualValue; }
     }
-    public CloneMapType GlobalCloneMap {
-      get { return GlobalCloneMapParameter.ActualValue; }
-    }
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-    public TraceMapType SecondaryTraceMap {
-      get { return SecondaryTraceMapParameter.ActualValue; }
-      set { SecondaryTraceMapParameter.ActualValue = value; }
-    }
-    public CloneMapType SecondaryFragmentMap {
-      get { return SecondaryFragmentMapParameter.ActualValue; }
-      set { SecondaryFragmentMapParameter.ActualValue = value; }
-    }
-    public CloneMapType SecondaryCloneMap {
-      get { return SecondaryCloneMapParameter.ActualValue; }
-      set { SecondaryCloneMapParameter.ActualValue = value; }
-    }
-    public CloneMapType GlobalFragmentMap {
-      get { return GlobalFragmentMapParameter.ActualValue; }
-    }
     public IntValue Generations {
       get { return GenerationsParameter.ActualValue; }
-    }
-    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
-      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
-    }
-    public RegressionProblemData SymbolicRegressionProblemData {
-      get { return SymbolicRegressionProblemDataParameter.ActualValue; }
     }
     #endregion
 
     [StorableConstructor]
-    protected SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeShapeAnalyzer(bool deserializing) : base(deserializing) { }
 
-    protected SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner) : base(original, cloner) { }
+    private SymbolicExpressionTreeShapeAnalyzer(SymbolicExpressionTreeShapeAnalyzer original, Cloner cloner) : base(original, cloner) { }
 
-    protected SymbolicExpressionTreeFragmentsAnalyzer()
+    private SymbolicExpressionTreeShapeAnalyzer()
       : base() {
       #region Add parameters
@@ -166 +89 @@
       Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
       Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
-      // tracking
-      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, GlobalTraceMapParameterDescription));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, GlobalCloneMapParameterDescription));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, GlobalFragmentMapParameterDescription));
-      // secondary tracking 
-      Parameters.Add(new LookupParameter<TraceMapType>(SecondaryTraceMapParameterName, GlobalTraceMapParameterDescription));
-      Parameters.Add(new LookupParameter<CloneMapType>(SecondaryCloneMapParameterName, GlobalCloneMapParameterDescription));
-      Parameters.Add(new LookupParameter<CloneMapType>(SecondaryFragmentMapParameterName, GlobalFragmentMapParameterDescription));
-      // impact calculation
-      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
-      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
-      // fragment statistics parameters
       Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
       Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
@@ -211 +122 @@
     #endregion
 
-    /* A small description of the way this analyzer works
-     * 
-     * We keep 3 maps in the global scope: the GlobalTraceMap, the GlobalFragmentMap and the GlobalCloneMap that are updated on each step: selection, crossover, mutation
-     * These maps provide information about the children, parents and transferred fragments as follows:
-     * 
-     * 1) GlobalCloneMap
-     *    This data structure provides the basis for tracking. In the selection step, every selected individual gets cloned and transferred into the recombination pool.
-     *    The GlobalCloneMap keeps track of clones by mapping them to the original individuals. This is an essential step for building the genealogy graph. Using this
-     *    structure we can find out how many times each individual was selected. 
-     *    The GlobalCloneMap consists of Key-Value pairs Clone->Original
-     *
-     * 2) GlobalTraceMap
-     *    Keeps information in the form of key-value pairs Child->{Parents}, where {Parents} is a set consisting of 
-     *      - one parent individual (in the case of mutation), by language abuse we say that the individual that mutation acted on is the parent,
-     *        and the resulting individual is the child
-     *      - two parent individuals (in the case of crossover), named Parent0 and Parent1. Parent0 is the individual that crossover acts on by replacing 
-     *        one of its subtrees with a compatible subtree, randomly selected from Parent1
-     *
-     *    CROSSOVER
-     *        Parent0     Parent1                                                                    {Parents}
-     *           \           /                                                                           ^
-     *            \       fragment (inserted from Parent1 into Parent0 to create the Child)              ^    [Mapping provided by the GlobalTraceMap]
-     *             \       /                                                                             ^
-     *              \     /                                                                              ^
-     *               Child                                                                             Child
-     *               
-     *    MUTATION
-     *        Parent0
-     *           |
-     *           |    [mutation acts on a random node/subtree in the 'parent' individual
-     *           |
-     *         Child
-     *         
-     *    Since crossover and mutation act on individuals in the recombination pool (which in fact are clones of individuals from the previous generation), the GlobalTraceMap
-     *    is populated with values given by the mappings in the GlobalCloneMap, so that the original parent for each child is known.
-     *    
-     *  3) GlobalFragmentMap
-     *     Keeps information in the form of Key-Value pairs about an individual and its respective fragment 
-     *     (ie., the subtree received via crossover or created/altered by mutation)
-     * */
+    public override IOperation Apply() {
 
-    public override IOperation Apply() {
-      // save the current generation so it can be compared to the following one, next time the analyzer is applied
-      SecondaryTraceMap = SecondaryTraceMap ?? new TraceMapType();
-      SecondaryCloneMap = SecondaryCloneMap ?? new CloneMapType();
-      SecondaryFragmentMap = SecondaryFragmentMap ?? new CloneMapType();
-
-      SecondaryTraceMap.Clear();
-      if (GlobalTraceMap != null)
-        foreach (var m in GlobalTraceMap)
-          SecondaryTraceMap.Add(m.Key, m.Value);
-
-      SecondaryCloneMap.Clear();
-      if (GlobalCloneMap != null)
-        foreach (var m in GlobalCloneMap)
-          SecondaryCloneMap.Add(m.Key, m.Value);
-
-      SecondaryFragmentMap.Clear();
-      if (GlobalFragmentMap != null)
-        foreach (var m in GlobalFragmentMap)
-          SecondaryFragmentMap.Add(m.Key, m.Value);
       return base.Apply();
-    }
-
-    protected virtual void InitializeParameters() {
-      #region Init parameters
-
-      #endregion
     }
 
@@ -285 +131 @@
     }
 
+    private static int PathLength(ISymbolicExpressionTree tree) {
+      return PathLength(tree.Root);
+    }
+
     private static int VisitationLength(ISymbolicExpressionTreeNode node) {
       return node.IterateNodesBreadth().Sum(n => n.GetLength());
     }
 
-    #region Similarity computations
-    /// <summary>
-    /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are. 
-    /// </summary>
-    /// <param name="fragments">The symbolic expression tree fragments</param>
-    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
-    /// <returns>The average number of similar fragments</returns>
-    private static double CalculateSimilarity(IList<IFragment> fragments, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
-      var visited = new bool[fragments.Count];
-      int groups = 0;
-      for (int i = 0; i != fragments.Count - 1; ++i) {
-        if (visited[i]) continue;
-        for (int j = i + 1; j != fragments.Count; ++j) {
-          if (visited[j]) continue;
-          if (fragments[i].Root.IsSimilarTo(fragments[j].Root, comparer))
-            visited[j] = true;
-        }
-        ++groups;
-      }
-      return (double)fragments.Count / groups;
+    private static int PathLength(ISymbolicExpressionTreeNode node) {
+      return node.IterateNodesBreadth().Sum(n => node.GetBranchLevel(n)) + 1;
     }
-    #endregion
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new SymbolicExpressionTreeShapeAnalyzer(this, cloner);
+    }
   } //SymbolicExpressionTreeFragmentsAnalyzer
 }