1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Linq;
|
---|
4 | using HeuristicLab.Common;
|
---|
5 | using HeuristicLab.Core;
|
---|
6 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
7 | using HeuristicLab.EvolutionTracking;
|
---|
8 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
9 |
|
---|
10 | namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
|
---|
11 |
|
---|
12 |
|
---|
13 | [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
|
---|
14 | [StorableClass]
|
---|
15 | public class TraceCalculator : Item {
|
---|
16 | private IGenealogyGraphNode<ISymbolicExpressionTree> lastVisited;
|
---|
17 | private readonly IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
|
---|
18 | private readonly Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
|
---|
19 |
|
---|
20 | public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
|
---|
21 |
|
---|
22 | public TraceCalculator() {
|
---|
23 | traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
|
---|
24 | traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
|
---|
25 | }
|
---|
26 |
|
---|
27 | protected TraceCalculator(TraceCalculator original, Cloner cloner)
|
---|
28 | : base(original, cloner) {
|
---|
29 | }
|
---|
30 |
|
---|
31 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
32 | return new TraceCalculator(this, cloner);
|
---|
33 | }
|
---|
34 |
|
---|
35 | public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
|
---|
36 | var tc = new TraceCalculator();
|
---|
37 | tc.Trace(node, subtreeIndex);
|
---|
38 | return tc.TraceGraph;
|
---|
39 | }
|
---|
40 |
|
---|
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;
|
---|
60 | if (fragment == null) {
|
---|
61 | // the node is either an elite node or (in rare cases) no fragment was transferred
|
---|
62 | node = parents[0];
|
---|
63 | continue;
|
---|
64 | }
|
---|
65 |
|
---|
66 | int fragmentLength = fragment.Root.GetLength();
|
---|
67 | int subtreeLength = node.Data.NodeAt(subtreeIndex).GetLength();
|
---|
68 |
|
---|
69 | #region trace crossover
|
---|
70 | if (parents.Count == 2) {
|
---|
71 | if (fragment.Index1 == subtreeIndex) {
|
---|
72 | node = parents[1];
|
---|
73 | subtreeIndex = fragment.Index2;
|
---|
74 | continue;
|
---|
75 | }
|
---|
76 | if (fragment.Index1 < subtreeIndex) {
|
---|
77 | if (fragment.Index1 + fragmentLength > subtreeIndex) {
|
---|
78 | // fragment contains subtree
|
---|
79 | node = parents[1];
|
---|
80 | subtreeIndex += fragment.Index2 - fragment.Index1;
|
---|
81 | } else {
|
---|
82 | // fragment distinct from subtree
|
---|
83 | node = parents[0];
|
---|
84 | subtreeIndex += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
|
---|
85 | }
|
---|
86 | continue;
|
---|
87 | }
|
---|
88 | if (fragment.Index1 > subtreeIndex) {
|
---|
89 | if (fragment.Index1 < subtreeIndex + subtreeLength) {
|
---|
90 | // subtree contains fragment => branching point in the fragment graph
|
---|
91 | var n = traceGraph.GetByContent(node.Data);
|
---|
92 | if (n == null) {
|
---|
93 | n = node.Copy();
|
---|
94 | traceGraph.AddVertex(n);
|
---|
95 | traceMap[n] = new Tuple<int, int>(subtreeIndex, fragment.Index1);
|
---|
96 | }
|
---|
97 |
|
---|
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);
|
---|
113 | break;
|
---|
114 | } else {
|
---|
115 | // subtree and fragment are distinct.
|
---|
116 | node = parents[0];
|
---|
117 | continue;
|
---|
118 | }
|
---|
119 | }
|
---|
120 | }
|
---|
121 | #endregion
|
---|
122 | #region trace mutation
|
---|
123 | if (parents.Count == 1) {
|
---|
124 | if (subtreeIndex == fragment.Index1) {
|
---|
125 | // node = parents[0];
|
---|
126 | var n = traceGraph.GetByContent(node.Data);
|
---|
127 | if (n == null) {
|
---|
128 | n = node.Copy();
|
---|
129 | 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 | }
|
---|
140 | #endregion
|
---|
141 | } else {
|
---|
142 | throw new InvalidOperationException("A node cannot have more than two parents");
|
---|
143 | }
|
---|
144 | }
|
---|
145 | }
|
---|
146 | }
|
---|
147 |
|
---|
148 | internal static class Util {
|
---|
149 | // shallow copy which does not clone the data and completely ignores arcs
|
---|
150 | public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
|
---|
151 | return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
|
---|
152 | }
|
---|
153 | #region some helper methods for shortening the tracing code
|
---|
154 | public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
|
---|
155 | return NodeAt(tree.Root, index);
|
---|
156 | }
|
---|
157 | public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
|
---|
158 | return root.IterateNodesPrefix().ElementAt(index);
|
---|
159 | }
|
---|
160 | #endregion
|
---|
161 | }
|
---|
162 | }
|
---|