Changeset 11473 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking
- Timestamp:
- 10/16/14 15:52:41 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs
r11458 r11473 9 9 10 10 namespace HeuristicLab.Problems.DataAnalysis.Symbolic { 11 12 13 11 [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")] 14 12 [StorableClass] 15 13 public class TraceCalculator : Item { 16 private IGenealogyGraphNode<ISymbolicExpressionTree> lastVisited;17 14 private readonly IGenealogyGraph<ISymbolicExpressionTree> traceGraph; 18 15 private readonly Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap; … … 39 36 } 40 37 41 public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) { 42 while (true) { 43 if (!node.Parents.Any()) { 44 if (node.Rank.IsAlmost(0) && lastVisited != null) { 45 var n = traceGraph.GetByContent(node.Data); 46 if (n == null) { 47 n = node.Copy(); 48 traceGraph.AddVertex(n); 49 } 50 if (n.InArcs.All(x => x.Source != lastVisited)) { 51 traceGraph.AddArc(lastVisited, n); 52 } 53 } 54 return; 55 } 56 57 var parents = node.Parents.ToList(); 58 59 var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data; 38 /// <summary> 39 /// This method starts from a given vertex in the genealogy graph and works its way 40 /// up the ancestry trying to track the structure of the subtree given by subtreeIndex. 41 /// This method will skip genealogy graph nodes that did not have an influence on the 42 /// structure of the tracked subtree. 43 /// 44 /// Only genealogy nodes which did have an influence are added (as copies) to the trace 45 /// and are consequently called 'trace nodes'. 46 /// 47 /// The arcs connecting trace nodes hold information about the locations of the subtrees 48 /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi), 49 /// where: 50 /// - si is the subtree index in the current trace node 51 /// - fi is the fragment index in the current trace node 52 /// - lastSi is the subtree index in the previous trace node 53 /// - lastFi is the subtree index in the previous trace node 54 /// </summary> 55 /// <param name="g">The current node in the genealogy graph</param> 56 /// <param name="si">The index of the traced subtree</param> 57 /// <param name="last">The last added node in the trace graph</param> 58 public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) { 59 while (g.Parents.Any()) { 60 var parents = g.Parents.ToList(); 61 var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data; 60 62 if (fragment == null) { 61 63 // the node is either an elite node or (in rare cases) no fragment was transferred 62 node= parents[0];64 g = parents[0]; 63 65 continue; 64 66 } 65 67 66 68 int fragmentLength = fragment.Root.GetLength(); 67 int subtreeLength = node.Data.NodeAt(subtreeIndex).GetLength();69 int subtreeLength = g.Data.NodeAt(si).GetLength(); 68 70 69 71 #region trace crossover 70 72 if (parents.Count == 2) { 71 if (fragment.Index1 == s ubtreeIndex) {72 node= parents[1];73 s ubtreeIndex= fragment.Index2;73 if (fragment.Index1 == si) { 74 g = parents[1]; 75 si = fragment.Index2; 74 76 continue; 75 77 } 76 if (fragment.Index1 < s ubtreeIndex) {77 if (fragment.Index1 + fragmentLength > s ubtreeIndex) {78 if (fragment.Index1 < si) { 79 if (fragment.Index1 + fragmentLength > si) { 78 80 // fragment contains subtree 79 node= parents[1];80 s ubtreeIndex+= fragment.Index2 - fragment.Index1;81 g = parents[1]; 82 si += fragment.Index2 - fragment.Index1; 81 83 } else { 82 84 // fragment distinct from subtree 83 node= parents[0];84 s ubtreeIndex += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;85 g = parents[0]; 86 si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; 85 87 } 86 88 continue; 87 89 } 88 if (fragment.Index1 > s ubtreeIndex) {89 if (fragment.Index1 < s ubtreeIndex+ subtreeLength) {90 if (fragment.Index1 > si) { 91 if (fragment.Index1 < si + subtreeLength) { 90 92 // subtree contains fragment => branching point in the fragment graph 91 var n = traceGraph.GetByContent( node.Data);93 var n = traceGraph.GetByContent(g.Data); 92 94 if (n == null) { 93 n = node.Copy();95 n = g.Copy(); 94 96 traceGraph.AddVertex(n); 95 traceMap[n] = new Tuple<int, int>(s ubtreeIndex, fragment.Index1);97 traceMap[n] = new Tuple<int, int>(si, fragment.Index1); 96 98 } 97 99 98 if (lastVisited != null) { 99 var lastTraceData = traceMap[lastVisited]; 100 int lastSi = lastTraceData.Item1; 101 int lastFi = lastTraceData.Item2; 102 var traceData = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1); 103 if (!n.InArcs.Any(a => a.Source == lastVisited && a.Data.Equals(traceData))) { 104 var arc = traceGraph.AddArc(lastVisited, n); 105 arc.Data = traceData; 106 } 107 } 108 109 lastVisited = n; 110 Trace(parents[0], subtreeIndex); 111 lastVisited = n; 112 Trace(parents[1], fragment.Index2); 100 Trace(parents[0], si, n); 101 Trace(parents[1], fragment.Index2, n); 113 102 break; 114 103 } else { 115 104 // subtree and fragment are distinct. 116 node= parents[0];105 g = parents[0]; 117 106 continue; 118 107 } … … 122 111 #region trace mutation 123 112 if (parents.Count == 1) { 124 if (subtreeIndex == fragment.Index1) { 125 // node = parents[0]; 126 var n = traceGraph.GetByContent(node.Data); 113 if (si == fragment.Index1) { 114 // fragment and subtree coincide 115 // since mutation can potentially alter trees quite drastically, we branch here, 116 // in order not to miss any changes 117 var n = traceGraph.GetByContent(g.Data); 127 118 if (n == null) { 128 n = node.Copy();119 n = g.Copy(); 129 120 traceGraph.AddVertex(n); 130 } 131 132 if (lastVisited != null) { 133 var arc = traceGraph.AddArc(lastVisited, n); 134 var lastTraceData = traceMap[lastVisited]; 135 int lastSi = lastTraceData.Item1; 136 int lastFi = lastTraceData.Item2; 137 var td = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1); 138 } 139 } 121 traceMap[n] = new Tuple<int, int>(si, fragment.Index1); 122 } 123 Trace(parents[0], si, n); 124 break; 125 } 126 if (fragment.Index1 < si) { 127 if (si < fragment.Index1 + fragmentLength) { 128 // fragment contains subtree 129 g = parents[0]; 130 si = fragment.Index2; 131 } else { 132 // fragment and subtree are distinct 133 // since the fragment occurs before the subtree in the prefix node ordering 134 // the subtree index must be adjusted according to the fragment length 135 g = parents[0]; 136 si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; 137 } 138 continue; 139 } 140 if (si < fragment.Index1) { 141 // subtree occurs before fragment in the prefix node ordering 142 if (fragment.Index1 < si + subtreeLength) { 143 // subtree contains fragment, we are interested to see what the subtree looked like before 144 // but we also want to keep track of what it looks like now, therefore we branch here 145 var n = traceGraph.GetByContent(g.Data); 146 if (n == null) { 147 n = g.Copy(); 148 traceGraph.AddVertex(n); 149 traceMap[n] = new Tuple<int, int>(si, fragment.Index1); 150 } 151 Trace(parents[0], si, n); 152 break; 153 } else { 154 // fragment and subtree are distinct, subtree index stays the same 155 // since the subtree comes before the fragment in the prefix node ordering 156 g = parents[0]; 157 continue; 158 } 159 } 160 } 140 161 #endregion 141 } else { 142 throw new InvalidOperationException("A node cannot have more than two parents"); 143 } 162 throw new InvalidOperationException("A node cannot have more than two parents"); 144 163 } 164 // when we are out of the while the last vertex must be connected with the current one 165 ConnectLast(g, si, last); 166 } 167 168 /// <summary> 169 /// Connect the current node of the trace graph with the node that was previously added (@last). The current node of the trace graph is determined by the content 170 /// of the genealogy graph node @g. 171 /// </summary> 172 /// <param name="g">The current node in the genealogy graph</param> 173 /// <param name="si">The index of the traced subtree</param> 174 /// <param name="last">The last added node in the trace graph</param> 175 private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last) { 176 IFragment<ISymbolicExpressionTreeNode> fragment = g.Parents.Any() ? (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data : null; 177 var n = traceGraph.GetByContent(g.Data); 178 if (n == null) { 179 n = g.Copy(); 180 traceGraph.AddVertex(n); 181 } 182 int fi = fragment == null ? 0 : fragment.Index1; // fragment index 183 traceMap[n] = new Tuple<int, int>(si, fi); 184 if (last == null) 185 return; 186 var lastTraceData = traceMap[last]; 187 int lastSi = lastTraceData.Item1; // last subtree index 188 int lastFi = lastTraceData.Item2; // last fragment index 189 var td = new Tuple<int, int, int, int>(si, fi, lastSi, lastFi); // trace data 190 var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td)); 191 if (arc != null) 192 return; 193 arc = new GenealogyGraphArc(last, n); 194 arc.Data = td; 195 traceGraph.AddArc(arc); 145 196 } 146 197 } 147 198 148 199 internal static class Util { 149 // shallow copy which does not clone the data and completely ignores arcs200 // shallow node copy (does not clone the data or the arcs) 150 201 public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) { 151 202 return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
Note: See TracChangeset
for help on using the changeset viewer.