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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.IO;
|
---|
25 | using System.Linq;
|
---|
26 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
27 | using HeuristicLab.EvolutionTracking;
|
---|
28 | using FragmentNode = HeuristicLab.EvolutionTracking.GenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
|
---|
29 | using IFragmentNode = HeuristicLab.EvolutionTracking.IGenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
|
---|
30 | using IGraphNode = HeuristicLab.EvolutionTracking.IGenealogyGraphNode<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>;
|
---|
31 |
|
---|
32 | namespace 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 | }
|
---|