Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772: Fixed bug and improved handling of elite individuals in the genealogy analyzer. Fixed minor bug in the tracing code. Other minor cosmetic improvements to the GenealogyGraph and FragmentGraphView.

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