source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs @ 11751

Last change on this file since 11751 was 11751, checked in by bburlacu, 7 years ago

#1772: TraceCalculator: Added static TraceSubtree method, renamed private Trace method to TraceRecursive to avoid method name confusion.

File size: 10.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Diagnostics;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.EvolutionTracking;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
34  [StorableClass]
35  public class TraceCalculator : Item {
36    private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
37    private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
38
39    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
40
41    public TraceCalculator() {
42      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
43      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
44    }
45
46    protected TraceCalculator(TraceCalculator original, Cloner cloner)
47      : base(original, cloner) {
48    }
49
50    public override IDeepCloneable Clone(Cloner cloner) {
51      return new TraceCalculator(this, cloner);
52    }
53
54    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
55      var tc = new TraceCalculator();
56      tc.Trace(node, subtreeIndex);
57      return tc.TraceGraph;
58    }
59
60    public IGenealogyGraph<ISymbolicExpressionTree> PartialTrace(IGenealogyGraphNode<ISymbolicExpressionTree> node,
61      int subtreeIndex, ISymbolicExpressionTreeNode subtree) {
62      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
63      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
64      return null;
65    }
66
67    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
68      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
69      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
70      TraceRecursive(node, subtreeIndex);
71      return traceGraph;
72    }
73
74    /// <summary>
75    /// This method starts from a given vertex in the genealogy graph and works its way
76    /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
77    /// This method will skip genealogy graph nodes that did not have an influence on the
78    /// structure of the tracked subtree.
79    ///
80    /// Only genealogy nodes which did have an influence are added (as copies) to the trace
81    /// and are consequently called 'trace nodes'.
82    ///
83    /// The arcs connecting trace nodes hold information about the locations of the subtrees
84    /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
85    /// where:
86    /// - si is the subtree index in the current trace node
87    /// - fi is the fragment index in the current trace node
88    /// - lastSi is the subtree index in the previous trace node
89    /// - lastFi is the subtree index in the previous trace node
90    /// </summary>
91    /// <param name="node">The current node in the genealogy graph</param>
92    /// <param name="subtreeIndex">The index of the traced subtree</param>
93    /// <param name="last">The last added node in the trace graph</param>
94    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
95      var g = node;
96      int si = subtreeIndex;
97      while (g.Parents.Any()) {
98        Debug.Assert(si < g.Data.Length);
99        var parents = g.Parents.ToList();
100        var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
101        if (fragment == null) {
102          //          if (parents.Count == 2)
103          //            throw new Exception("There should always be a crossover fragment.");
104          // the node is either an elite node or (in rare cases) no fragment was transferred
105          g = parents[0];
106          continue;
107        }
108
109        int fi = fragment.Index1;               // fragment index
110        int fl = fragment.Root.GetLength();     // fragment length
111        int sl = g.Data.NodeAt(si).GetLength(); // subtree length
112
113        #region trace crossover
114        if (parents.Count == 2) {
115          if (fi == si) {
116            g = parents[1];
117            si = fragment.Index2;
118            continue;
119          }
120          if (fi < si) {
121            if (fi + fl > si) {
122              // fragment contains subtree
123              g = parents[1];
124              si += fragment.Index2 - fi;
125            } else {
126              // fragment distinct from subtree
127              g = parents[0];
128              si += g.Data.NodeAt(fi).GetLength() - fl;
129            }
130            continue;
131          }
132          if (fi > si) {
133            if (fi < si + sl) {
134              // subtree contains fragment => branching point in the fragment graph
135              var n = GetTraceNode(g, si, fi);
136              TraceRecursive(parents[0], si, n);
137              TraceRecursive(parents[1], fragment.Index2, n);
138              break;
139            } else {
140              // subtree and fragment are distinct.
141              g = parents[0];
142              continue;
143            }
144          }
145        }
146        #endregion
147        #region trace mutation
148        // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
149        // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
150        if (parents.Count == 1) {
151          Debug.Assert(fragment.Index1 == fragment.Index2);
152          // check if the subtree and the fragment overlap => branch out
153          if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
154            var n = GetTraceNode(g, si, fi);
155            int i = si < fi ? si : fi;
156            TraceRecursive(parents[0], i, n);
157            break;
158          } else {
159            // if they don't overlap, go up
160            g = parents[0];
161            if (fi < si)
162              si += g.Data.NodeAt(fi).GetLength() - fl;
163            continue;
164          }
165        }
166        #endregion
167        throw new InvalidOperationException("A node cannot have more than two parents");
168      }
169      // when we are out of the while the last vertex must be connected with the current one
170      ConnectLast(g, si, last);
171    }
172
173    /// <summary>
174    /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
175    /// If the trace graph does not contain such a node, one is created by performing a shallow copy of g, then inserted into the trace graph.
176    /// </summary>
177    /// <param name="g">The genealogy graph node</param>
178    /// <param name="si">The subtree index</param>
179    /// <param name="fi">The fragment index</param>
180    /// <returns></returns>
181    private IGenealogyGraphNode<ISymbolicExpressionTree> GetTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
182      var n = traceGraph.GetByContent(g.Data);
183      if (n == null) {
184        n = g.Copy();
185        traceGraph.AddVertex(n);
186        Debug.Assert(!traceMap.ContainsKey(n));
187        traceMap[n] = new Tuple<int, int>(si, fi);
188      }
189      return n;
190    }
191
192    /// <summary>
193    /// Connect the current node of the trace graph with the node that was previously added (@last). The current node of the trace graph is determined by the content
194    /// of the genealogy graph node @g. 
195    /// </summary>
196    /// <param name="g">The current node in the genealogy graph</param>
197    /// <param name="si">The index of the traced subtree</param>
198    /// <param name="last">The last added node in the trace graph</param>
199    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last) {
200      IFragment<ISymbolicExpressionTreeNode> fragment = g.Parents.Any() ? (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data : null;
201      int fi = fragment == null ? 0 : fragment.Index1; // fragment index
202      var n = GetTraceNode(g, si, fi); // will append n to the trace graph if it does not exist
203      if (last == null)
204        return;
205      var lastTraceData = traceMap[last];
206      int lastSi = lastTraceData.Item1; // last subtree index
207      int lastFi = lastTraceData.Item2; // last fragment index
208      var td = new Tuple<int, int, int, int>(si, fi, lastSi, lastFi); // trace data
209      var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td));
210      if (arc == null) {
211        arc = new GenealogyGraphArc(last, n) { Data = td };
212        traceGraph.AddArc(arc);
213      }
214    }
215  }
216
217  internal static class Util {
218    // shallow node copy (does not clone the data or the arcs)
219    #region some helper methods for shortening the tracing code
220    public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
221      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
222    }
223    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
224      return NodeAt(tree.Root, index);
225    }
226    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
227      return root.IterateNodesPrefix().ElementAt(index);
228    }
229    #endregion
230  }
231}
Note: See TracBrowser for help on using the repository browser.