Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs @ 4524

Last change on this file since 4524 was 4524, checked in by gkronber, 13 years ago

Fixed #1214. The size of the manipulated tree is checked and only if the new tree fulfills the size requirements it is accepted otherwise the original tree is returned instead. Additionally the calculation of tree sizes is checked for overflows now.

File size: 6.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 System.Linq;
25using System.Text;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using Microsoft.VisualStudio.TestTools.UnitTesting;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
31  public static class Util {
32    public static string GetSizeDistributionString(IList<SymbolicExpressionTree> trees, int maxTreeSize, int binSize) {
33      int[] histogram = new int[maxTreeSize / binSize];
34      for (int i = 0; i < trees.Count; i++) {
35        int binIndex = Math.Min(histogram.Length - 1, trees[i].Size / binSize);
36        histogram[binIndex]++;
37      }
38      StringBuilder strBuilder = new StringBuilder();
39      for (int i = 0; i < histogram.Length - 1; i++) {
40        strBuilder.Append(Environment.NewLine);
41        strBuilder.Append("< "); strBuilder.Append((i + 1) * binSize);
42        strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)trees.Count);
43      }
44      strBuilder.Append(Environment.NewLine);
45      strBuilder.Append(">= "); strBuilder.Append(histogram.Length * binSize);
46      strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[histogram.Length - 1] / (double)trees.Count);
47
48      return "Size distribution: " + strBuilder;
49    }
50
51    public static string GetFunctionDistributionString(IList<SymbolicExpressionTree> trees) {
52      Dictionary<string, int> occurances = new Dictionary<string, int>();
53      double n = 0.0;
54      for (int i = 0; i < trees.Count; i++) {
55        foreach (var node in trees[i].IterateNodesPrefix()) {
56          if (node.SubTrees.Count > 0) {
57            if (!occurances.ContainsKey(node.Symbol.Name))
58              occurances[node.Symbol.Name] = 0;
59            occurances[node.Symbol.Name]++;
60            n++;
61          }
62        }
63      }
64      StringBuilder strBuilder = new StringBuilder();
65      foreach (var function in occurances.Keys) {
66        strBuilder.Append(Environment.NewLine);
67        strBuilder.Append(function); strBuilder.Append(": ");
68        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
69      }
70      return "Function distribution: " + strBuilder;
71    }
72
73    public static string GetNumberOfSubTreesDistributionString(IList<SymbolicExpressionTree> trees) {
74      Dictionary<int, int> occurances = new Dictionary<int, int>();
75      double n = 0.0;
76      for (int i = 0; i < trees.Count; i++) {
77        foreach (var node in trees[i].IterateNodesPrefix()) {
78          if (!occurances.ContainsKey(node.SubTrees.Count))
79            occurances[node.SubTrees.Count] = 0;
80          occurances[node.SubTrees.Count]++;
81          n++;
82        }
83      }
84      StringBuilder strBuilder = new StringBuilder();
85      foreach (var arity in occurances.Keys) {
86        strBuilder.Append(Environment.NewLine);
87        strBuilder.Append(arity); strBuilder.Append(": ");
88        strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
89      }
90      return "Distribution of function arities: " + strBuilder;
91    }
92
93
94    public static string GetTerminalDistributionString(IList<SymbolicExpressionTree> trees) {
95      Dictionary<string, int> occurances = new Dictionary<string, int>();
96      double n = 0.0;
97      for (int i = 0; i < trees.Count; i++) {
98        foreach (var node in trees[i].IterateNodesPrefix()) {
99          if (node.SubTrees.Count == 0) {
100            if (!occurances.ContainsKey(node.Symbol.Name))
101              occurances[node.Symbol.Name] = 0;
102            occurances[node.Symbol.Name]++;
103            n++;
104          }
105        }
106      }
107      StringBuilder strBuilder = new StringBuilder();
108      foreach (var function in occurances.Keys) {
109        strBuilder.Append(Environment.NewLine);
110        strBuilder.Append(function); strBuilder.Append(": ");
111        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
112      }
113      return "Terminal distribution: " + strBuilder;
114    }
115
116    public static void IsValid(SymbolicExpressionTree tree) {
117      int reportedSize = tree.Size;
118      int actualSize = tree.IterateNodesPostfix().Count();
119      Assert.AreEqual(actualSize, reportedSize);
120
121      foreach (var defunTreeNode in tree.Root.SubTrees.OfType<DefunTreeNode>()) {
122        int arity = defunTreeNode.NumberOfArguments;
123        var invoke = new InvokeFunction(defunTreeNode.FunctionName);
124        foreach (var otherRootNode in tree.Root.SubTrees) {
125          if (otherRootNode.Grammar.ContainsSymbol(invoke)) {
126            Assert.IsTrue(otherRootNode.Grammar.GetMinSubtreeCount(invoke) == arity);
127            Assert.IsTrue(otherRootNode.Grammar.GetMaxSubtreeCount(invoke) == arity);
128          }
129        }
130      }
131      //Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
132      //foreach (var subtree in tree.Root.SubTrees)
133      //  Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
134      IsValid(tree.Root);
135    }
136
137    public static void IsValid(SymbolicExpressionTreeNode treeNode) {
138      var matchingSymbol = (from symb in treeNode.Grammar.Symbols
139                            where symb.Name == treeNode.Symbol.Name
140                            select symb).SingleOrDefault();
141      Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
142      Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
143      for (int i = 0; i < treeNode.SubTrees.Count; i++) {
144        Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));
145        IsValid(treeNode.SubTrees[i]);
146      }
147    }
148  }
149}
Note: See TracBrowser for help on using the repository browser.