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

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

#1772: Simplified GenealogyGraph (and related components) API in an effort to improve speed and memory consumption (eg., by sharing the same arc when walking the graph in both directions: parent-child and child-parent).

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.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(parent, fragmentNode);
61            parent.AddForwardArc(arc);
62            fragmentNode.AddReverseArc(arc);
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(parent, fragmentNode);
94            parent.AddForwardArc(arc);
95            fragmentNode.AddReverseArc(arc);
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(parent, fragmentNode);
137                parent.AddForwardArc(arc);
138                fragmentNode.AddReverseArc(arc);
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.