[11493] | 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;
|
---|
[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 {
|
---|
[11866] | 36 | private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData> traceMap;
|
---|
[11855] | 37 | private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
|
---|
[11979] | 38 | private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
|
---|
| 39 | public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
|
---|
[11458] | 40 |
|
---|
| 41 | public TraceCalculator() {
|
---|
[11979] | 42 | TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
|
---|
[11866] | 43 | traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
|
---|
[11855] | 44 | nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
|
---|
[11979] | 45 | traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
|
---|
[11458] | 46 | }
|
---|
| 47 |
|
---|
| 48 | protected TraceCalculator(TraceCalculator original, Cloner cloner)
|
---|
| 49 | : base(original, cloner) {
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 53 | return new TraceCalculator(this, cloner);
|
---|
| 54 | }
|
---|
| 55 |
|
---|
[11979] | 56 | public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(
|
---|
| 57 | IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
|
---|
[11458] | 58 | var tc = new TraceCalculator();
|
---|
| 59 | tc.Trace(node, subtreeIndex);
|
---|
| 60 | return tc.TraceGraph;
|
---|
| 61 | }
|
---|
| 62 |
|
---|
[11476] | 63 | public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
|
---|
[11979] | 64 | TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
|
---|
[11866] | 65 | traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
|
---|
[11855] | 66 | nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
|
---|
[11979] | 67 | traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
|
---|
[11751] | 68 | TraceRecursive(node, subtreeIndex);
|
---|
[11979] | 69 | return TraceGraph;
|
---|
[11476] | 70 | }
|
---|
| 71 |
|
---|
[11473] | 72 | /// <summary>
|
---|
| 73 | /// This method starts from a given vertex in the genealogy graph and works its way
|
---|
| 74 | /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
|
---|
| 75 | /// This method will skip genealogy graph nodes that did not have an influence on the
|
---|
| 76 | /// structure of the tracked subtree.
|
---|
| 77 | ///
|
---|
| 78 | /// Only genealogy nodes which did have an influence are added (as copies) to the trace
|
---|
| 79 | /// and are consequently called 'trace nodes'.
|
---|
| 80 | ///
|
---|
| 81 | /// The arcs connecting trace nodes hold information about the locations of the subtrees
|
---|
| 82 | /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
|
---|
| 83 | /// where:
|
---|
| 84 | /// - si is the subtree index in the current trace node
|
---|
| 85 | /// - fi is the fragment index in the current trace node
|
---|
| 86 | /// - lastSi is the subtree index in the previous trace node
|
---|
| 87 | /// - lastFi is the subtree index in the previous trace node
|
---|
| 88 | /// </summary>
|
---|
[11751] | 89 | /// <param name="node">The current node in the genealogy graph</param>
|
---|
| 90 | /// <param name="subtreeIndex">The index of the traced subtree</param>
|
---|
[11473] | 91 | /// <param name="last">The last added node in the trace graph</param>
|
---|
[11979] | 92 | private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex,
|
---|
| 93 | IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
|
---|
[11751] | 94 | var g = node;
|
---|
[11881] | 95 | int si = subtreeIndex; // subtree index
|
---|
| 96 | int fi = 0; // fragment index
|
---|
[11968] | 97 | while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
|
---|
| 98 | // while (g.Parents.Any()) {
|
---|
[11751] | 99 | Debug.Assert(si < g.Data.Length);
|
---|
[11858] | 100 | var inArcs = (List<IArc>)((IVertex)g).InArcs;
|
---|
[11925] | 101 | var fragment = (IFragment<ISymbolicExpressionTreeNode>)((IGenealogyGraphArc)inArcs.Last()).Data;
|
---|
[11458] | 102 | if (fragment == null) {
|
---|
[11855] | 103 | // TODO: think about what the correct behavior should be here (seems good so far)
|
---|
[11458] | 104 | // the node is either an elite node or (in rare cases) no fragment was transferred
|
---|
[11858] | 105 | g = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
[11458] | 106 | continue;
|
---|
| 107 | }
|
---|
| 108 |
|
---|
[11979] | 109 | fi = fragment.Index1; // fragment index
|
---|
| 110 | int fl = fragment.Root.GetLength(); // fragment length
|
---|
[11855] | 111 | int sl = NodeAt(g.Data, si).GetLength(); // subtree length
|
---|
[11458] | 112 |
|
---|
| 113 | #region trace crossover
|
---|
[11979] | 114 |
|
---|
[11858] | 115 | if (inArcs.Count == 2) {
|
---|
| 116 | var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
| 117 | var parent1 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[1].Source;
|
---|
[11493] | 118 | if (fi == si) {
|
---|
[11858] | 119 | g = parent1;
|
---|
[11473] | 120 | si = fragment.Index2;
|
---|
[11458] | 121 | continue;
|
---|
| 122 | }
|
---|
[11493] | 123 | if (fi < si) {
|
---|
| 124 | if (fi + fl > si) {
|
---|
[11458] | 125 | // fragment contains subtree
|
---|
[11858] | 126 | g = parent1;
|
---|
[11493] | 127 | si += fragment.Index2 - fi;
|
---|
[11458] | 128 | } else {
|
---|
| 129 | // fragment distinct from subtree
|
---|
[11858] | 130 | g = parent0;
|
---|
[11855] | 131 | si += NodeAt(g.Data, fi).GetLength() - fl;
|
---|
[11458] | 132 | }
|
---|
| 133 | continue;
|
---|
| 134 | }
|
---|
[11493] | 135 | if (fi > si) {
|
---|
| 136 | if (fi < si + sl) {
|
---|
[11458] | 137 | // subtree contains fragment => branching point in the fragment graph
|
---|
[11881] | 138 | var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
|
---|
[11979] | 139 | var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
|
---|
| 140 | if (!traceCache.Contains(t0)) {
|
---|
| 141 | TraceRecursive(parent0, si, n);
|
---|
| 142 | traceCache.Add(t0);
|
---|
| 143 | } else {
|
---|
| 144 | n.Weight++;
|
---|
| 145 | }
|
---|
| 146 | var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
|
---|
| 147 | if (!traceCache.Contains(t1)) {
|
---|
| 148 | TraceRecursive(parent1, fragment.Index2, n);
|
---|
| 149 | traceCache.Add(t1);
|
---|
| 150 | } else {
|
---|
| 151 | n.Weight++;
|
---|
| 152 | }
|
---|
[11458] | 153 | break;
|
---|
| 154 | } else {
|
---|
| 155 | // subtree and fragment are distinct.
|
---|
[11858] | 156 | g = parent0;
|
---|
[11458] | 157 | continue;
|
---|
| 158 | }
|
---|
| 159 | }
|
---|
| 160 | }
|
---|
| 161 | #endregion
|
---|
| 162 | #region trace mutation
|
---|
[11493] | 163 | // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
|
---|
| 164 | // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
|
---|
[11858] | 165 | if (inArcs.Count == 1) {
|
---|
| 166 | var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
|
---|
[11493] | 167 | Debug.Assert(fragment.Index1 == fragment.Index2);
|
---|
| 168 | // check if the subtree and the fragment overlap => branch out
|
---|
| 169 | if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
|
---|
[11881] | 170 | var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
|
---|
[11493] | 171 | int i = si < fi ? si : fi;
|
---|
[11979] | 172 | var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
|
---|
| 173 | if (!traceCache.Contains(t)) {
|
---|
| 174 | TraceRecursive(parent0, i, n);
|
---|
| 175 | traceCache.Add(t);
|
---|
| 176 | } else {
|
---|
| 177 | n.Weight++;
|
---|
| 178 | }
|
---|
[11473] | 179 | break;
|
---|
[11493] | 180 | } else {
|
---|
| 181 | // if they don't overlap, go up
|
---|
[11858] | 182 | g = parent0;
|
---|
[11493] | 183 | if (fi < si)
|
---|
[11855] | 184 | si += NodeAt(g.Data, fi).GetLength() - fl;
|
---|
[11473] | 185 | continue;
|
---|
[11458] | 186 | }
|
---|
[11473] | 187 | }
|
---|
[11458] | 188 | #endregion
|
---|
[11473] | 189 | throw new InvalidOperationException("A node cannot have more than two parents");
|
---|
[11458] | 190 | }
|
---|
[11473] | 191 | // when we are out of the while the last vertex must be connected with the current one
|
---|
[11881] | 192 | // if there is no last vertex, it means the tracing reached the top of the genealogy graph
|
---|
| 193 | var current = AddTraceNode(g, si, fi);
|
---|
| 194 | if (last != null)
|
---|
| 195 | ConnectLast(current, last, si, fi);
|
---|
[11458] | 196 | }
|
---|
[11473] | 197 |
|
---|
| 198 | /// <summary>
|
---|
[11493] | 199 | /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
|
---|
| 200 | /// 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.
|
---|
| 201 | /// </summary>
|
---|
| 202 | /// <param name="g">The genealogy graph node</param>
|
---|
| 203 | /// <param name="si">The subtree index</param>
|
---|
| 204 | /// <param name="fi">The fragment index</param>
|
---|
| 205 | /// <returns></returns>
|
---|
[11979] | 206 | private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g,
|
---|
| 207 | int si, int fi) {
|
---|
| 208 | var n = TraceGraph.GetByContent(g.Data);
|
---|
[11493] | 209 | if (n == null) {
|
---|
| 210 | n = g.Copy();
|
---|
[11979] | 211 | TraceGraph.AddVertex(n);
|
---|
[11493] | 212 | Debug.Assert(!traceMap.ContainsKey(n));
|
---|
[11866] | 213 | traceMap[n] = new TraceData(si, fi, -1, -1); // only the first two fields are needed
|
---|
[11493] | 214 | }
|
---|
| 215 | return n;
|
---|
| 216 | }
|
---|
| 217 |
|
---|
[11855] | 218 | // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
|
---|
| 219 | // this caching will be even more effective with larger tree sizes
|
---|
| 220 | private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
|
---|
| 221 | List<ISymbolicExpressionTreeNode> list;
|
---|
| 222 | nodeListCache.TryGetValue(tree, out list);
|
---|
| 223 | if (list == null) {
|
---|
| 224 | list = tree.IterateNodesPrefix().ToList();
|
---|
| 225 | nodeListCache[tree] = list;
|
---|
| 226 | }
|
---|
| 227 | return list[index];
|
---|
| 228 | }
|
---|
| 229 |
|
---|
[11493] | 230 | /// <summary>
|
---|
[11473] | 231 | /// 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
|
---|
| 232 | /// of the genealogy graph node @g.
|
---|
| 233 | /// </summary>
|
---|
[11881] | 234 | /// <param name="current">The current node in the genealogy graph</param>
|
---|
| 235 | /// <param name="last">The last added node in the trace graph</param>
|
---|
[11473] | 236 | /// <param name="si">The index of the traced subtree</param>
|
---|
[11881] | 237 | /// <param name="fi">The index of the fragment</param>
|
---|
[11979] | 238 | private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current,
|
---|
| 239 | IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
|
---|
[11473] | 240 | var lastTraceData = traceMap[last];
|
---|
[11979] | 241 | int lastSi = lastTraceData.SubtreeIndex;
|
---|
| 242 | // last subtree index (index of the traced subtree in the previous trace node)
|
---|
| 243 | int lastFi = lastTraceData.FragmentIndex;
|
---|
| 244 | // last fragment index (index of the fragment in the previous trace node)
|
---|
[11866] | 245 | var td = new TraceData(si, fi, lastSi, lastFi); // trace data
|
---|
[11979] | 246 | // using the inArcs seems to be slightly more efficient than using the outArcs
|
---|
| 247 | // TODO: more testing
|
---|
| 248 | var inArcs = (List<IArc>)((IVertex)last).InArcs;
|
---|
| 249 | var arc = inArcs.FirstOrDefault(a => a.Source == current && ((IArc<IDeepCloneable>)a).Data.Equals(td));
|
---|
[11503] | 250 | if (arc == null) {
|
---|
[11881] | 251 | arc = new GenealogyGraphArc(current, last) { Data = td };
|
---|
[11979] | 252 | TraceGraph.AddArc(arc);
|
---|
[11503] | 253 | }
|
---|
[11473] | 254 | }
|
---|
[11458] | 255 | }
|
---|
[11979] | 256 |
|
---|
[11925] | 257 | public class TraceData : Tuple<int, int, int, int>, IDeepCloneable {
|
---|
[11866] | 258 | public TraceData(int currentSubtreeIndex, int currentFragmentIndex, int lastSubtreeIndex, int lastFragmentIndex)
|
---|
| 259 | : base(currentSubtreeIndex, currentFragmentIndex, lastSubtreeIndex, lastFragmentIndex) {
|
---|
| 260 | }
|
---|
[11458] | 261 |
|
---|
[11866] | 262 | public int SubtreeIndex { get { return Item1; } }
|
---|
| 263 | public int FragmentIndex { get { return Item2; } }
|
---|
| 264 | public int LastSubtreeIndex { get { return Item3; } }
|
---|
| 265 | public int LastFragmentIndex { get { return Item4; } }
|
---|
[11925] | 266 | public object Clone() {
|
---|
| 267 | return new TraceData(SubtreeIndex, FragmentIndex, LastSubtreeIndex, LastFragmentIndex);
|
---|
| 268 | }
|
---|
| 269 |
|
---|
| 270 | public IDeepCloneable Clone(Cloner cloner) {
|
---|
| 271 | return cloner.Clone(this);
|
---|
| 272 | }
|
---|
[11866] | 273 | }
|
---|
| 274 |
|
---|
[11458] | 275 | internal static class Util {
|
---|
[11473] | 276 | // shallow node copy (does not clone the data or the arcs)
|
---|
[11751] | 277 | #region some helper methods for shortening the tracing code
|
---|
[11458] | 278 | public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
|
---|
| 279 | return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
|
---|
| 280 | }
|
---|
| 281 | #endregion
|
---|
| 282 | }
|
---|
| 283 | }
|
---|