Changeset 9419


Ignore:
Timestamp:
05/02/13 13:18:57 (8 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
Files:
4 added
1 deleted
13 edited
3 copied
2 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFrequentPatternsAnalyzer.cs

    r9238 r9419  
    204204        var grammar = trees[0].Root.Grammar;
    205205
    206         // bring trees to a canonical form to eliminate permuted fragments
    207         var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
    208         foreach (var t in trees)
    209           canonicalSorter.SortSubtrees(t);
    210 
    211206        var graph = Results["SymbolGraph"].Value as SymbolGraph;
    212207
     
    217212        // subtree-sort fragments to bring them to a canonical form
    218213        // var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
    219         foreach (var fragment in fragments)
    220           canonicalSorter.SortSubtrees(fragment.Root);
    221214
    222215        if (!Results.ContainsKey(CommonFragmentsParameterName)) {
     
    342335        int minCount = grammar.GetMinimumSubtreeCount(node.Symbol);
    343336        var arity = random.Next(enforceGrammarArity ? minCount : 1, maxCount + 1);
    344         var possibleChildConnections = new List<Arc>();
     337        var possibleChildConnections = new List<SymbolArc>();
    345338
    346339        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

    r9296 r9419  
    4444  public sealed class SymbolicExpressionTreePopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer {
    4545    #region Parameter names
     46    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
    4647    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    4748    private const string UpdateIntervalParameterName = "UpdateInterval";
     
    5657    private const string SortSubtreesParameterName = "SortSubtrees";
    5758    private const string SimilarityValuesParmeterName = "Similarity";
    58     // population graph
    59     private const string PopulationGraphParameterName = "PopulationGraph";
    6059    // clone map
    6160    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
     
    6463
    6564    #region Parameters
     65    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
     66      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
     67    }
    6668
    6769    public ValueParameter<IntValue> UpdateIntervalParameter {
     
    116118
    117119    #region Parameter properties
     120    public IntValue MaximumSymbolicExpressionTreeDepth {
     121      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
     122    }
    118123
    119124    public IntValue UpdateInterval {
     
    164169      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
    165170      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
    166       Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names."));
    167       Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights."));
    168       Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values."));
     171      Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
     172      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
     173      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
    169174      Parameters.Add(new ValueParameter<BoolValue>(SortSubtreesParameterName, "Specifies whether the subtrees of a tree should be sorted before comparison."));
    170175      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
    171176      Parameters.Add(new ValueParameter<BoolValue>(StoreHistoryParameterName, "True if the tree lengths history of the population should be stored.", new BoolValue(false)));
    172177      Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
     178      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
    173179      UpdateCounterParameter.Hidden = true;
    174180      UpdateIntervalParameter.Hidden = true;
     
    177183    [StorableHook(HookType.AfterDeserialization)]
    178184    private void AfterDeserialization() {
     185      if (!Parameters.ContainsKey(MaximumSymbolicExpressionTreeDepthParameterName)) {
     186        Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
     187      }
    179188    }
    180189
    181190    #region IStatefulItem members
    182191    public override void InitializeState() {
     192      UpdateCounter.Value = 0;
    183193      base.InitializeState();
    184       UpdateCounter.Value = 0;
    185     }
    186 
    187     public override void ClearState() {
    188       base.ClearState();
    189       UpdateCounter.Value = 0;
    190194    }
    191195    #endregion
     
    199203        UpdateCounter.Value++;
    200204        if (UpdateCounter.Value != UpdateInterval.Value) return base.Apply();
    201 
    202205        UpdateCounter.Value = 0;
    203206        var trees = SymbolicExpressionTreeParameter.ActualValue.ToList();
     
    208211
    209212        SimilarityParameter.ActualValue = new DoubleValue();
     213        // needed only with the old (and inefficient) geneticitem-based similarity measure
     214        //        var geneticItems = trees.ToDictionary(tree => tree, tree => tree.GetGeneticItems(1, MaximumSymbolicExpressionTreeDepth.Value - 2).ToArray());
    210215
    211216        var comp = new SymbolicExpressionTreeNodeSimilarityComparer {
     
    217222        var operations = new OperationCollection { Parallel = true };
    218223        foreach (var tree in trees) {
    219           var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator { CurrentSymbolicExpressionTree = tree, SimilarityComparer = comp };
     224          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator { CurrentSymbolicExpressionTree = tree, SimilarityComparer = comp, MaximumTreeDepth = MaximumSymbolicExpressionTreeDepth.Value };
    220225          var operation = ExecutionContext.CreateChildOperation(op, ExecutionContext.Scope);
    221226          operations.Add(operation);
     
    256261      relativeSelectionCountsTable.Rows["SelectedIndividuals"].Values.Add(relativeSelectionCount);
    257262
    258       // build a selection frequencies histogram
    259       var graph = (SymbolicExpressionTreeGenealogyGraph)results[PopulationGraphParameterName].Value;
    260       // get graph nodes corresponding to individuals of the previous generation
    261       var prevGen = graph.Nodes.Where(node => node.Rank.IsAlmost(Generations.Value - 1)).OrderByDescending(n => n.Quality).ToList();
    262       var frequencies = new double[SymbolicExpressionTreeParameter.ActualValue.Length];
    263       for (int i = 0; i != prevGen.Count; ++i) {
    264         int selFreq = GlobalCloneMap.Values.Count(t => t == prevGen[i].SymbolicExpressionTree);
    265         frequencies[i] = selFreq;
    266       }
    267       DataTable selectionFrequenciesTable;
    268       if (!results.ContainsKey("SelectionFrequencies")) {
    269         selectionFrequenciesTable = new DataTable("Selection Frequencies") { VisualProperties = { YAxisTitle = "Selection Count" } };
    270         results.Add(new Result("SelectionFrequencies", selectionFrequenciesTable));
    271       }
    272       selectionFrequenciesTable = (DataTable)results["SelectionFrequencies"].Value;
    273       DataRow histoRow;
    274       if (!selectionFrequenciesTable.Rows.ContainsKey("SelectionFrequencies")) {
    275         histoRow = new DataRow("SelectionFrequencies") { VisualProperties = { StartIndexZero = true } };
    276         selectionFrequenciesTable.Rows.Add(histoRow);
    277       }
    278       histoRow = selectionFrequenciesTable.Rows["SelectionFrequencies"];
    279       histoRow.Values.Replace(frequencies);
    280 
    281       bool storeHistory = StoreHistory.Value;
    282       if (storeHistory) {
    283         DataTableHistory selectionFrequenciesHistory;
    284         if (!results.ContainsKey("SelectionFrequenciesHistory")) {
    285           selectionFrequenciesHistory = new DataTableHistory();
    286           results.Add(new Result("SelectionFrequenciesHistory", selectionFrequenciesHistory));
    287         }
    288         selectionFrequenciesHistory = (DataTableHistory)results["SelectionFrequenciesHistory"].Value;
    289         selectionFrequenciesHistory.Add((DataTable)selectionFrequenciesTable.Clone());
    290       }
    291263      return base.Apply();
    292264    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeShapeAnalyzer.cs

    r9082 r9419  
    2020#endregion
    2121
    22 using System.Collections.Generic;
    2322using System.Linq;
    2423using HeuristicLab.Common;
     
    3029using HeuristicLab.Parameters;
    3130using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    32 using HeuristicLab.Problems.DataAnalysis;
    33 using HeuristicLab.Problems.DataAnalysis.Symbolic;
    34 // type definitions for convenience
    35 using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
    36 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    37 using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
    3831
    3932namespace HeuristicLab.EvolutionaryTracking {
     
    4437  [Item("SymbolicExpressionTreeFragmentsAnalyzer", "An operator that provides statistics about crossover fragments")]
    4538  [StorableClass]
    46   public abstract class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
     39  public sealed class SymbolicExpressionTreeShapeAnalyzer : SingleSuccessorOperator, IAnalyzer {
    4740    #region Parameter names
    48     protected const string UpdateIntervalParameterName = "UpdateInterval";
    49     protected const string UpdateCounterParameterName = "UpdateCounter";
    50     protected const string ResultsParameterName = "Results";
    51     protected const string SecondaryTraceMapParameterName = "SecondaryTraceMap";
    52     protected const string SecondaryFragmentMapParameterName = "SecondaryFragmentMap";
    53     protected const string SecondaryCloneMapParameterName = "SecondaryCloneMap";
    54     protected const string GlobalTraceMapParameterName = "GlobalTraceMap";
    55     protected const string GlobalTraceMapParameterDescription = "Global map of trees and their parents.";
    56     protected const string GlobalCloneMapParameterName = "GlobalCloneMap";
    57     protected const string GlobalCloneMapParameterDescription = "Global map of trees and their clones";
    58     protected const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    59     protected const string GlobalFragmentMapParameterDescription = "Global map of trees and their respective fragments.";
    60     protected const string GenerationsParameterName = "Generations";
    61     protected const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    62     protected const string SymbolicRegressionProblemDataParameterName = "ProblemData";
     41    private const string UpdateIntervalParameterName = "UpdateInterval";
     42    private const string UpdateCounterParameterName = "UpdateCounter";
     43    private const string ResultsParameterName = "Results";
     44    private const string GenerationsParameterName = "Generations";
    6345    #endregion
    64 
    65     // impact values calculator
    66     private readonly SymbolicRegressionSolutionImpactValuesCalculator calculator = new SymbolicRegressionSolutionImpactValuesCalculator();
    6746
    6847    #region Parameter properties
     
    7857    public LookupParameter<IntValue> GenerationsParameter {
    7958      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    80     }
    81     // tracking structures
    82     public LookupParameter<TraceMapType> GlobalTraceMapParameter {
    83       get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
    84     }
    85     public LookupParameter<CloneMapType> GlobalCloneMapParameter {
    86       get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    87     }
    88     public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
    89       get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    90     }
    91     // auxiliary structures for tracking fragments and individuals from the previous generation
    92     // (this is needed because tracking is done in connection to the current generation, i.e., for
    93     // counting "successful" offspring and fragments
    94     public LookupParameter<TraceMapType> SecondaryTraceMapParameter {
    95       get { return (LookupParameter<TraceMapType>)Parameters[SecondaryTraceMapParameterName]; }
    96     }
    97     public LookupParameter<CloneMapType> SecondaryFragmentMapParameter {
    98       get { return (LookupParameter<CloneMapType>)Parameters[SecondaryFragmentMapParameterName]; }
    99     }
    100     public LookupParameter<CloneMapType> SecondaryCloneMapParameter {
    101       get { return (LookupParameter<CloneMapType>)Parameters[SecondaryCloneMapParameterName]; }
    102     }
    103     // problem data, interpreter and evaluator
    104     public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
    105       get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
    106     }
    107     public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
    108       get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
    10959    }
    11060    #endregion
     
    12373      get { return ResultsParameter.ActualValue; }
    12474    }
    125     public CloneMapType GlobalCloneMap {
    126       get { return GlobalCloneMapParameter.ActualValue; }
    127     }
    128     public TraceMapType GlobalTraceMap {
    129       get { return GlobalTraceMapParameter.ActualValue; }
    130     }
    131     public TraceMapType SecondaryTraceMap {
    132       get { return SecondaryTraceMapParameter.ActualValue; }
    133       set { SecondaryTraceMapParameter.ActualValue = value; }
    134     }
    135     public CloneMapType SecondaryFragmentMap {
    136       get { return SecondaryFragmentMapParameter.ActualValue; }
    137       set { SecondaryFragmentMapParameter.ActualValue = value; }
    138     }
    139     public CloneMapType SecondaryCloneMap {
    140       get { return SecondaryCloneMapParameter.ActualValue; }
    141       set { SecondaryCloneMapParameter.ActualValue = value; }
    142     }
    143     public CloneMapType GlobalFragmentMap {
    144       get { return GlobalFragmentMapParameter.ActualValue; }
    145     }
    14675    public IntValue Generations {
    14776      get { return GenerationsParameter.ActualValue; }
    148     }
    149     public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
    150       get { return SymbolicExpressionInterpreterParameter.ActualValue; }
    151     }
    152     public RegressionProblemData SymbolicRegressionProblemData {
    153       get { return SymbolicRegressionProblemDataParameter.ActualValue; }
    15477    }
    15578    #endregion
    15679
    15780    [StorableConstructor]
    158     protected SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing) : base(deserializing) { }
     81    private SymbolicExpressionTreeShapeAnalyzer(bool deserializing) : base(deserializing) { }
    15982
    160     protected SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner) : base(original, cloner) { }
     83    private SymbolicExpressionTreeShapeAnalyzer(SymbolicExpressionTreeShapeAnalyzer original, Cloner cloner) : base(original, cloner) { }
    16184
    162     protected SymbolicExpressionTreeFragmentsAnalyzer()
     85    private SymbolicExpressionTreeShapeAnalyzer()
    16386      : base() {
    16487      #region Add parameters
     
    16689      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
    16790      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
    168       // tracking
    169       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, GlobalTraceMapParameterDescription));
    170       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, GlobalCloneMapParameterDescription));
    171       Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, GlobalFragmentMapParameterDescription));
    172       // secondary tracking
    173       Parameters.Add(new LookupParameter<TraceMapType>(SecondaryTraceMapParameterName, GlobalTraceMapParameterDescription));
    174       Parameters.Add(new LookupParameter<CloneMapType>(SecondaryCloneMapParameterName, GlobalCloneMapParameterDescription));
    175       Parameters.Add(new LookupParameter<CloneMapType>(SecondaryFragmentMapParameterName, GlobalFragmentMapParameterDescription));
    176       // impact calculation
    177       Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
    178       Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
    179       // fragment statistics parameters
    18091      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
    18192      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
     
    211122    #endregion
    212123
    213     /* A small description of the way this analyzer works
    214      *
    215      * We keep 3 maps in the global scope: the GlobalTraceMap, the GlobalFragmentMap and the GlobalCloneMap that are updated on each step: selection, crossover, mutation
    216      * These maps provide information about the children, parents and transferred fragments as follows:
    217      *
    218      * 1) GlobalCloneMap
    219      *    This data structure provides the basis for tracking. In the selection step, every selected individual gets cloned and transferred into the recombination pool.
    220      *    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
    221      *    structure we can find out how many times each individual was selected.
    222      *    The GlobalCloneMap consists of Key-Value pairs Clone->Original
    223      *
    224      * 2) GlobalTraceMap
    225      *    Keeps information in the form of key-value pairs Child->{Parents}, where {Parents} is a set consisting of
    226      *      - one parent individual (in the case of mutation), by language abuse we say that the individual that mutation acted on is the parent,
    227      *        and the resulting individual is the child
    228      *      - two parent individuals (in the case of crossover), named Parent0 and Parent1. Parent0 is the individual that crossover acts on by replacing
    229      *        one of its subtrees with a compatible subtree, randomly selected from Parent1
    230      *
    231      *    CROSSOVER
    232      *        Parent0     Parent1                                                                    {Parents}
    233      *           \           /                                                                           ^
    234      *            \       fragment (inserted from Parent1 into Parent0 to create the Child)              ^    [Mapping provided by the GlobalTraceMap]
    235      *             \       /                                                                             ^
    236      *              \     /                                                                              ^
    237      *               Child                                                                             Child
    238      *               
    239      *    MUTATION
    240      *        Parent0
    241      *           |
    242      *           |    [mutation acts on a random node/subtree in the 'parent' individual
    243      *           |
    244      *         Child
    245      *         
    246      *    Since crossover and mutation act on individuals in the recombination pool (which in fact are clones of individuals from the previous generation), the GlobalTraceMap
    247      *    is populated with values given by the mappings in the GlobalCloneMap, so that the original parent for each child is known.
    248      *   
    249      *  3) GlobalFragmentMap
    250      *     Keeps information in the form of Key-Value pairs about an individual and its respective fragment
    251      *     (ie., the subtree received via crossover or created/altered by mutation)
    252      * */
     124    public override IOperation Apply() {
    253125
    254     public override IOperation Apply() {
    255       // save the current generation so it can be compared to the following one, next time the analyzer is applied
    256       SecondaryTraceMap = SecondaryTraceMap ?? new TraceMapType();
    257       SecondaryCloneMap = SecondaryCloneMap ?? new CloneMapType();
    258       SecondaryFragmentMap = SecondaryFragmentMap ?? new CloneMapType();
    259 
    260       SecondaryTraceMap.Clear();
    261       if (GlobalTraceMap != null)
    262         foreach (var m in GlobalTraceMap)
    263           SecondaryTraceMap.Add(m.Key, m.Value);
    264 
    265       SecondaryCloneMap.Clear();
    266       if (GlobalCloneMap != null)
    267         foreach (var m in GlobalCloneMap)
    268           SecondaryCloneMap.Add(m.Key, m.Value);
    269 
    270       SecondaryFragmentMap.Clear();
    271       if (GlobalFragmentMap != null)
    272         foreach (var m in GlobalFragmentMap)
    273           SecondaryFragmentMap.Add(m.Key, m.Value);
    274126      return base.Apply();
    275     }
    276 
    277     protected virtual void InitializeParameters() {
    278       #region Init parameters
    279 
    280       #endregion
    281127    }
    282128
     
    285131    }
    286132
     133    private static int PathLength(ISymbolicExpressionTree tree) {
     134      return PathLength(tree.Root);
     135    }
     136
    287137    private static int VisitationLength(ISymbolicExpressionTreeNode node) {
    288138      return node.IterateNodesBreadth().Sum(n => n.GetLength());
    289139    }
    290140
    291     #region Similarity computations
    292     /// <summary>
    293     /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are.
    294     /// </summary>
    295     /// <param name="fragments">The symbolic expression tree fragments</param>
    296     /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
    297     /// <returns>The average number of similar fragments</returns>
    298     private static double CalculateSimilarity(IList<IFragment> fragments, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    299       var visited = new bool[fragments.Count];
    300       int groups = 0;
    301       for (int i = 0; i != fragments.Count - 1; ++i) {
    302         if (visited[i]) continue;
    303         for (int j = i + 1; j != fragments.Count; ++j) {
    304           if (visited[j]) continue;
    305           if (fragments[i].Root.IsSimilarTo(fragments[j].Root, comparer))
    306             visited[j] = true;
    307         }
    308         ++groups;
    309       }
    310       return (double)fragments.Count / groups;
     141    private static int PathLength(ISymbolicExpressionTreeNode node) {
     142      return node.IterateNodesBreadth().Sum(n => node.GetBranchLevel(n)) + 1;
    311143    }
    312     #endregion
     144
     145    public override IDeepCloneable Clone(Cloner cloner) {
     146      return new SymbolicExpressionTreeShapeAnalyzer(this, cloner);
     147    }
    313148  } //SymbolicExpressionTreeFragmentsAnalyzer
    314149}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/FPGraph.cs

    r9082 r9419  
    2828  [Item("Symbol graph", "A graph used to store the relationship between symbols in a population of individuals")]
    2929  [StorableClass]
    30   public class FPGraph : DirectedGraph<SymbolNode> {
     30  public class FPGraph : GenericGraph<SymbolNode> {
    3131    [Storable]
    3232    public Dictionary<int, List<SymbolNode>> Levels { get { return levels; } }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenericGraph/Arc.cs

    r9082 r9419  
    1 
     1using HeuristicLab.Common;
     2using HeuristicLab.Core;
     3using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     4
    25namespace HeuristicLab.EvolutionaryTracking {
    36  /// <summary>
    47  /// An arc that can have a weight, a label, and can old additional information in the Data object
    58  /// </summary>
    6   public class Arc {
    7     public IVertex Source { get; set; }
    8     public IVertex Target { get; set; }
    9     public string Label { get; set; }
    10     public double Weight { get; set; }
    11     public object Data { get; set; }
     9  [StorableClass]
     10  public class Arc : Item, IEdge
     11  {
     12    [Storable] private IVertex source;
     13    public IVertex Source { get { return source; } set { source = value; } }
     14    [Storable] private IVertex target;
     15    public IVertex Target { get { return target; } set { target = value; } }
     16    [Storable] private string label;
     17    public string Label { get { return label; } set { label = value; } }
     18    [Storable] private double weight;
     19    public double Weight { get { return weight; } set { weight = value; } }
     20    [Storable] private object data;
     21    public object Data { get { return data; } set { data = value; } }
     22
     23    [StorableConstructor]
     24    public Arc(bool deserializing) : base(deserializing) {}
     25
     26    public Arc() {}
     27
     28    private Arc(Arc original, Cloner cloner) : base(original, cloner)
     29    {
     30      Source = original.Source;
     31      Target = original.Target;
     32      Label = original.Label;
     33      Weight = original.Weight;
     34      Data = original.Data;
     35    }
     36
     37    public override IDeepCloneable Clone(Cloner cloner)
     38    {
     39      return new Arc(this, cloner);
     40    }
    1241  }
    1342}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenericGraph/GenericGraph.cs

    r9236 r9419  
    3131  [Item("Directed graph", "Generic directed graph base class.")]
    3232  [StorableClass]
    33   public class DirectedGraph<T> : Item, IDirectedGraph<T> where T : class, IVertex {
     33  public class GenericGraph<T> : Item, IGenericGraph<T> where T : class, IVertex {
    3434    [Storable]
    3535    private readonly List<T> nodes; // graph will consist of a set of nodes of type T
     
    3838    }
    3939
    40     public DirectedGraph() {
     40    public GenericGraph() {
    4141      nodes = new List<T>();
    4242    }
    4343
    44     public DirectedGraph(IDirectedGraph<T> g) {
     44    public GenericGraph(IGenericGraph<T> g) {
    4545      nodes = new List<T>(g.Nodes);
    4646    }
    4747
    4848    public override IDeepCloneable Clone(Cloner cloner) {
    49       return new DirectedGraph<T>(this, cloner);
     49      return new GenericGraph<T>(this, cloner);
    5050    }
    5151
     
    5555
    5656    [StorableConstructor]
    57     protected DirectedGraph(bool serializing)
     57    protected GenericGraph(bool serializing)
    5858      : base(serializing) {
    5959    }
    6060
    61     protected DirectedGraph(DirectedGraph<T> original, Cloner cloner)
     61    protected GenericGraph(GenericGraph<T> original, Cloner cloner)
    6262      : base(original, cloner) {
    6363      nodes = new List<T>(original.Nodes); // bburlacu: maybe the list should be empty
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenericGraph/Vertex.cs

    r9247 r9419  
    2222using System;
    2323using System.Collections.Generic;
     24using HeuristicLab.Common;
     25using HeuristicLab.Core;
    2426using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2527
    2628namespace HeuristicLab.EvolutionaryTracking {
    2729  [StorableClass]
    28   public class Vertex : IVertex {
    29     public string Id { get; private set; }
    30     public string Label { get; set; }
    31     public double Weight { get; set; }
    32     public List<Arc> InEdges { get; private set; }
    33     public List<Arc> OutEdges { get; private set; }
    34     private object content;
     30  public class Vertex : Item, IVertex
     31  {
     32    [Storable]
     33    private string id;
     34    public string Id { get { return id; } }
     35    [Storable] private string label;
     36    public string Label { get { return label; } set { label = value; } }
     37    [Storable] private double weight;
     38    public double Weight { get { return weight; } set { weight = value; } }
     39    [Storable] private List<IEdge> inEdges;
     40    public List<IEdge> InEdges { get { return inEdges; } private set { inEdges = value; } }
     41    [Storable] private List<IEdge> outEdges;
     42    public List<IEdge> OutEdges { get { return outEdges; }private set { outEdges = value; }}
     43    [Storable] private object content;
    3544    public object Content {
    3645      get { return content; }
     
    4352
    4453    [StorableConstructor]
    45     public Vertex(bool deserializing) { }
     54    public Vertex(bool deserializing) : base(deserializing) { }
    4655
    4756    public Vertex() {
    48       Id = Guid.NewGuid().ToString();
     57      id = Guid.NewGuid().ToString();
     58    }
     59
     60    [StorableHook(HookType.AfterDeserialization)]
     61    private void AfterDeserialization()
     62    {
     63      if (id == null) {
     64        id = Guid.NewGuid().ToString();
     65      }
     66    }
     67
     68    protected Vertex(Vertex original, Cloner cloner)
     69      : base(original, cloner) {
     70      Content = original.Content;
     71      id = Guid.NewGuid().ToString();
     72      Label = original.Label;
     73      Content = original.Content;
     74      InEdges = new List<IEdge>(original.InEdges);
     75      OutEdges = new List<IEdge>(original.OutEdges);
     76    }
     77
     78    public override IDeepCloneable Clone(Cloner cloner) {
     79      return new Vertex(this, cloner);
    4980    }
    5081
    5182    public Vertex(Vertex node) {
    52       Id = Guid.NewGuid().ToString();
     83      id = Guid.NewGuid().ToString();
    5384      Label = node.Label;
    5485      Content = node.Content;
    55       InEdges = new List<Arc>(node.InEdges);
    56       OutEdges = new List<Arc>(node.OutEdges);
     86      InEdges = new List<IEdge>(node.InEdges);
     87      OutEdges = new List<IEdge>(node.OutEdges);
    5788    }
    5889
     
    108139    public void AddForwardArc(IVertex target, double weight = 0.0, object data = null) {
    109140      var e = new Arc { Source = this, Target = target, Data = data, Weight = weight };
    110       if (OutEdges == null) OutEdges = new List<Arc> { e };
     141      if (OutEdges == null) OutEdges = new List<IEdge> { e };
    111142      else OutEdges.Add(e);
    112143    }
    113     public void AddForwardArc(Arc arc) {
     144    public void AddForwardArc(IEdge arc) {
    114145      if (arc.Source == null) { arc.Source = this; }
    115146      if (arc.Source != this) { throw new Exception("AddForwardArc: Source should be equal to this."); }
    116       if (OutEdges == null) { OutEdges = new List<Arc> { arc }; } else { OutEdges.Add(arc); }
     147      if (OutEdges == null) { OutEdges = new List<IEdge> { arc }; } else { OutEdges.Add(arc); }
    117148    }
    118     public void AddReverseArc(Arc arc) {
     149    public void AddReverseArc(IEdge arc) {
    119150      if (arc.Target == null) { arc.Target = this; }
    120151      if (arc.Target != this) { throw new Exception("AddReverseArc: Target should be equal to this."); };
    121       if (InEdges == null) { InEdges = new List<Arc> { arc }; } else { InEdges.Add(arc); }
     152      if (InEdges == null) { InEdges = new List<IEdge> { arc }; } else { InEdges.Add(arc); }
    122153    }
    123154    public void AddReverseArc(IVertex source, double weight = 0.0, object data = null) {
    124155      var e = new Arc { Source = source, Target = this, Data = data, Weight = weight };
    125       if (InEdges == null) InEdges = new List<Arc> { e };
     156      if (InEdges == null) InEdges = new List<IEdge> { e };
    126157      else InEdges.Add(e);
    127158    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

    r9296 r9419  
    1818    <DebugType>full</DebugType>
    1919    <Optimize>false</Optimize>
    20     <OutputPath>..\..\..\..\Trunk\sources\bin\</OutputPath>
     20    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    2121    <DefineConstants>DEBUG;TRACE</DefineConstants>
    2222    <ErrorReport>prompt</ErrorReport>
     
    3939  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x64'">
    4040    <DebugSymbols>true</DebugSymbols>
    41     <OutputPath>bin\x64\Debug\</OutputPath>
     41    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    4242    <DefineConstants>DEBUG;TRACE</DefineConstants>
    4343    <DebugType>full</DebugType>
     
    5656  </PropertyGroup>
    5757  <ItemGroup>
    58     <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     58    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     59      <Private>False</Private>
     60    </Reference>
    5961    <Reference Include="HeuristicLab.Collections-3.3">
    6062      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
     63      <Private>False</Private>
    6164    </Reference>
    6265    <Reference Include="HeuristicLab.Common-3.3">
    6366      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
    64     </Reference>
    65     <Reference Include="HeuristicLab.Common.Resources-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     67      <Private>False</Private>
     68    </Reference>
     69    <Reference Include="HeuristicLab.Common.Resources-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     70      <Private>False</Private>
     71    </Reference>
    6672    <Reference Include="HeuristicLab.Core-3.3">
    6773      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
    68     </Reference>
    69     <Reference Include="HeuristicLab.Core.Views-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     74      <Private>False</Private>
     75    </Reference>
     76    <Reference Include="HeuristicLab.Core.Views-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     77      <Private>False</Private>
     78    </Reference>
    7079    <Reference Include="HeuristicLab.Data-3.3">
    7180      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
    72     </Reference>
    73     <Reference Include="HeuristicLab.MainForm-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    74     <Reference Include="HeuristicLab.MainForm.WindowsForms-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     81      <Private>False</Private>
     82    </Reference>
     83    <Reference Include="HeuristicLab.MainForm-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     84      <Private>False</Private>
     85    </Reference>
     86    <Reference Include="HeuristicLab.MainForm.WindowsForms-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     87      <Private>False</Private>
     88    </Reference>
    7589    <Reference Include="HeuristicLab.Operators-3.3">
    7690      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
     91      <Private>False</Private>
    7792    </Reference>
    7893    <Reference Include="HeuristicLab.Optimization-3.3">
    7994      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Optimization-3.3.dll</HintPath>
     95      <Private>False</Private>
    8096    </Reference>
    8197    <Reference Include="HeuristicLab.Parameters-3.3">
    8298      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Parameters-3.3.dll</HintPath>
     99      <Private>False</Private>
    83100    </Reference>
    84101    <Reference Include="HeuristicLab.Persistence-3.3">
    85102      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Persistence-3.3.dll</HintPath>
    86     </Reference>
    87     <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    88     <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    89     <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    90     <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    91     <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     103      <Private>False</Private>
     104    </Reference>
     105    <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     106      <Private>False</Private>
     107    </Reference>
     108    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     109      <Private>False</Private>
     110    </Reference>
     111    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     112      <Private>False</Private>
     113    </Reference>
     114    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     115      <Private>False</Private>
     116    </Reference>
     117    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     118      <Private>False</Private>
     119    </Reference>
    92120    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    93121      <SpecificVersion>False</SpecificVersion>
    94122      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     123      <Private>False</Private>
    95124    </Reference>
    96125    <Reference Include="System" />
     
    105134  </ItemGroup>
    106135  <ItemGroup>
     136    <Compile Include="Analyzers\BuildingBlocks\RelevantBuildingBlocksAnalyzer.cs" />
     137    <Compile Include="Analyzers\BuildingBlocks\Poly10BuildingBlocksAnalyzer.cs" />
    107138    <Compile Include="Analyzers\SymbolicExpressionTreeShapeAnalyzer.cs" />
    108139    <Compile Include="Analyzers\SymbolicExpressionTreeEvolvabilityAnalyzer.cs" />
     
    113144    <Compile Include="Analyzers\Fragments\SymbolicExpressionTreeFragmentsAnalyzer.cs" />
    114145    <Compile Include="FPGraph.cs" />
     146    <Compile Include="Interfaces\IEdge.cs" />
    115147    <Compile Include="LineageExplorer.cs" />
    116148    <Compile Include="Operators\LineageAggregator.cs" />
     
    119151    <Compile Include="Analyzers\SymbolicExpressionTreePopulationDiversityAnalyzer.cs" />
    120152    <Compile Include="Analyzers\SymbolicExpressionTreeRelativeLengthAnalyzer.cs" />
    121     <Compile Include="DirectedGraph\DirectedGraph.cs" />
    122     <Compile Include="DirectedGraph\Arc.cs" />
    123     <Compile Include="DirectedGraph\Vertex.cs" />
    124     <Compile Include="Interfaces\IDirectedGraph.cs" />
     153    <Compile Include="GenericGraph\GenericGraph.cs" />
     154    <Compile Include="GenericGraph\Arc.cs" />
     155    <Compile Include="GenericGraph\Vertex.cs" />
     156    <Compile Include="Interfaces\IGenericGraph.cs" />
    125157    <Compile Include="Interfaces\IVertex.cs" />
    126158    <Compile Include="Interfaces\ISymbolicExpressionTreeGenealogyGraph.cs" />
     
    132164    <Compile Include="SymbolGraph.cs" />
    133165    <Compile Include="SymbolicExpressionTreeGenealogyGraph.cs" />
     166    <Compile Include="TreeDistance\TreeDistanceCalculator.cs" />
    134167  </ItemGroup>
    135168  <ItemGroup />
     
    138171      <Project>{06D4A186-9319-48A0-BADE-A2058D462EEA}</Project>
    139172      <Name>HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4</Name>
     173      <Private>False</Private>
    140174    </ProjectReference>
    141175    <ProjectReference Include="..\..\HeuristicLab.Problems.DataAnalysis.Symbolic\3.4\HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj">
    142176      <Project>{3d28463f-ec96-4d82-afee-38be91a0ca00}</Project>
    143177      <Name>HeuristicLab.Problems.DataAnalysis.Symbolic-3.4</Name>
     178      <Private>False</Private>
    144179    </ProjectReference>
    145180    <ProjectReference Include="..\..\HeuristicLab.Selection\3.3\HeuristicLab.Selection-3.3.csproj">
    146181      <Project>{2C36CD4F-E5F5-43A4-801A-201EA895FE17}</Project>
    147182      <Name>HeuristicLab.Selection-3.3</Name>
     183      <Private>False</Private>
    148184    </ProjectReference>
    149185  </ItemGroup>
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IGenericGraph.cs

    r9236 r9419  
    2525
    2626namespace HeuristicLab.EvolutionaryTracking {
    27   public interface IDirectedGraph<T> : IItem where T : class, IVertex {
     27  public interface IGenericGraph<T> : IItem where T : class, IVertex {
    2828    bool Contains(T t); // graph contains specific node?
    2929    bool Any(Func<T, bool> predicate); // graph contains any nodes matching the given predicate?
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/ISymbolicExpressionTreeGenealogyGraph.cs

    r9082 r9419  
    2424
    2525namespace HeuristicLab.EvolutionaryTracking {
    26   public interface ISymbolicExpressionTreeGenealogyGraph : IDirectedGraph<SymbolicExpressionGenealogyGraphNode> {
     26  public interface ISymbolicExpressionTreeGenealogyGraph : IGenericGraph<SymbolicExpressionGenealogyGraphNode> {
    2727    List<SymbolicExpressionGenealogyGraphNode> GetGraphNodes(ISymbolicExpressionTree tree);
    2828  }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IVertex.cs

    r9082 r9419  
    2525  public interface IVertex {
    2626    string Id { get; }
    27     List<Arc> InEdges { get; }
    28     List<Arc> OutEdges { get; }
     27    List<IEdge> InEdges { get; }
     28    List<IEdge> OutEdges { get; }
     29
     30
    2931    int InDegree { get; }
    3032    int OutDegree { get; }
     
    3840
    3941    void AddForwardArc(IVertex target, double weight = 0.0, object content = null);
    40     void AddForwardArc(Arc arc);
     42    void AddForwardArc(IEdge arc);
    4143    void AddReverseArc(IVertex target, double weight = 0.0, object content = null);
    42     void AddReverseArc(Arc arc);
     44    void AddReverseArc(IEdge arc);
    4345  }
    4446}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/LineageExplorer.cs

    r9238 r9419  
    99  [StorableClass]
    1010  public class LineageExplorer : Item {
    11     public ISymbolicExpressionTreeGenealogyGraph GenealogyGraph { get; set; }
    12     public IList<Tuple<ISymbolicExpressionTree, double>> Trees { get; set; }
    13     public int Generations { get; set; }
     11    [Storable]
     12    private ISymbolicExpressionTreeGenealogyGraph genealogyGraph;
     13    public ISymbolicExpressionTreeGenealogyGraph GenealogyGraph { get { return genealogyGraph; } set { genealogyGraph = value; } }
     14    [Storable]
     15    private IList<Tuple<ISymbolicExpressionTree, double>> trees;
     16    public IList<Tuple<ISymbolicExpressionTree, double>> Trees { get { return trees; } set { trees = value; } }
     17    [Storable]
     18    private int generations;
     19    public int Generations { get { return generations; } set { generations = value; } }
    1420
    1521    private LineageExplorer(bool deserializing) : base(deserializing) { }
    16     private LineageExplorer(LineageExplorer original, Cloner cloner) : base(original, cloner) { }
     22    private LineageExplorer(LineageExplorer original, Cloner cloner)
     23      : base(original, cloner) {
     24      genealogyGraph = original.genealogyGraph;
     25      trees = original.trees;
     26      generations = original.generations;
     27    }
    1728    public LineageExplorer() { }
    1829    public override IDeepCloneable Clone(Cloner cloner) { return new LineageExplorer(this, cloner); }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/SymbolicExpressionTreeFPBuilder.cs

    r9082 r9419  
    3232
    3333    private SymbolicRegressionSolutionImpactValuesCalculator calculator;
    34     private Dictionary<SymbolNode, double> averageNodeImpacts;
     34    //    private Dictionary<SymbolNode, double> averageNodeImpacts;
    3535
    3636    #region Parameter properties
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/SymbolicExpressionTreeGenealogyGraphBuilder.cs

    r9247 r9419  
    201201      var qualities = SymbolicExpressionTreeQualityParameter.ActualValue.ToArray();
    202202
    203       if (trees.Length != qualities.Length) throw new Exception("Error: trees and qualities array sizes do not match!");
     203      if (trees.Length != qualities.Length)
     204        throw new Exception("Error: trees and qualities array sizes do not match!");
    204205
    205206      // add all individuals to the evolutionary graph
    206207      int generation = Generations.Value;
    207208
    208       var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q.Value }).OrderByDescending(x => x.Quality).ToList();
     209      var pairs =
     210        trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q.Value }).OrderByDescending(x => x.Quality).ToList();
    209211
    210212      if (generation == 0) {
     
    214216          var quality = pair.Quality;
    215217          graph.AddNode(new SymbolicExpressionGenealogyGraphNode {
    216             SymbolicExpressionTree = tree, Quality = quality, Rank = generation
     218            SymbolicExpressionTree = tree,
     219            Quality = quality,
     220            Rank = generation
    217221          });
    218222        }
     
    231235        // the following query addds the intermediate nodes that were created when
    232236        // crossover was followed by mutation (they are not present in the scope)
    233                         (from t in trees
    234                          where GlobalTraceMap.ContainsKey(t)
    235                          let parents = GlobalTraceMap[t]
    236                          where parents.Count == 1 // 1 parent means mutation
    237                          let p = (ISymbolicExpressionTree)parents[0]
    238                          select new SymbolicExpressionGenealogyGraphNode {
    239                            SymbolicExpressionTree = p,
    240                            Quality = Evaluate(p),
    241                            Rank = generation - 0.5 // an intermediate parent that would normale be 'invisible' to the evolutionary process
    242                          }
    243                         ).ToList();
     237        (from t in trees
     238         where GlobalTraceMap.ContainsKey(t)
     239         let parents = GlobalTraceMap[t]
     240         where parents.Count == 1
     241         // 1 parent means mutation
     242         let p = (ISymbolicExpressionTree)parents[0]
     243         select new SymbolicExpressionGenealogyGraphNode {
     244           SymbolicExpressionTree = p,
     245           Quality = Evaluate(p),
     246           Rank = generation - 0.5
     247           // an intermediate parent that would normale be 'invisible' to the evolutionary process
     248         }
     249        ).ToList();
    244250
    245251      foreach (var node in graphNodes) {
     
    262268          continue;
    263269        }
    264         var parents = GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>();
     270        var parents = GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>().ToList();
     271        var fragment = GlobalFragmentMap[tree];
    265272        foreach (var p in parents) {
    266273          var nodes = graph.GetGraphNodes(p);
     
    272279            throw new Exception("Source node cannot be null");
    273280          }
    274           var arc = new Arc { Source = sourceNode, Target = node, Data = GlobalFragmentMap[tree] };
     281          var arc = new Arc { Source = sourceNode, Target = node, Data = fragment };
    275282          sourceNode.AddForwardArc(arc);
    276283          node.AddReverseArc(arc);
    277284        }
     285        // the root parent is the one that receives the subtree/fragment from the other parent
     286        // so it does not actually pass a subtree to the child, therefore the fragment is null
     287        // so in case of crossover, we add a null fragment below
     288        if (parents.Count > 1) node.InEdges[0].Data = new Fragment(null);
    278289      }
     290
     291      // notify listeners that the genealogy graph was updated
     292      graph.Updated();
     293
    279294      return base.Apply();
    280295    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/Util.cs

    r9082 r9419  
    2828    }
    2929
    30     public static void WriteDot(this IDirectedGraph<SymbolNode> graph, string path) {
     30    public static void WriteDot(this IGenericGraph<SymbolNode> graph, string path) {
    3131      const double minNorm = 1.0, maxNorm = 3.0;
    3232
     
    3737      var max = arcs.Max(x => x.Weight);
    3838
    39       var normalizedWeights = arcs.Select(arc => new KeyValuePair<Arc, double>(arc, (arc.Weight - min) * (maxNorm - minNorm) / (max - min) + minNorm))
     39      var normalizedWeights = arcs.Select(arc => new KeyValuePair<SymbolArc, double>(arc, (arc.Weight - min) * (maxNorm - minNorm) / (max - min) + minNorm))
    4040                                  .ToDictionary(x => x.Key, x => x.Value);
    4141
     
    7575      }
    7676    }
    77     public static void WriteGml(this IDirectedGraph<SymbolNode> graph, string path) {
     77    public static void WriteGml(this IGenericGraph<SymbolNode> graph, string path) {
    7878      var idMap = new Dictionary<string, int>();
    7979      const double minNorm = 1.0, maxNorm = 3.0;
     
    8686      var max = arcs.Max(x => x.Weight);
    8787
    88       var normalizedWeights = arcs.Select(arc => new KeyValuePair<Arc, double>(arc, (arc.Weight - min) * (maxNorm - minNorm) / (max - min) + minNorm))
     88      var normalizedWeights = arcs.Select(arc => new KeyValuePair<SymbolArc, double>(arc, (arc.Weight - min) * (maxNorm - minNorm) / (max - min) + minNorm))
    8989                                  .ToDictionary(x => x.Key, x => x.Value);
    9090
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolGraph.cs

    r9082 r9419  
    2121
    2222using System.Collections.Generic;
     23using System.Linq;
    2324using HeuristicLab.Core;
    2425using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    2829  [Item("Symbol graph", "A graph used to store the relationship between symbols in a population of individuals")]
    2930  [StorableClass]
    30   public class SymbolGraph : DirectedGraph<SymbolNode> {
     31  public class SymbolGraph : GenericGraph<SymbolNode> {
    3132    [Storable]
    3233    private Dictionary<string, SymbolNode> nodes = new Dictionary<string, SymbolNode>();
     
    5859    public Dictionary<int, int> Positions { get; set; }
    5960    public double AverageArity { get; set; }
     61
     62    public new List<SymbolArc> InEdges {
     63      get { return base.InEdges == null ? null : base.InEdges.Cast<SymbolArc>().ToList(); }
     64    }
     65
     66    public new List<SymbolArc> OutEdges {
     67      get { return base.OutEdges == null ? null : base.OutEdges.Cast<SymbolArc>().ToList(); }
     68    }
     69  }
     70
     71  public class SymbolArc : IEdge {
     72    public IVertex Source { get; set; }
     73    public IVertex Target { get; set; }
     74    public double Weight { get; set; }
    6075  }
    6176}
    62 
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph.cs

    r9247 r9419  
    3131  [Item("SymbolicExpressionTreeGenealogyGraph", "A genealogy graph for symbolic expression tree individuals")]
    3232  [StorableClass]
    33   public sealed class SymbolicExpressionTreeGenealogyGraph : DirectedGraph<SymbolicExpressionGenealogyGraphNode>, ISymbolicExpressionTreeGenealogyGraph, IDisposable {
     33  public sealed class SymbolicExpressionTreeGenealogyGraph : GenericGraph<SymbolicExpressionGenealogyGraphNode>,
     34                                                             ISymbolicExpressionTreeGenealogyGraph, IDisposable {
    3435    [Storable]
    35     private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>> nodeMap = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>();
     36    private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>> nodeMap
     37      = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>();
    3638
    37     public SymbolicExpressionTreeGenealogyGraph() { }
     39    public SymbolicExpressionTreeGenealogyGraph() {
     40    }
     41
     42    public void Updated() {
     43      var updated = GraphUpdated;
     44      if (updated != null) updated(this, null);
     45    }
    3846
    3947    [StorableConstructor]
    40     public SymbolicExpressionTreeGenealogyGraph(bool serializing) : base(serializing) { }
     48    public SymbolicExpressionTreeGenealogyGraph(bool serializing)
     49      : base(serializing) {
     50    }
    4151
    42     public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraph(this, cloner); }
     52    public override IDeepCloneable Clone(Cloner cloner) {
     53      return new SymbolicExpressionTreeGenealogyGraph(this, cloner);
     54    }
    4355
    44     private SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner) : base(original, cloner) { }
     56    private SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner)
     57      : base(original, cloner) {
     58      nodeMap = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>(original.nodeMap);
     59    }
    4560
    4661    public override void AddNode(SymbolicExpressionGenealogyGraphNode node) {
     
    5065      else
    5166        nodeMap[tree] = new List<SymbolicExpressionGenealogyGraphNode> { node };
    52       base.AddNode(node); // the genealogy graph should have as many nodes as individuals in the population multiplied by the number of generations
     67      base.AddNode(node);
     68      // the genealogy graph should have as many nodes as individuals in the population multiplied by the number of generations
     69      // plus a number of intermediate individuals ~= mutation probability * population size
    5370    }
    5471
     
    7087    }
    7188
    72     //    #region Fragment tracing
    73     //    public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    74     //      return Nodes.Select(x => x.SymbolicExpressionTree).Where(tree => tree.ContainsFragment(fragment, comparer));
    75     //    }
    76     //    #endregion
     89    public SymbolicExpressionGenealogyGraphNode MostRecentCommonAncestor() {
     90      double currentRank = Nodes.Last().Rank;
     91      var currentGen = Nodes.Where(n => n.Rank.IsAlmost(currentRank)).ToList();
     92      var lineages = currentGen.Select(n => n.RootLineage().ToArray()).ToArray();
     93      for (int i = 0; i < (int)currentRank; ++i) {
     94        if (lineages.All(lineage => lineages[0][i].SymbolicExpressionTree == lineage[i].SymbolicExpressionTree))
     95          return lineages[0][i];
     96      }
     97      return null;
     98    }
    7799
    78100    public void Dispose() {
     
    80102      nodeMap.Clear();
    81103      // call GC.SupressFinalize?
     104    }
     105
     106    public event EventHandler GraphUpdated;
     107    private void OnGraphUpdated(object sender, EventArgs args) {
     108      var updated = GraphUpdated;
     109      if (updated != null) updated(sender, args);
    82110    }
    83111  }
     
    89117      set { Content = value; }
    90118    }
    91     public double Quality { get; set; }
    92     public bool IsElite { get; set; }
    93     public double Rank { get; set; }
     119
     120    [Storable]
     121    private double quality;
     122    public double Quality { get { return quality; } set { quality = value; } }
     123    [Storable]
     124    private bool isElite;
     125    public bool IsElite { get { return isElite; } set { isElite = value; } }
     126    [Storable]
     127    private double rank;
     128    public double Rank { get { return rank; } set { rank = value; } }
     129
     130    [StorableHook(HookType.AfterDeserialization)]
     131    private void AfterDeserialization() {
     132      if (Id == null) throw new Exception();
     133    }
    94134
    95135    [StorableConstructor]
    96     public SymbolicExpressionGenealogyGraphNode(bool deserializing) : base(deserializing) { }
     136    public SymbolicExpressionGenealogyGraphNode(bool deserializing)
     137      : base(deserializing) {
     138    }
    97139
    98     public SymbolicExpressionGenealogyGraphNode() { }
     140    public SymbolicExpressionGenealogyGraphNode() {
     141    }
    99142
    100     public SymbolicExpressionGenealogyGraphNode(object content) {
    101       Content = content;
     143    private SymbolicExpressionGenealogyGraphNode(SymbolicExpressionGenealogyGraphNode original, Cloner cloner)
     144      : base(original, cloner) {
     145      Quality = original.Quality;
     146      IsElite = original.IsElite;
     147      Rank = original.Rank;
     148    }
     149
     150    public override IDeepCloneable Clone(Cloner cloner) {
     151      return new SymbolicExpressionGenealogyGraphNode(this, cloner);
    102152    }
    103153
     
    109159      return base.Descendants().Cast<SymbolicExpressionGenealogyGraphNode>();
    110160    }
     161
     162    public IEnumerable<SymbolicExpressionGenealogyGraphNode> RootLineage() {
     163      var lineage = new List<SymbolicExpressionGenealogyGraphNode> { this };
     164      int i = 0;
     165      while (i != lineage.Count) {
     166        if (lineage[i].InEdges != null) {
     167          lineage.Add((SymbolicExpressionGenealogyGraphNode)lineage[i].InEdges[0].Source);
     168        }
     169        ++i;
     170      }
     171      return lineage;
     172    }
     173
     174    public new List<Arc> InEdges {
     175      get {
     176        return base.InEdges == null ? null : base.InEdges.Cast<Arc>().ToList();
     177      }
     178    }
     179
     180    public new List<Arc> OutEdges {
     181      get {
     182        return base.OutEdges == null ? null : base.InEdges.Cast<Arc>().ToList();
     183      }
     184    }
    111185  }
    112186}
Note: See TracChangeset for help on using the changeset viewer.