Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 13481 was 13479, checked in by bburlacu, 9 years ago

#1772: Improve caching in TraceCalculator

File size: 14.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
37    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>> traceCache;
38    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
39
40    public bool UpdateVertexWeights { get; set; }
41    public bool UpdateSubtreeWeights { get; set; }
42    public bool CacheTraceNodes { get; set; }
43
44    public int TraceCacheHits { get; set; }
45
46    public TraceCalculator() {
47      ResetState();
48    }
49
50    [StorableConstructor]
51    protected TraceCalculator(bool deserializing) : base(deserializing) { }
52
53    protected TraceCalculator(TraceCalculator original, Cloner cloner)
54      : base(original, cloner) {
55    }
56
57    public override IDeepCloneable Clone(Cloner cloner) {
58      return new TraceCalculator(this, cloner);
59    }
60
61    public void ResetState() {
62      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
63      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
64      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>>();
65    }
66
67    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool updateVertexWeights = false, bool updateSubtreeWeights = false, bool cacheTraceNodes = true) {
68      var tc = new TraceCalculator {
69        UpdateVertexWeights = updateSubtreeWeights,
70        UpdateSubtreeWeights = updateSubtreeWeights,
71        CacheTraceNodes = cacheTraceNodes
72      };
73      tc.Trace(node, subtreeIndex);
74      return tc.TraceGraph;
75    }
76
77    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool resetState = true) {
78      if (resetState) ResetState();
79      TraceRecursive(node, subtreeIndex);
80      return TraceGraph;
81    }
82
83    /// <summary>
84    /// This method starts from a given vertex in the genealogy graph and works its way
85    /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
86    /// This method will skip genealogy graph nodes that did not have an influence on the
87    /// structure of the tracked subtree.
88    ///
89    /// Only genealogy nodes which did have an influence are added (as copies) to the trace
90    /// and are consequently called 'trace nodes'.
91    ///
92    /// The arcs connecting trace nodes hold information about the locations of the subtrees
93    /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
94    /// where:
95    /// - si is the subtree index in the current trace node
96    /// - fi is the fragment index in the current trace node
97    /// - lastSi is the subtree index in the previous trace node
98    /// - lastFi is the subtree index in the previous trace node
99    /// </summary>
100    /// <param name="node">The current node in the genealogy graph</param>
101    /// <param name="subtreeIndex">The index of the traced subtree</param>
102    /// <param name="last">The last added node in the trace graph</param>
103    /// <param name="lastSi">The subtree index in the last added individual</param>
104    /// <param name="lastFi">The fragment index in the last added individual</param>
105    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null, int lastSi = -1, int lastFi = -1) {
106      var g = node;
107      int si = subtreeIndex; // subtree index
108      int fi = 0; // fragment index
109      while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
110        if (!(si < g.Data.Length)) throw new ArgumentOutOfRangeException("The subtree index exceeds the size of the tree.");
111        var inArcs = (List<IArc>)((IVertex)g).InArcs;
112        var fragment = (IFragment<ISymbolicExpressionTreeNode>)((IGenealogyGraphArc)inArcs.Last()).Data;
113        if (fragment == null) {
114          // TODO: think about what the correct behavior should be here (seems good so far)
115          // the node is either an elite node or (in rare cases) no fragment was transferred
116          g = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
117          continue;
118        }
119
120        fi = fragment.Index1; // fragment index
121        int fl = fragment.Root.GetLength(); // fragment length
122        int sl = NodeAt(g.Data, si).GetLength(); // subtree length
123
124        #region trace crossover
125        if (inArcs.Count == 2) {
126          var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
127          var parent1 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[1].Source;
128          if (fi == si) {
129            g = parent1;
130            si = fragment.Index2;
131            continue;
132          }
133          if (fi < si) {
134            if (fi + fl > si) {
135              // fragment contains subtree
136              g = parent1;
137              si += fragment.Index2 - fi;
138            } else {
139              // fragment distinct from subtree
140              g = parent0;
141              si += NodeAt(g.Data, fi).GetLength() - fl;
142            }
143            continue;
144          }
145          if (fi > si) {
146            if (fi < si + sl) {
147              // subtree contains fragment => branching point in the fragment graph
148              var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
149              if (CacheTraceNodes) {
150                var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, si, n, si, fi);
151                var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent1, fragment.Index2, n, si, fi);
152                if (!traceCache.Contains(t0)) {
153                  traceCache.Add(t0);
154                  TraceRecursive(parent0, si, n, si, fi);
155                } else {
156                  TraceCacheHits++;
157                }
158                if (!traceCache.Contains(t1)) {
159                  traceCache.Add(t1);
160                  TraceRecursive(parent1, fragment.Index2, n, si, fi);
161                } else {
162                  TraceCacheHits++;
163                }
164              } else {
165                TraceRecursive(parent0, si, n, si, fi);
166                TraceRecursive(parent1, fragment.Index2, n, si, fi);
167              }
168              break;
169            } else {
170              // subtree and fragment are distinct.
171              g = parent0;
172              continue;
173            }
174          }
175        }
176        #endregion
177        #region trace mutation
178        // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
179        // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
180        if (inArcs.Count == 1) {
181          var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
182          Debug.Assert(fragment.Index1 == fragment.Index2);
183          // check if the subtree and the fragment overlap => branch out
184          if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
185            var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
186            int i = si < fi ? si : fi;
187            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, i, n, si, fi);
188            if (!(CacheTraceNodes && traceCache.Contains(t))) {
189              TraceRecursive(parent0, i, n, si, fi);
190              traceCache.Add(t);
191            }
192            break;
193          } else {
194            // if they don't overlap, go up
195            g = parent0;
196            if (fi < si)
197              si += NodeAt(g.Data, fi).GetLength() - fl;
198            continue;
199          }
200        }
201        #endregion
202        throw new InvalidOperationException("A node cannot have more than two parents");
203      }
204      // when we are out of the while the last vertex must be connected with the current one
205      // if there is no last vertex, it means the tracing reached the top of the genealogy graph
206      if (last != null) {
207        var current = AddTraceNode(g);
208        if (current.Rank.IsAlmost(0)) fi = -1; // if current is part of the initial population there will be no fragment
209        var td = new TraceData(si, fi, lastSi, lastFi);
210#if DEBUG
211        var currentLength = current.Data.Length;
212        var lastLength = last.Data.Length;
213
214        if (!(si < currentLength))
215          throw new ArgumentOutOfRangeException(string.Format("Subtree index {0} exceeds tree length ({1}", si, currentLength));
216
217        if (!(fi < currentLength))
218          throw new ArgumentOutOfRangeException(string.Format("Fragment index {0} exceeds tree length ({1}", fi, currentLength));
219
220        if (!(lastSi < lastLength))
221          throw new ArgumentOutOfRangeException(string.Format("Last subtree index {0} exceeds tree length ({1}", lastSi, lastLength));
222
223        if (!(lastFi < lastLength))
224          throw new ArgumentOutOfRangeException(string.Format("Last fragment index {0} exceeds tree length ({1}", lastFi, lastLength));
225#endif
226        ConnectLast(current, last, td);
227      }
228    }
229
230    /// <summary>
231    /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
232    /// 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.
233    /// </summary>
234    /// <param name="g">The genealogy graph node</param>
235    /// <param name="si">The subtree index</param>
236    /// <param name="fi">The fragment index</param>
237    /// <returns></returns>
238    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g) {
239      var n = TraceGraph.GetByContent(g.Data);
240      if (n == null) {
241        n = g.Copy();
242        TraceGraph.AddVertex(n);
243      }
244      return n;
245    }
246
247    // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
248    // this caching will be even more effective with larger tree sizes
249    private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
250      List<ISymbolicExpressionTreeNode> list;
251      nodeListCache.TryGetValue(tree, out list);
252      if (list == null) {
253        list = tree.IterateNodesPrefix().ToList();
254        nodeListCache[tree] = list;
255      }
256      return list[index];
257    }
258
259    /// <summary>
260    /// 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
261    /// of the genealogy graph node @g. 
262    /// </summary>
263    /// <param name="current">The current node in the genealogy graph</param>
264    /// <param name="last">The last added node in the trace graph</param>
265    /// <param name="td">The trace data specifying the preorder indices of the subtree and fragment in the @current and @last vertices</param>   
266    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, TraceData td) {
267      // TODO: more testing
268      var inArcs = (List<IArc>)((IVertex)last).InArcs; // using the InArcs seems to be slightly more efficient than using the OutArcs
269      var arc = inArcs.FirstOrDefault(a => a.Source == current && ((IArc<IDeepCloneable>)a).Data.Equals(td));
270      if (arc == null) {
271        arc = new GenealogyGraphArc(current, last) { Data = td };
272        TraceGraph.AddArc(arc);
273      }
274      if (UpdateVertexWeights) {
275        arc.Weight++;
276        current.Weight++;
277      }
278      if (UpdateSubtreeWeights) {
279        var subtree = NodeAt(current.Data, td.SubtreeIndex);
280        foreach (var s in subtree.IterateNodesPrefix())
281          s.NodeWeight++;
282      }
283    }
284  }
285
286  public class TraceData : Tuple<int, int, int, int>, IDeepCloneable {
287    public TraceData(int currentSubtreeIndex, int currentFragmentIndex, int lastSubtreeIndex, int lastFragmentIndex)
288      : base(currentSubtreeIndex, currentFragmentIndex, lastSubtreeIndex, lastFragmentIndex) {
289    }
290
291    public int SubtreeIndex { get { return Item1; } }
292    public int FragmentIndex { get { return Item2; } }
293    public int LastSubtreeIndex { get { return Item3; } }
294    public int LastFragmentIndex { get { return Item4; } }
295    public object Clone() {
296      return new TraceData(SubtreeIndex, FragmentIndex, LastSubtreeIndex, LastFragmentIndex);
297    }
298
299    protected TraceData(TraceData original, Cloner cloner) :
300      base(original.SubtreeIndex, original.FragmentIndex, original.LastFragmentIndex, original.LastFragmentIndex) {
301    }
302
303    public IDeepCloneable Clone(Cloner cloner) {
304      return cloner.Clone(this);
305    }
306  }
307
308  internal static class Util {
309    // shallow node copy (does not clone the data or the arcs)
310    #region some helper methods for shortening the tracing code
311    public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
312      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
313    }
314    #endregion
315  }
316}
Note: See TracBrowser for help on using the repository browser.