source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs @ 10888

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

#1772: Introduced separate class for FragmentNodes and adjusted tracing code. Fixed small bug creating the genealogy graph.

File size: 7.6 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.IO;
25using System.Linq;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using HeuristicLab.EvolutionTracking;
28
29namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
30  public static class SymbolicDataAnalysisExpressionTracing {
31    public static FragmentGraph TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex) {
32      var graph = new FragmentGraph { AllowDuplicateContent = true };
33      var nodes = Trace(graphNode, subtreeIndex);
34      foreach (var n in nodes) {
35        graph.AddVertex(n);
36      }
37      return graph;
38    }
39    /// <summary>
40    /// Traces a subtree in a genealogy of individuals, tracking down it's genetic components
41    /// </summary>
42    /// <param name="graphNode">The point in the genealogy where to start the tracing from</param>
43    /// <param name="subtreeIndex">The traced subtree preorder index in the current tree</param>
44    /// <param name="parentNode">The parent node in the fragment graph if there is any</param>
45    /// <returns></returns>
46    private static IEnumerable<FragmentNode> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex, FragmentNode parentNode = null) {
47      var node = graphNode; // current node
48      var index = subtreeIndex; // current index
49      var parent = parentNode; // current parent
50
51      while (true) {
52        if (!node.Parents.Any()) {
53          var fragmentNode = new FragmentNode {
54            Content = node,
55            SubtreeIndex = index,
56          };
57          if (parent != null) {
58            var arc = new Arc(parent, fragmentNode);
59            parent.AddForwardArc(arc);
60            fragmentNode.AddReverseArc(arc);
61          }
62          yield return fragmentNode; // no tracing if there are no parents
63          break;
64        }
65        var parents = node.Parents.ToList();
66        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
67
68        if (node.IsElite || fragment == null) {
69          // skip elite, go up the graph to original individual
70          node = parents[0];
71          continue;
72        }
73        var fragmentLength = fragment.Root.GetLength();
74        var tree = node.Content;
75        var subtree = tree.NodeAt(index);
76        var subtreeLength = subtree.GetLength();
77
78        #region mutation tracing
79        if (parents.Count == 1) {
80          // we are tracing a mutation operation
81          var fragmentNode = new FragmentNode {
82            Content = node,
83            SubtreeIndex = index,
84            FragmentIndex = fragment.Index1
85          };
86          if (parent != null) {
87            var arc = new Arc(parent, fragmentNode);
88            parent.AddForwardArc(arc);
89            fragmentNode.AddReverseArc(arc);
90          }
91          node = parents[0];
92          if (subtreeIndex == fragment.Index1) {
93            // index stays the same
94          } else if (fragment.Index1 < subtreeIndex) {
95            if (subtreeIndex < fragment.Index1 + fragmentLength) {
96              // subtree contained in fragment, index stays the same
97            } else {
98              index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength;
99            }
100          } else if (subtreeIndex < fragment.Index1) {
101            if (fragment.Index1 < subtreeIndex + subtreeLength) {
102              // subtree contains fragment
103              index = fragment.Index1;
104            } else {
105              // index stays the same
106            }
107          }
108
109          yield return fragmentNode;
110          var up = Trace(node, index, fragmentNode);
111          foreach (var v in up) { yield return v; }
112          break;
113        }
114        #endregion
115
116        #region crossover tracing
117        if (parents.Count == 2) {
118          // we are tracing a crossover operation
119          if (fragment.Index1 == index) {
120            node = parents[1]; // take second parent which contains the fragment
121            index = fragment.Index2;
122            continue;
123          }
124
125          if (fragment.Index1 < index) {
126            if (fragment.Index1 + fragmentLength > index) {
127              node = parents[1]; // fragment contains subtree, take second parent
128              index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
129            } else {
130              // fragment distinct from subtree
131              node = parents[0]; // take first parent which contains the subtree
132              index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
133            }
134            continue;
135          }
136
137          if (fragment.Index1 > index) {
138            if (fragment.Index1 < index + subtreeLength) {
139              // subtree contains fragment => bifurcation point in the fragment graph
140              var fragmentNode = new FragmentNode {
141                Content = node,
142                SubtreeIndex = index,
143                FragmentIndex = fragment.Index1
144              };
145              if (parent != null) {
146                var arc = new Arc(parent, fragmentNode);
147                parent.AddForwardArc(arc);
148                fragmentNode.AddReverseArc(arc);
149              }
150              yield return fragmentNode;
151
152              if (parents[1].Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
153                throw new Exception("Fragment lengths should match!");
154              }
155              // the two paths below ("left" and "right") correspond to the subtree and the fragment, respectively
156              var left = Trace(parents[0], index, fragmentNode); // trace subtree
157              var right = Trace(parents[1], fragment.Index2, fragmentNode); // trace fragment
158              foreach (var v in left.Concat(right)) { yield return v; }
159              break;
160            } else {
161              node = parents[0]; // fragment distinct from subtree: update node, index remains unchanged
162            }
163          }
164        }
165        #endregion
166      }
167    }
168
169    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
170      var writer = new StringWriter();
171      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
172      return writer.ToString();
173    }
174    #region some helper methods for shortening the tracing code
175    private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
176      return NodeAt(tree.Root, position);
177    }
178    private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
179      return root.IterateNodesPrefix().ElementAt(position);
180    }
181    #endregion
182  }
183}
Note: See TracBrowser for help on using the repository browser.