[11493] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[12287] | 3 | * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[11493] | 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;
|
---|
[11458] | 23 | using System.Collections.Generic;
|
---|
[11493] | 24 | using System.Diagnostics;
|
---|
[11458] | 25 | using System.Linq;
|
---|
| 26 | using HeuristicLab.Common;
|
---|
| 27 | using HeuristicLab.Core;
|
---|
| 28 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
| 29 | using HeuristicLab.EvolutionTracking;
|
---|
| 30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 31 |
|
---|
| 32 | namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
|
---|
| 33 | [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
|
---|
| 34 | [StorableClass]
|
---|
| 35 | public class TraceCalculator : Item {
|
---|
[11855] | 36 | private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
|
---|
[13479] | 37 | private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>> traceCache;
|
---|
[11979] | 38 | public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
|
---|
[11458] | 39 |
|
---|
[12225] | 40 | public bool UpdateVertexWeights { get; set; }
|
---|
| 41 | public bool UpdateSubtreeWeights { get; set; }
|
---|
| 42 | public bool CacheTraceNodes { get; set; }
|
---|
| 43 |
|
---|
[13479] | 44 | public int TraceCacheHits { get; set; }
|
---|
| 45 |
|
---|
[11458] | 46 | public TraceCalculator() {
|
---|
[12225] | 47 | ResetState();
|
---|
[11458] | 48 | }
|
---|
| 49 |
|
---|
[12966] | 50 | [StorableConstructor]
|
---|
| 51 | protected TraceCalculator(bool deserializing) : base(deserializing) { }
|
---|
| 52 |
|
---|
[11458] | 53 | protected TraceCalculator(TraceCalculator original, Cloner cloner)
|
---|
| 54 | : base(original, cloner) {
|
---|
| 55 | }
|
---|
| 56 |
|
---|
| 57 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 58 | return new TraceCalculator(this, cloner);
|
---|
| 59 | }
|
---|
| 60 |
|
---|
[12225] | 61 | public void ResetState() {
|
---|
| 62 | TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
|
---|
| 63 | nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
|
---|
[13479] | 64 | traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>>();
|
---|
[12225] | 65 | }
|
---|
| 66 |
|
---|
| 67 | public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool updateVertexWeights = false, bool updateSubtreeWeights = false, bool cacheTraceNodes = true) {
|
---|
| 68 | var tc = new TraceCalculator {
|
---|
| 69 | UpdateVertexWeights = updateSubtreeWeights,
|
---|
| 70 | UpdateSubtreeWeights = updateSubtreeWeights,
|
---|
| 71 | CacheTraceNodes = cacheTraceNodes
|
---|
| 72 | };
|
---|
[11458] | 73 | tc.Trace(node, subtreeIndex);
|
---|
| 74 | return tc.TraceGraph;
|
---|
| 75 | }
|
---|
| 76 |
|
---|
[12225] | 77 | public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool resetState = true) {
|
---|
| 78 | if (resetState) ResetState();
|
---|
[11751] | 79 | TraceRecursive(node, subtreeIndex);
|
---|
[11979] | 80 | return TraceGraph;
|
---|
[11476] | 81 | }
|
---|
| 82 |
|
---|
[11473] | 83 | /// <summary>
|
---|
| 84 | /// This method starts from a given vertex in the genealogy graph and works its way
|
---|
| 85 | /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
|
---|
| 86 | /// This method will skip genealogy graph nodes that did not have an influence on the
|
---|
| 87 | /// structure of the tracked subtree.
|
---|
| 88 | ///
|
---|
| 89 | /// Only genealogy nodes which did have an influence are added (as copies) to the trace
|
---|
| 90 | /// and are consequently called 'trace nodes'.
|
---|
| 91 | ///
|
---|
| 92 | /// The arcs connecting trace nodes hold information about the locations of the subtrees
|
---|
| 93 | /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
|
---|
| 94 | /// where:
|
---|
| 95 | /// - si is the subtree index in the current trace node
|
---|
| 96 | /// - fi is the fragment index in the current trace node
|
---|
| 97 | /// - lastSi is the subtree index in the previous trace node
|
---|
| 98 | /// - lastFi is the subtree index in the previous trace node
|
---|
| 99 | /// </summary>
|
---|
[11751] | 100 | /// <param name="node">The current node in the genealogy graph</param>
|
---|
| 101 | /// <param name="subtreeIndex">The index of the traced subtree</param>
|
---|
[11473] | 102 | /// <param name="last">The last added node in the trace graph</param>
|
---|
[13424] | 103 | /// <param name="lastSi">The subtree index in the last added individual</param>
|
---|
| 104 | /// <param name="lastFi">The fragment index in the last added individual</param>
|
---|
| 105 | private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null, int lastSi = -1, int lastFi = -1) {
|
---|
[11751] | 106 | var g = node;
|
---|
[11881] | 107 | int si = subtreeIndex; // subtree index
|
---|
| 108 | int fi = 0; // fragment index
|
---|
[11968] | 109 | while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
|
---|
[13424] | 110 | if (!(si < g.Data.Length)) throw new ArgumentOutOfRangeException("The subtree index exceeds the size of the tree.");
|
---|
[11858] | 111 | var inArcs = (List<IArc>)((IVertex)g).InArcs;
|
---|
[11925] | 112 | var fragment = (IFragment<ISymbolicExpressionTreeNode>)((IGenealogyGraphArc)inArcs.Last()).Data;
|
---|
[11458] | 113 | if (fragment == null) {
|
---|
[11855] | 114 | // TODO: think about what the correct behavior should be here (seems good so far)
|
---|
[11458] | 115 | // the node is either an elite node or (in rare cases) no fragment was transferred
|
---|
[11858] | 116 | g = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
[11458] | 117 | continue;
|
---|
| 118 | }
|
---|
| 119 |
|
---|
[11979] | 120 | fi = fragment.Index1; // fragment index
|
---|
| 121 | int fl = fragment.Root.GetLength(); // fragment length
|
---|
[11855] | 122 | int sl = NodeAt(g.Data, si).GetLength(); // subtree length
|
---|
[11458] | 123 |
|
---|
| 124 | #region trace crossover
|
---|
[11858] | 125 | if (inArcs.Count == 2) {
|
---|
| 126 | var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
| 127 | var parent1 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[1].Source;
|
---|
[11493] | 128 | if (fi == si) {
|
---|
[11858] | 129 | g = parent1;
|
---|
[11473] | 130 | si = fragment.Index2;
|
---|
[11458] | 131 | continue;
|
---|
| 132 | }
|
---|
[11493] | 133 | if (fi < si) {
|
---|
| 134 | if (fi + fl > si) {
|
---|
[11458] | 135 | // fragment contains subtree
|
---|
[11858] | 136 | g = parent1;
|
---|
[11493] | 137 | si += fragment.Index2 - fi;
|
---|
[11458] | 138 | } else {
|
---|
| 139 | // fragment distinct from subtree
|
---|
[11858] | 140 | g = parent0;
|
---|
[11855] | 141 | si += NodeAt(g.Data, fi).GetLength() - fl;
|
---|
[11458] | 142 | }
|
---|
| 143 | continue;
|
---|
| 144 | }
|
---|
[11493] | 145 | if (fi > si) {
|
---|
| 146 | if (fi < si + sl) {
|
---|
[11458] | 147 | // subtree contains fragment => branching point in the fragment graph
|
---|
[13424] | 148 | var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
|
---|
[13479] | 149 | if (CacheTraceNodes) {
|
---|
| 150 | var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, si, n, si, fi);
|
---|
| 151 | var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent1, fragment.Index2, n, si, fi);
|
---|
| 152 | if (!traceCache.Contains(t0)) {
|
---|
| 153 | traceCache.Add(t0);
|
---|
| 154 | TraceRecursive(parent0, si, n, si, fi);
|
---|
| 155 | } else {
|
---|
| 156 | TraceCacheHits++;
|
---|
| 157 | }
|
---|
| 158 | if (!traceCache.Contains(t1)) {
|
---|
| 159 | traceCache.Add(t1);
|
---|
| 160 | TraceRecursive(parent1, fragment.Index2, n, si, fi);
|
---|
| 161 | } else {
|
---|
| 162 | TraceCacheHits++;
|
---|
| 163 | }
|
---|
| 164 | } else {
|
---|
[13424] | 165 | TraceRecursive(parent0, si, n, si, fi);
|
---|
| 166 | TraceRecursive(parent1, fragment.Index2, n, si, fi);
|
---|
[12225] | 167 | }
|
---|
[11458] | 168 | break;
|
---|
| 169 | } else {
|
---|
| 170 | // subtree and fragment are distinct.
|
---|
[11858] | 171 | g = parent0;
|
---|
[11458] | 172 | continue;
|
---|
| 173 | }
|
---|
| 174 | }
|
---|
| 175 | }
|
---|
| 176 | #endregion
|
---|
| 177 | #region trace mutation
|
---|
[11493] | 178 | // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
|
---|
| 179 | // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
|
---|
[11858] | 180 | if (inArcs.Count == 1) {
|
---|
| 181 | var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
[11493] | 182 | Debug.Assert(fragment.Index1 == fragment.Index2);
|
---|
| 183 | // check if the subtree and the fragment overlap => branch out
|
---|
| 184 | if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
|
---|
[13424] | 185 | var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
|
---|
[11493] | 186 | int i = si < fi ? si : fi;
|
---|
[13479] | 187 | var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, i, n, si, fi);
|
---|
[12225] | 188 | if (!(CacheTraceNodes && traceCache.Contains(t))) {
|
---|
[13424] | 189 | TraceRecursive(parent0, i, n, si, fi);
|
---|
[11979] | 190 | traceCache.Add(t);
|
---|
[12225] | 191 | }
|
---|
[11473] | 192 | break;
|
---|
[11493] | 193 | } else {
|
---|
| 194 | // if they don't overlap, go up
|
---|
[11858] | 195 | g = parent0;
|
---|
[11493] | 196 | if (fi < si)
|
---|
[11855] | 197 | si += NodeAt(g.Data, fi).GetLength() - fl;
|
---|
[11473] | 198 | continue;
|
---|
[11458] | 199 | }
|
---|
[11473] | 200 | }
|
---|
[11458] | 201 | #endregion
|
---|
[11473] | 202 | throw new InvalidOperationException("A node cannot have more than two parents");
|
---|
[11458] | 203 | }
|
---|
[11473] | 204 | // when we are out of the while the last vertex must be connected with the current one
|
---|
[11881] | 205 | // if there is no last vertex, it means the tracing reached the top of the genealogy graph
|
---|
[13424] | 206 | if (last != null) {
|
---|
| 207 | var current = AddTraceNode(g);
|
---|
| 208 | if (current.Rank.IsAlmost(0)) fi = -1; // if current is part of the initial population there will be no fragment
|
---|
| 209 | var td = new TraceData(si, fi, lastSi, lastFi);
|
---|
| 210 | #if DEBUG
|
---|
| 211 | var currentLength = current.Data.Length;
|
---|
| 212 | var lastLength = last.Data.Length;
|
---|
| 213 |
|
---|
| 214 | if (!(si < currentLength))
|
---|
| 215 | throw new ArgumentOutOfRangeException(string.Format("Subtree index {0} exceeds tree length ({1}", si, currentLength));
|
---|
| 216 |
|
---|
| 217 | if (!(fi < currentLength))
|
---|
| 218 | throw new ArgumentOutOfRangeException(string.Format("Fragment index {0} exceeds tree length ({1}", fi, currentLength));
|
---|
| 219 |
|
---|
| 220 | if (!(lastSi < lastLength))
|
---|
| 221 | throw new ArgumentOutOfRangeException(string.Format("Last subtree index {0} exceeds tree length ({1}", lastSi, lastLength));
|
---|
| 222 |
|
---|
| 223 | if (!(lastFi < lastLength))
|
---|
| 224 | throw new ArgumentOutOfRangeException(string.Format("Last fragment index {0} exceeds tree length ({1}", lastFi, lastLength));
|
---|
| 225 | #endif
|
---|
| 226 | ConnectLast(current, last, td);
|
---|
| 227 | }
|
---|
[11458] | 228 | }
|
---|
[11473] | 229 |
|
---|
| 230 | /// <summary>
|
---|
[11493] | 231 | /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
|
---|
| 232 | /// If the trace graph does not contain such a node, one is created by performing a shallow copy of g, then inserted into the trace graph.
|
---|
| 233 | /// </summary>
|
---|
| 234 | /// <param name="g">The genealogy graph node</param>
|
---|
| 235 | /// <param name="si">The subtree index</param>
|
---|
| 236 | /// <param name="fi">The fragment index</param>
|
---|
| 237 | /// <returns></returns>
|
---|
[13424] | 238 | private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g) {
|
---|
[11979] | 239 | var n = TraceGraph.GetByContent(g.Data);
|
---|
[11493] | 240 | if (n == null) {
|
---|
| 241 | n = g.Copy();
|
---|
[11979] | 242 | TraceGraph.AddVertex(n);
|
---|
[11493] | 243 | }
|
---|
| 244 | return n;
|
---|
| 245 | }
|
---|
| 246 |
|
---|
[11855] | 247 | // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
|
---|
| 248 | // this caching will be even more effective with larger tree sizes
|
---|
| 249 | private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
|
---|
| 250 | List<ISymbolicExpressionTreeNode> list;
|
---|
| 251 | nodeListCache.TryGetValue(tree, out list);
|
---|
| 252 | if (list == null) {
|
---|
| 253 | list = tree.IterateNodesPrefix().ToList();
|
---|
| 254 | nodeListCache[tree] = list;
|
---|
| 255 | }
|
---|
| 256 | return list[index];
|
---|
| 257 | }
|
---|
| 258 |
|
---|
[11493] | 259 | /// <summary>
|
---|
[11473] | 260 | /// 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
|
---|
| 261 | /// of the genealogy graph node @g.
|
---|
| 262 | /// </summary>
|
---|
[11881] | 263 | /// <param name="current">The current node in the genealogy graph</param>
|
---|
[13424] | 264 | /// <param name="last">The last added node in the trace graph</param>
|
---|
| 265 | /// <param name="td">The trace data specifying the preorder indices of the subtree and fragment in the @current and @last vertices</param>
|
---|
| 266 | private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, TraceData td) {
|
---|
[11979] | 267 | // TODO: more testing
|
---|
[12265] | 268 | var inArcs = (List<IArc>)((IVertex)last).InArcs; // using the InArcs seems to be slightly more efficient than using the OutArcs
|
---|
[11979] | 269 | var arc = inArcs.FirstOrDefault(a => a.Source == current && ((IArc<IDeepCloneable>)a).Data.Equals(td));
|
---|
[11503] | 270 | if (arc == null) {
|
---|
[11881] | 271 | arc = new GenealogyGraphArc(current, last) { Data = td };
|
---|
[11979] | 272 | TraceGraph.AddArc(arc);
|
---|
[11503] | 273 | }
|
---|
[12283] | 274 | if (UpdateVertexWeights) {
|
---|
| 275 | arc.Weight++;
|
---|
| 276 | current.Weight++;
|
---|
| 277 | }
|
---|
| 278 | if (UpdateSubtreeWeights) {
|
---|
| 279 | var subtree = NodeAt(current.Data, td.SubtreeIndex);
|
---|
| 280 | foreach (var s in subtree.IterateNodesPrefix())
|
---|
| 281 | s.NodeWeight++;
|
---|
| 282 | }
|
---|
[11473] | 283 | }
|
---|
[11458] | 284 | }
|
---|
[11979] | 285 |
|
---|
[11925] | 286 | public class TraceData : Tuple<int, int, int, int>, IDeepCloneable {
|
---|
[11866] | 287 | public TraceData(int currentSubtreeIndex, int currentFragmentIndex, int lastSubtreeIndex, int lastFragmentIndex)
|
---|
| 288 | : base(currentSubtreeIndex, currentFragmentIndex, lastSubtreeIndex, lastFragmentIndex) {
|
---|
| 289 | }
|
---|
[11458] | 290 |
|
---|
[11866] | 291 | public int SubtreeIndex { get { return Item1; } }
|
---|
| 292 | public int FragmentIndex { get { return Item2; } }
|
---|
| 293 | public int LastSubtreeIndex { get { return Item3; } }
|
---|
| 294 | public int LastFragmentIndex { get { return Item4; } }
|
---|
[11925] | 295 | public object Clone() {
|
---|
| 296 | return new TraceData(SubtreeIndex, FragmentIndex, LastSubtreeIndex, LastFragmentIndex);
|
---|
| 297 | }
|
---|
| 298 |
|
---|
[12966] | 299 | protected TraceData(TraceData original, Cloner cloner) :
|
---|
| 300 | base(original.SubtreeIndex, original.FragmentIndex, original.LastFragmentIndex, original.LastFragmentIndex) {
|
---|
| 301 | }
|
---|
| 302 |
|
---|
[11925] | 303 | public IDeepCloneable Clone(Cloner cloner) {
|
---|
| 304 | return cloner.Clone(this);
|
---|
| 305 | }
|
---|
[11866] | 306 | }
|
---|
| 307 |
|
---|
[11458] | 308 | internal static class Util {
|
---|
[11473] | 309 | // shallow node copy (does not clone the data or the arcs)
|
---|
[11751] | 310 | #region some helper methods for shortening the tracing code
|
---|
[11458] | 311 | public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
|
---|
| 312 | return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
|
---|
| 313 | }
|
---|
| 314 | #endregion
|
---|
| 315 | }
|
---|
| 316 | }
|
---|