Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 11473

Ignore:
Timestamp:
10/16/14 15:52:41 (10 years ago)
Message:

#1772: Finished the TraceCalculator, added tracing for mutation operations.

File:
1 edited

Unmodified
Added
Removed
• ## branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

 r11458 namespace HeuristicLab.Problems.DataAnalysis.Symbolic { [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")] [StorableClass] public class TraceCalculator : Item { private IGenealogyGraphNode lastVisited; private readonly IGenealogyGraph traceGraph; private readonly Dictionary, Tuple> traceMap; } public void Trace(IGenealogyGraphNode node, int subtreeIndex) { while (true) { if (!node.Parents.Any()) { if (node.Rank.IsAlmost(0) && lastVisited != null) { var n = traceGraph.GetByContent(node.Data); if (n == null) { n = node.Copy(); traceGraph.AddVertex(n); } if (n.InArcs.All(x => x.Source != lastVisited)) { traceGraph.AddArc(lastVisited, n); } } return; } var parents = node.Parents.ToList(); var fragment = (IFragment)node.InArcs.Last().Data; /// /// This method starts from a given vertex in the genealogy graph and works its way /// up the ancestry trying to track the structure of the subtree given by subtreeIndex. /// This method will skip genealogy graph nodes that did not have an influence on the /// structure of the tracked subtree. /// /// Only genealogy nodes which did have an influence are added (as copies) to the trace /// and are consequently called 'trace nodes'. /// /// The arcs connecting trace nodes hold information about the locations of the subtrees /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi), /// where: /// - si is the subtree index in the current trace node /// - fi is the fragment index in the current trace node /// - lastSi is the subtree index in the previous trace node /// - lastFi is the subtree index in the previous trace node /// /// The current node in the genealogy graph /// The index of the traced subtree /// The last added node in the trace graph public void Trace(IGenealogyGraphNode g, int si, IGenealogyGraphNode last = null) { while (g.Parents.Any()) { var parents = g.Parents.ToList(); var fragment = (IFragment)g.InArcs.Last().Data; if (fragment == null) { // the node is either an elite node or (in rare cases) no fragment was transferred node = parents[0]; g = parents[0]; continue; } int fragmentLength = fragment.Root.GetLength(); int subtreeLength = node.Data.NodeAt(subtreeIndex).GetLength(); int subtreeLength = g.Data.NodeAt(si).GetLength(); #region trace crossover if (parents.Count == 2) { if (fragment.Index1 == subtreeIndex) { node = parents[1]; subtreeIndex = fragment.Index2; if (fragment.Index1 == si) { g = parents[1]; si = fragment.Index2; continue; } if (fragment.Index1 < subtreeIndex) { if (fragment.Index1 + fragmentLength > subtreeIndex) { if (fragment.Index1 < si) { if (fragment.Index1 + fragmentLength > si) { // fragment contains subtree node = parents[1]; subtreeIndex += fragment.Index2 - fragment.Index1; g = parents[1]; si += fragment.Index2 - fragment.Index1; } else { // fragment distinct from subtree node = parents[0]; subtreeIndex += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; g = parents[0]; si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; } continue; } if (fragment.Index1 > subtreeIndex) { if (fragment.Index1 < subtreeIndex + subtreeLength) { if (fragment.Index1 > si) { if (fragment.Index1 < si + subtreeLength) { // subtree contains fragment => branching point in the fragment graph var n = traceGraph.GetByContent(node.Data); var n = traceGraph.GetByContent(g.Data); if (n == null) { n = node.Copy(); n = g.Copy(); traceGraph.AddVertex(n); traceMap[n] = new Tuple(subtreeIndex, fragment.Index1); traceMap[n] = new Tuple(si, fragment.Index1); } if (lastVisited != null) { var lastTraceData = traceMap[lastVisited]; int lastSi = lastTraceData.Item1; int lastFi = lastTraceData.Item2; var traceData = new Tuple(lastSi, lastFi, subtreeIndex, fragment.Index1); if (!n.InArcs.Any(a => a.Source == lastVisited && a.Data.Equals(traceData))) { var arc = traceGraph.AddArc(lastVisited, n); arc.Data = traceData; } } lastVisited = n; Trace(parents[0], subtreeIndex); lastVisited = n; Trace(parents[1], fragment.Index2); Trace(parents[0], si, n); Trace(parents[1], fragment.Index2, n); break; } else { // subtree and fragment are distinct. node = parents[0]; g = parents[0]; continue; } #region trace mutation if (parents.Count == 1) { if (subtreeIndex == fragment.Index1) { //            node = parents[0]; var n = traceGraph.GetByContent(node.Data); if (si == fragment.Index1) { // fragment and subtree coincide // since mutation can potentially alter trees quite drastically, we branch here, // in order not to miss any changes var n = traceGraph.GetByContent(g.Data); if (n == null) { n = node.Copy(); n = g.Copy(); traceGraph.AddVertex(n); } if (lastVisited != null) { var arc = traceGraph.AddArc(lastVisited, n); var lastTraceData = traceMap[lastVisited]; int lastSi = lastTraceData.Item1; int lastFi = lastTraceData.Item2; var td = new Tuple(lastSi, lastFi, subtreeIndex, fragment.Index1); } } traceMap[n] = new Tuple(si, fragment.Index1); } Trace(parents[0], si, n); break; } if (fragment.Index1 < si) { if (si < fragment.Index1 + fragmentLength) { // fragment contains subtree g = parents[0]; si = fragment.Index2; } else { // fragment and subtree are distinct // since the fragment occurs before the subtree in the prefix node ordering // the subtree index must be adjusted according to the fragment length g = parents[0]; si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; } continue; } if (si < fragment.Index1) { // subtree occurs before fragment in the prefix node ordering if (fragment.Index1 < si + subtreeLength) { // subtree contains fragment, we are interested to see what the subtree looked like before // but we also want to keep track of what it looks like now, therefore we branch here var n = traceGraph.GetByContent(g.Data); if (n == null) { n = g.Copy(); traceGraph.AddVertex(n); traceMap[n] = new Tuple(si, fragment.Index1); } Trace(parents[0], si, n); break; } else { // fragment and subtree are distinct, subtree index stays the same // since the subtree comes before the fragment in the prefix node ordering g = parents[0]; continue; } } } #endregion } else { throw new InvalidOperationException("A node cannot have more than two parents"); } throw new InvalidOperationException("A node cannot have more than two parents"); } // when we are out of the while the last vertex must be connected with the current one ConnectLast(g, si, last); } /// /// 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 /// of the genealogy graph node @g. /// /// The current node in the genealogy graph /// The index of the traced subtree /// The last added node in the trace graph private void ConnectLast(IGenealogyGraphNode g, int si, IGenealogyGraphNode last) { IFragment fragment = g.Parents.Any() ? (IFragment)g.InArcs.Last().Data : null; var n = traceGraph.GetByContent(g.Data); if (n == null) { n = g.Copy(); traceGraph.AddVertex(n); } int fi = fragment == null ? 0 : fragment.Index1; // fragment index traceMap[n] = new Tuple(si, fi); if (last == null) return; var lastTraceData = traceMap[last]; int lastSi = lastTraceData.Item1; // last subtree index int lastFi = lastTraceData.Item2; // last fragment index var td = new Tuple(si, fi, lastSi, lastFi); // trace data var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td)); if (arc != null) return; arc = new GenealogyGraphArc(last, n); arc.Data = td; traceGraph.AddArc(arc); } } internal static class Util { // shallow copy which does not clone the data and completely ignores arcs // shallow node copy (does not clone the data or the arcs) public static IGenealogyGraphNode Copy(this IGenealogyGraphNode node) { return new GenealogyGraphNode(node.Data) { Rank = node.Rank, Quality = node.Quality };
Note: See TracChangeset for help on using the changeset viewer.