Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs @ 12231

Last change on this file since 12231 was 12231, checked in by bburlacu, 8 years ago

#1772: Changed the way node highlighting is performed (taking into account sampling count relative to current generation). Made NodeWeight field storable in the SymbolicExpressionTreeNode. Updated the statistics counting in the TraceCalculator.

File size: 7.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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
22using System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27
28namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
29  [StorableClass]
30  public class SymbolicExpressionTreeNode : DeepCloneable, ISymbolicExpressionTreeNode {
31    [Storable]
32    private IList<ISymbolicExpressionTreeNode> subtrees;
33    [Storable]
34    private ISymbol symbol;
35
36    // cached values to prevent unnecessary tree iterations
37    private ushort length;
38    private ushort depth;
39
40    public ISymbol Symbol {
41      get { return symbol; }
42      protected set { symbol = value; }
43    }
44
45    // parent relation is not persisted or cloned (will be set on AddSubtree or RemoveSubtree)
46    private ISymbolicExpressionTreeNode parent;
47    public ISymbolicExpressionTreeNode Parent {
48      get { return parent; }
49      set { parent = value; }
50    }
51
52    [Storable]
53    public double NodeWeight { get; set; }
54
55    [StorableConstructor]
56    protected SymbolicExpressionTreeNode(bool deserializing) { }
57    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original, Cloner cloner)
58      : base(original, cloner) {
59      symbol = original.symbol; // symbols are reused
60      length = original.length;
61      depth = original.depth;
62      NodeWeight = original.NodeWeight;
63      if (original.subtrees != null) {
64        subtrees = new List<ISymbolicExpressionTreeNode>(original.subtrees.Count);
65        foreach (var subtree in original.subtrees) {
66          var clonedSubtree = cloner.Clone(subtree);
67          subtrees.Add(clonedSubtree);
68          clonedSubtree.Parent = this;
69        }
70      }
71    }
72    public override IDeepCloneable Clone(Cloner cloner) {
73      return new SymbolicExpressionTreeNode(this, cloner);
74    }
75
76    internal SymbolicExpressionTreeNode()
77      : base() {
78      // don't allocate subtrees list here!
79      // because we don't want to allocate it in terminal nodes
80    }
81
82    public SymbolicExpressionTreeNode(ISymbol symbol)
83      : base() {
84      subtrees = new List<ISymbolicExpressionTreeNode>(3);
85      this.symbol = symbol;
86    }
87
88
89    [StorableHook(HookType.AfterDeserialization)]
90    private void AfterDeserialization() {
91      if (subtrees != null) {
92        foreach (var subtree in subtrees)
93          subtree.Parent = this;
94      }
95    }
96
97    public virtual bool HasLocalParameters {
98      get { return false; }
99    }
100
101    public virtual IEnumerable<ISymbolicExpressionTreeNode> Subtrees {
102      get { return subtrees; }
103    }
104
105    public virtual ISymbolicExpressionTreeGrammar Grammar {
106      get { return parent.Grammar; }
107    }
108
109    public int GetLength() {
110      if (length > 0) return length;
111      else {
112        length = 1;
113        if (subtrees != null) {
114          for (int i = 0; i < subtrees.Count; i++) {
115            checked { length += (ushort)subtrees[i].GetLength(); }
116          }
117        }
118        return length;
119      }
120    }
121
122    public int GetDepth() {
123      if (depth > 0) return depth;
124      else {
125        if (subtrees != null) {
126          for (int i = 0; i < subtrees.Count; i++) depth = Math.Max(depth, (ushort)subtrees[i].GetDepth());
127        }
128        depth++;
129        return depth;
130      }
131    }
132
133    public int GetBranchLevel(ISymbolicExpressionTreeNode child) {
134      return GetBranchLevel(this, child);
135    }
136
137    private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
138      if (root == point)
139        return 0;
140      foreach (var subtree in root.Subtrees) {
141        int branchLevel = GetBranchLevel(subtree, point);
142        if (branchLevel < int.MaxValue)
143          return 1 + branchLevel;
144      }
145      return int.MaxValue;
146    }
147
148    public virtual void ResetLocalParameters(IRandom random) { }
149    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
150
151    public int SubtreeCount {
152      get {
153        if (subtrees == null) return 0;
154        return subtrees.Count;
155      }
156    }
157
158    public virtual ISymbolicExpressionTreeNode GetSubtree(int index) {
159      return subtrees[index];
160    }
161    public virtual int IndexOfSubtree(ISymbolicExpressionTreeNode tree) {
162      return subtrees.IndexOf(tree);
163    }
164    public virtual void AddSubtree(ISymbolicExpressionTreeNode tree) {
165      subtrees.Add(tree);
166      tree.Parent = this;
167      ResetCachedValues();
168    }
169    public virtual void InsertSubtree(int index, ISymbolicExpressionTreeNode tree) {
170      subtrees.Insert(index, tree);
171      tree.Parent = this;
172      ResetCachedValues();
173    }
174    public virtual void RemoveSubtree(int index) {
175      subtrees[index].Parent = null;
176      subtrees.RemoveAt(index);
177      ResetCachedValues();
178    }
179
180    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
181      var list = new List<ISymbolicExpressionTreeNode>() { this };
182      int i = 0;
183      while (i != list.Count) {
184        for (int j = 0; j != list[i].SubtreeCount; ++j)
185          list.Add(list[i].GetSubtree(j));
186        ++i;
187      }
188      return list;
189    }
190
191    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
192      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
193      ForEachNodePrefix((n) => list.Add(n));
194      return list;
195    }
196
197    public void ForEachNodePrefix(Action<ISymbolicExpressionTreeNode> a) {
198      a(this);
199      if (Subtrees != null) {
200        foreach (var subtree in Subtrees) {
201          subtree.ForEachNodePrefix(a);
202        }
203      }
204    }
205
206    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix() {
207      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
208      ForEachNodePostfix((n) => list.Add(n));
209      return list;
210    }
211
212    public void ForEachNodePostfix(Action<ISymbolicExpressionTreeNode> a) {
213      if (Subtrees != null) {
214        foreach (var subtree in Subtrees) {
215          subtree.ForEachNodePostfix(a);
216        }
217      }
218      a(this);
219    }
220
221    public override string ToString() {
222      if (Symbol != null) return Symbol.Name;
223      return "SymbolicExpressionTreeNode";
224    }
225
226    private void ResetCachedValues() {
227      length = 0; depth = 0;
228      SymbolicExpressionTreeNode parentNode = parent as SymbolicExpressionTreeNode;
229      if (parentNode != null) parentNode.ResetCachedValues();
230    }
231  }
232}
Note: See TracBrowser for help on using the repository browser.