source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph/SymbolicExpressionTreeGenealogyGraph.cs @ 10264

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.EvolutionaryTracking {
  [Item("SymbolicExpressionTreeGenealogyGraph", "A genealogy graph for symbolic expression tree individuals")]
  [StorableClass]
  public sealed class SymbolicExpressionTreeGenealogyGraph : GenericGraph<SymbolicExpressionTreeGenealogyGraphNode>,
                                                             ISymbolicExpressionTreeGenealogyGraph, IDisposable {
    [Storable]
    private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionTreeGenealogyGraphNode>> nodeMap
      = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionTreeGenealogyGraphNode>>();

    public SymbolicExpressionTreeGenealogyGraph() {
    }

    public void Updated() {
      var updated = GraphUpdated;
      if (updated != null) updated(this, null);
    }

    [StorableConstructor]
    public SymbolicExpressionTreeGenealogyGraph(bool serializing)
      : base(serializing) {
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicExpressionTreeGenealogyGraph(this, cloner);
    }

    private SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner)
      : base(original, cloner) {
      nodeMap = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionTreeGenealogyGraphNode>>(original.nodeMap);
    }

    public override void AddNode(SymbolicExpressionTreeGenealogyGraphNode node) {
      var tree = node.SymbolicExpressionTree;
      if (nodeMap.ContainsKey(tree))
        nodeMap[tree].Add(node);
      else
        nodeMap[tree] = new List<SymbolicExpressionTreeGenealogyGraphNode> { node };
      base.AddNode(node);
      // the genealogy graph should have as many nodes as individuals in the population multiplied by the number of generations
      // plus a number of intermediate individuals ~= mutation probability * population size
    }

    public bool ContainsIndividual(ISymbolicExpressionTree tree) {
      return nodeMap.ContainsKey(tree);
    }

    public List<SymbolicExpressionTreeGenealogyGraphNode> GetGraphNodes(ISymbolicExpressionTree tree) {
      return nodeMap.ContainsKey(tree) ? nodeMap[tree] : null;
    }
    // TODO: make sure a and b are valid and the info exists for both
    public int Compare(SymbolicExpressionTreeGenealogyGraphNode a, SymbolicExpressionTreeGenealogyGraphNode b) {
      if (a.Quality.Equals(b.Quality)) {
        if (a.IsElite) return +1;
        if (b.IsElite) return -1;
      }
      return a.Quality.CompareTo(b.Quality);
    }

    public SymbolicExpressionTreeGenealogyGraphNode MostRecentCommonAncestor() {
      double currentRank = Nodes.Last().Rank;
      var currentGen = Nodes.Where(n => n.Rank.IsAlmost(currentRank)).ToList();
      var lineages = currentGen.Select(n => n.RootLineage().ToArray()).ToArray();
      for (int i = 0; i < (int)currentRank; ++i) {
        if (lineages.All(lineage => lineages[0][i].SymbolicExpressionTree == lineage[i].SymbolicExpressionTree))
          return lineages[0][i];
      }
      return null;
    }

    public void Dispose() {
      Nodes.Clear();
      nodeMap.Clear();
      // call GC.SupressFinalize?
    }

    public event EventHandler GraphUpdated;
    private void OnGraphUpdated(object sender, EventArgs args) {
      var updated = GraphUpdated;
      if (updated != null) updated(sender, args);
    }
  }
}