Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772: Introduced TraceData class in order to make the semantics clear from the code. Changed arcs orientation in the trace graphs to match the orientation in the genealogy graph.

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