source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/SymbolicExpressionTreeFPBuilder.cs @ 9419

using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;

namespace HeuristicLab.EvolutionaryTracking {
  /// <summary>
  /// Operator which builds a so-called frequenct pattern tree
  /// (a compact representation of the symbol relationships in the population)
  /// </summary>
  [Item("SymbolicExpressionTreeFPBuilder", "Builds a frequent-pattern tree out of the GP population.")]
  [StorableClass]
  public class SymbolicExpressionTreeFPBuilder : SingleSuccessorOperator {
    private const string ResultsParameterName = "Results";
    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    private const string SymbolicExpressionTreeQualityParameterName = "Quality";

    private SymbolicRegressionSolutionImpactValuesCalculator calculator;
    //    private Dictionary<SymbolNode, double> averageNodeImpacts;

    #region Parameter properties

    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }

    public IScopeTreeLookupParameter<DoubleValue> SymbolicExpressionTreeQualityParameter {
      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[SymbolicExpressionTreeQualityParameterName]; }
    }

    public ILookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionTreeInterpreterParameter {
      get {
        return
          (ILookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)
          Parameters[SymbolicExpressionInterpreterParameterName];
      }
    }

    public ILookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
      get { return (ILookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
    }

    #endregion

    [StorableConstructor]
    private SymbolicExpressionTreeFPBuilder(bool deserializing)
      : base(deserializing) {
    }

    private SymbolicExpressionTreeFPBuilder(SymbolicExpressionTreeFPBuilder original, Cloner cloner)
      : base(original, cloner) {
    }

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

    public SymbolicExpressionTreeFPBuilder()
      : base() {
      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze"));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));

      calculator = new SymbolicRegressionSolutionImpactValuesCalculator();
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
    }

    #region IStatefulItem members

    public override void InitializeState() {
      base.InitializeState();
    }

    public override void ClearState() {
      base.ClearState();
    }

    #endregion

    public override IOperation Apply() {
      var trees = SymbolicExpressionTreeParameter.ActualValue;
      var qualities = SymbolicExpressionTreeQualityParameter.ActualValue;

      if (trees == null || qualities == null) return base.Apply();

      if (trees.Length != qualities.Length)
        throw new Exception("Error: trees and qualities array sizes do not match!");

      var graph = new FPGraph();
      var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();

      var nodeImpacts = new Dictionary<SymbolNode, IList<double>>();
      var impactsCalculator = new SymbolicRegressionSolutionImpactValuesCalculator();

      for (int i = 0; i != trees.Length; ++i) {
        var model = new SymbolicRegressionModel(trees[i], SymbolicExpressionTreeInterpreterParameter.ActualValue);

        var root = trees[i].Root;
        var originalQuality = qualities[i].Value;

        //        canonicalSorter.SortSubtrees(root);
        foreach (var node in root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix())
          MergeNodesAndImpacts(graph, model, node, originalQuality, nodeImpacts, impactsCalculator, 0);
      }

      WriteGraphAndImpacts(graph, nodeImpacts, Environment.GetFolderPath(Environment.SpecialFolder.UserProfile) + "\\fpgraph.dot", 0.0);
      WriteGraphAndImpacts(graph, nodeImpacts, Environment.GetFolderPath(Environment.SpecialFolder.UserProfile) + "\\prunedfpgraph.dot", 0.1);
      return base.Apply();
    }

    private void MergeNodesAndImpacts(FPGraph graph, ISymbolicDataAnalysisModel model, ISymbolicExpressionTreeNode node,
                                      double originalQuality, IDictionary<SymbolNode, IList<double>> nodeImpacts,
                                      ISymbolicDataAnalysisSolutionImpactValuesCalculator impactValuesCalculator, int level = 0) {
      var label = node.Label();
      var symbolNode = graph.GetNode(label, level);
      if (symbolNode == null) {
        symbolNode = new SymbolNode { Label = label, Symbol = node.Symbol, Weight = 1 };
        graph.AddNode(symbolNode, level);
      } else {
        symbolNode.Weight += 1;
      }
      var problemData = SymbolicRegressionProblemDataParameter.ActualValue;

      var impact = impactValuesCalculator.CalculateImpactValue(model, node, problemData, problemData.TrainingIndices, originalQuality);
      if (nodeImpacts.ContainsKey(symbolNode)) {
        nodeImpacts[symbolNode].Add(impact);
      } else {
        nodeImpacts.Add(symbolNode, new List<double> { impact });
      }
      foreach (var s in node.Subtrees) {
        MergeNodesAndImpacts(graph, model, s, originalQuality, nodeImpacts, impactValuesCalculator, level + 1);

        var childLabel = s.Label();
        var childSymbolNode = graph.GetNode(childLabel, level + 1);
        if (childSymbolNode == null)
          throw new ArgumentException("SymbolNode cannot be null!");

        if (symbolNode.OutEdges == null || symbolNode.OutEdges.Count == 0)
          symbolNode.AddForwardArc(childSymbolNode);
        else {
          var arc = symbolNode.OutEdges.Find(e => e.Target == childSymbolNode);
          if (arc == null)
            symbolNode.AddForwardArc(childSymbolNode);
          else arc.Weight += 1;
        }
      }
    }

    private static void WriteGraphAndImpacts(FPGraph graph, IDictionary<SymbolNode, IList<double>> nodeImpacts, string path, double pruneFactor = 0.1) {
      var nl = Environment.NewLine;
      const string shape = "rectangle";

      var avgImpacts = nodeImpacts.ToDictionary(n => n.Key, n => n.Value.Average());

      double max = avgImpacts.Values.Max();
      double min = avgImpacts.Values.Min();

      long total = (long)graph.Nodes.Sum(node => node.Weight);

      var tuples = (from l in graph.Levels.ToList()
                    let sum = l.Value.Sum(n => n.Weight)
                    from node in l.Value
                    where node.Weight / sum > pruneFactor
                    select new Tuple<SymbolNode, int, double>(node, l.Key, node.Weight / sum)
                   ).ToList();

      using (var file = new StreamWriter(path)) {
        var sb = new StringBuilder();
        file.WriteLine("digraph {");

        var hashset = new HashSet<SymbolNode>(tuples.Select(t => t.Item1));
        foreach (var tuple in tuples) {
          var node = tuple.Item1;
          var level = tuple.Item2;
          node.Label = node.Label + ":" + level;
          var relativeWeight = tuple.Item3;
          var impact = avgImpacts[node];
          if (double.IsInfinity(impact)) {
            throw new ArgumentOutOfRangeException("Impact value cannot be infinite!");
          }
          Color color;
          if (impact.IsAlmost(0.0)) {
            color = Color.White;
          } else if (impact < 0.0) {
            color = Color.FromArgb((int)(impact / min * 255), Color.Red);
          } else {
            color = Color.FromArgb((int)(impact / max * 255), Color.Green);
          }
          file.WriteLine("\t\"" + node.Label + "\" [shape=" + shape + ", style=filled, fillcolor=\"" + color.ToHex() + "\""
                         + ", label=\"" + node.Label + "\\n" + string.Format("{0:0.00%}", node.Weight / total)
                         + "\\n" + string.Format("{0:0.00%}", relativeWeight) + "\", rank=same]");
        }
        foreach (var node in tuples.Select(t => t.Item1)) {
          if (node.OutEdges == null || node.OutEdges.Count == 0) continue;
          foreach (var arc in node.OutEdges) {
            if (!hashset.Contains(arc.Target)) continue;
            //            double relativeWeight = arc.Weight / node.OutEdges.Sum(a => a.Weight);
            sb.Clear();
            sb.Append("\t\"" + node.Label + "\" -> \"" + arc.Target.Label + "\""
              //                        + "[label=\"" + string.Format("{0:0.00%}", relativeWeight) + "\"]"
                      );
            file.WriteLine(sb);
          }
        }
        file.WriteLine("}");
      }
    }
  }
}