Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772: Small changes and improvements to TraceCalculator.cs

File size: 9.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Common;
5using HeuristicLab.Core;
6using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
7using HeuristicLab.EvolutionTracking;
8using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
9
10namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
11  [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
12  [StorableClass]
13  public class TraceCalculator : Item {
14    private readonly IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
15    private readonly Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
16
17    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
18
19    public TraceCalculator() {
20      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
21      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
22    }
23
24    protected TraceCalculator(TraceCalculator original, Cloner cloner)
25      : base(original, cloner) {
26    }
27
28    public override IDeepCloneable Clone(Cloner cloner) {
29      return new TraceCalculator(this, cloner);
30    }
31
32    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
33      var tc = new TraceCalculator();
34      tc.Trace(node, subtreeIndex);
35      return tc.TraceGraph;
36    }
37
38    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
39      traceGraph.Clear();
40      traceMap.Clear();
41      Trace(node, subtreeIndex, null);
42      return traceGraph;
43    }
44
45    /// <summary>
46    /// This method starts from a given vertex in the genealogy graph and works its way
47    /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
48    /// This method will skip genealogy graph nodes that did not have an influence on the
49    /// structure of the tracked subtree.
50    ///
51    /// Only genealogy nodes which did have an influence are added (as copies) to the trace
52    /// and are consequently called 'trace nodes'.
53    ///
54    /// The arcs connecting trace nodes hold information about the locations of the subtrees
55    /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
56    /// where:
57    /// - si is the subtree index in the current trace node
58    /// - fi is the fragment index in the current trace node
59    /// - lastSi is the subtree index in the previous trace node
60    /// - lastFi is the subtree index in the previous trace node
61    /// </summary>
62    /// <param name="g">The current node in the genealogy graph</param>
63    /// <param name="si">The index of the traced subtree</param>
64    /// <param name="last">The last added node in the trace graph</param>
65    private void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
66      while (g.Parents.Any()) {
67        var parents = g.Parents.ToList();
68        var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
69        if (fragment == null) {
70          // the node is either an elite node or (in rare cases) no fragment was transferred
71          g = parents[0];
72          continue;
73        }
74
75        int fragmentLength = fragment.Root.GetLength();
76        int subtreeLength = g.Data.NodeAt(si).GetLength();
77
78        #region trace crossover
79        if (parents.Count == 2) {
80          if (fragment.Index1 == si) {
81            g = parents[1];
82            si = fragment.Index2;
83            continue;
84          }
85          if (fragment.Index1 < si) {
86            if (fragment.Index1 + fragmentLength > si) {
87              // fragment contains subtree
88              g = parents[1];
89              si += fragment.Index2 - fragment.Index1;
90            } else {
91              // fragment distinct from subtree
92              g = parents[0];
93              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
94            }
95            continue;
96          }
97          if (fragment.Index1 > si) {
98            if (fragment.Index1 < si + subtreeLength) {
99              // subtree contains fragment => branching point in the fragment graph
100              var n = traceGraph.GetByContent(g.Data);
101              if (n == null) {
102                n = g.Copy();
103                traceGraph.AddVertex(n);
104                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
105              }
106
107              Trace(parents[0], si, n);
108              Trace(parents[1], fragment.Index2, n);
109              break;
110            } else {
111              // subtree and fragment are distinct.
112              g = parents[0];
113              continue;
114            }
115          }
116        }
117        #endregion
118        #region trace mutation
119        if (parents.Count == 1) {
120          if (si == fragment.Index1) {
121            // fragment and subtree coincide
122            // since mutation can potentially alter trees quite drastically, we branch here,
123            // in order not to miss any changes
124            var n = traceGraph.GetByContent(g.Data);
125            if (n == null) {
126              n = g.Copy();
127              traceGraph.AddVertex(n);
128              traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
129            }
130            Trace(parents[0], si, n);
131            break;
132          }
133          if (fragment.Index1 < si) {
134            if (si < fragment.Index1 + fragmentLength) {
135              // fragment contains subtree
136              g = parents[0];
137              si = fragment.Index2;
138            } else {
139              // fragment and subtree are distinct
140              // since the fragment occurs before the subtree in the prefix node ordering
141              // the subtree index must be adjusted according to the fragment length
142              g = parents[0];
143              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
144            }
145            continue;
146          }
147          if (si < fragment.Index1) {
148            // subtree occurs before fragment in the prefix node ordering
149            if (fragment.Index1 < si + subtreeLength) {
150              // subtree contains fragment, we are interested to see what the subtree looked like before
151              // but we also want to keep track of what it looks like now, therefore we branch here
152              var n = traceGraph.GetByContent(g.Data);
153              if (n == null) {
154                n = g.Copy();
155                traceGraph.AddVertex(n);
156                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
157              }
158              Trace(parents[0], si, n);
159              break;
160            } else {
161              // fragment and subtree are distinct, subtree index stays the same
162              // since the subtree comes before the fragment in the prefix node ordering
163              g = parents[0];
164              continue;
165            }
166          }
167        }
168        #endregion
169        throw new InvalidOperationException("A node cannot have more than two parents");
170      }
171      // when we are out of the while the last vertex must be connected with the current one
172      ConnectLast(g, si, last);
173    }
174
175    /// <summary>
176    /// 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
177    /// of the genealogy graph node @g. 
178    /// </summary>
179    /// <param name="g">The current node in the genealogy graph</param>
180    /// <param name="si">The index of the traced subtree</param>
181    /// <param name="last">The last added node in the trace graph</param>
182    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last) {
183      IFragment<ISymbolicExpressionTreeNode> fragment = g.Parents.Any() ? (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data : null;
184      var n = traceGraph.GetByContent(g.Data);
185      if (n == null) {
186        n = g.Copy();
187        traceGraph.AddVertex(n);
188      }
189      int fi = fragment == null ? 0 : fragment.Index1; // fragment index
190      traceMap[n] = new Tuple<int, int>(si, fi);
191      if (last == null)
192        return;
193      var lastTraceData = traceMap[last];
194      int lastSi = lastTraceData.Item1; // last subtree index
195      int lastFi = lastTraceData.Item2; // last fragment index
196      var td = new Tuple<int, int, int, int>(si, fi, lastSi, lastFi); // trace data
197      var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td));
198      if (arc != null)
199        return;
200      arc = new GenealogyGraphArc(last, n) { Data = td };
201      traceGraph.AddArc(arc);
202    }
203  }
204
205  internal static class Util {
206    // shallow node copy (does not clone the data or the arcs)
207    public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
208      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
209    }
210    #region some helper methods for shortening the tracing code
211    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
212      return NodeAt(tree.Root, index);
213    }
214    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
215      return root.IterateNodesPrefix().ElementAt(index);
216    }
217    #endregion
218  }
219}
Note: See TracBrowser for help on using the repository browser.