Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12225 was 12225, checked in by bburlacu, 8 years ago

#1772: Work in progress for calculating sampling counts for subtrees in the population: updated TraceCalculator to aggregate tracing statistics, updated SymbolicDataAnalysisGenealogyGraphView, added SymbolicDataAnalysisSubtreeSampleCountAnalyzer.

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