Changeset 10827 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs
- Timestamp:
- 05/08/14 17:26:32 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs
r10797 r10827 10 10 using IGraphNode = HeuristicLab.EvolutionTracking.IGenealogyGraphNode<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>; 11 11 12 namespace HeuristicLab.Problems.DataAnalysis.Symbolic .Views{12 namespace HeuristicLab.Problems.DataAnalysis.Symbolic { 13 13 public static class SymbolicDataAnalysisExpressionTracing { 14 14 public static IGenealogyGraph<IFragment<ISymbolicExpressionTreeNode>> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex) { … … 40 40 break; 41 41 } 42 42 var parents = node.Parents.ToList(); 43 43 if (node.IsElite) { 44 node = node.Parents.First(); 44 // skip elite, go up the graph to original individual 45 node = parents[0]; 45 46 continue; 46 } // skip elite, go up the graph to original individual 47 47 } 48 var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data; 49 if (fragment == null) { 50 // the fragment can be null when crossover or mutation did not actually make any change => then we skip 51 node = parents[0]; 52 continue; 53 } 54 var fragmentLength = fragment.Root.GetLength(); 48 55 var tree = node.Content; 49 56 var subtree = tree.NodeAt(index); 50 57 var subtreeLength = subtree.GetLength(); 51 58 52 var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data; 53 if (fragment == null) break; 54 var fragmentLength = fragment.Root.GetLength(); 59 if (parents.Count == 1) { 60 // we are tracing a mutation operation 61 var fragmentNode = new FragmentNode { 62 Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree }, 63 Rank = node.Rank 64 }; 65 if (parent != null) { 66 var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode }; 67 parent.AddForwardArc(arc); 68 } 69 yield return fragmentNode; 70 var up = Trace(parents[0], fragment.Index1, fragmentNode); 71 foreach (var v in up) { yield return v; } 72 break; 73 } 55 74 56 if (fragment.Index1 == index) { 57 node = node.Parents.Last(); // take second parent which contains the fragment 58 index = fragment.Index2; 59 } else if (fragment.Index1 < index) { 60 if (fragment.Index1 + fragmentLength > index) { 61 node = node.Parents.Last(); // fragment contains subtree, take second parent 62 index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment 63 } else { 64 // fragment distinct from subtree 65 node = node.Parents.First(); // take first parent which contains the subtree 66 index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes 75 if (parents.Count == 2) { 76 // we are tracing a crossover operation 77 if (fragment.Index1 == index) { 78 node = parents[1]; // take second parent which contains the fragment 79 index = fragment.Index2; 80 continue; 67 81 } 68 } else if (fragment.Index1 > index) { 69 if (fragment.Index1 < index + subtreeLength) { 70 // subtree contains fragment => bifurcation point in the fragment graph 71 var fragmentNode = new FragmentNode { 72 Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree }, 73 Rank = node.Rank 74 }; 75 if (parent != null) { 76 var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode }; 77 parent.AddForwardArc(arc); 82 83 if (fragment.Index1 < index) { 84 if (fragment.Index1 + fragmentLength > index) { 85 node = parents[1]; // fragment contains subtree, take second parent 86 index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment 87 } else { 88 // fragment distinct from subtree 89 node = parents[0]; // take first parent which contains the subtree 90 index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes 78 91 } 79 fragmentNode.Content.Index1 = fragment.Index1 - index;80 yield return fragmentNode;92 continue; 93 } 81 94 82 var left = Trace(node.Parents.First(), index, fragmentNode); // trace subtree 95 if (fragment.Index1 > index) { 96 if (fragment.Index1 < index + subtreeLength) { 97 // subtree contains fragment => bifurcation point in the fragment graph 98 var fragmentNode = new FragmentNode { 99 Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree }, 100 Rank = node.Rank 101 }; 102 if (parent != null) { 103 var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode }; 104 parent.AddForwardArc(arc); 105 } 106 fragmentNode.Content.Index1 = fragment.Index1 - index; 107 yield return fragmentNode; 83 108 84 if (node.Parents.Last().Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) { 85 throw new Exception("Fragment lengths should match!"); 109 if (parents[1].Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) { 110 throw new Exception("Fragment lengths should match!"); 111 } 112 // the two paths below ("left" and "right") correspond to the subtree and the fragment, respectively 113 var left = Trace(parents[0], index, fragmentNode); // trace subtree 114 var right = Trace(parents[1], fragment.Index2, fragmentNode); // trace fragment 115 foreach (var v in left.Concat(right)) { yield return v; } 116 break; 117 } else { 118 node = parents[0]; // fragment distinct from subtree: update node, index remains unchanged 86 119 } 87 var right = Trace(node.Parents.Last(), fragment.Index2, fragmentNode); // trace fragment88 foreach (var v in left.Concat(right)) { yield return v; }89 break;90 } else {91 node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged92 120 } 93 121 } … … 101 129 } 102 130 #region some helper methods for shortening the tracing code 103 104 131 private static void AddChild(this IGenealogyGraphNode parent, IGenealogyGraphNode child) { 105 132 parent.AddForwardArc(child);
Note: See TracChangeset
for help on using the changeset viewer.