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

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

#1772: Added license headers where they were missing. Introduced an id map to the DirectedGraph to get graph vertices based on the id injected in the scopes by the genealogy analyzer.

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