source: branches/2839_HiveProjectManagement/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/Util.cs @ 16057

Last change on this file since 16057 was 16057, checked in by jkarder, 2 years ago

#2839:

File size: 8.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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;
28
29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Tests {
30  public static class Util {
31    public static string GetSizeDistributionString(IList<ISymbolicExpressionTree> trees, int maxTreeLength, int binSize) {
32      int[] histogram = new int[maxTreeLength / binSize];
33      for (int i = 0; i < trees.Count; i++) {
34        int binIndex = Math.Min(histogram.Length - 1, trees[i].Length / binSize);
35        histogram[binIndex]++;
36      }
37      StringBuilder strBuilder = new StringBuilder();
38      for (int i = 0; i < histogram.Length - 1; i++) {
39        strBuilder.Append(Environment.NewLine);
40        strBuilder.Append("< "); strBuilder.Append((i + 1) * binSize);
41        strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)trees.Count);
42      }
43      strBuilder.Append(Environment.NewLine);
44      strBuilder.Append(">= "); strBuilder.Append(histogram.Length * binSize);
45      strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[histogram.Length - 1] / (double)trees.Count);
46
47      return "Size distribution: " + strBuilder;
48    }
49
50    public static string GetFunctionDistributionString(IList<ISymbolicExpressionTree> trees) {
51      Dictionary<string, int> occurances = new Dictionary<string, int>();
52      double n = 0.0;
53      for (int i = 0; i < trees.Count; i++) {
54        foreach (var node in trees[i].IterateNodesPrefix()) {
55          if (node.Subtrees.Count() > 0) {
56            if (!occurances.ContainsKey(node.Symbol.Name))
57              occurances[node.Symbol.Name] = 0;
58            occurances[node.Symbol.Name]++;
59            n++;
60          }
61        }
62      }
63      StringBuilder strBuilder = new StringBuilder();
64      foreach (var function in occurances.Keys) {
65        strBuilder.Append(Environment.NewLine);
66        strBuilder.Append(function); strBuilder.Append(": ");
67        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
68      }
69      return "Function distribution: " + strBuilder;
70    }
71
72    public static string GetNumberOfSubtreesDistributionString(IList<ISymbolicExpressionTree> trees) {
73      Dictionary<int, int> occurances = new Dictionary<int, int>();
74      double n = 0.0;
75      for (int i = 0; i < trees.Count; i++) {
76        foreach (var node in trees[i].IterateNodesPrefix()) {
77          if (!occurances.ContainsKey(node.Subtrees.Count()))
78            occurances[node.Subtrees.Count()] = 0;
79          occurances[node.Subtrees.Count()]++;
80          n++;
81        }
82      }
83      StringBuilder strBuilder = new StringBuilder();
84      foreach (var arity in occurances.Keys) {
85        strBuilder.Append(Environment.NewLine);
86        strBuilder.Append(arity); strBuilder.Append(": ");
87        strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
88      }
89      return "Distribution of function arities: " + strBuilder;
90    }
91
92
93    public static string GetTerminalDistributionString(IList<ISymbolicExpressionTree> trees) {
94      Dictionary<string, int> occurances = new Dictionary<string, int>();
95      double n = 0.0;
96      for (int i = 0; i < trees.Count; i++) {
97        foreach (var node in trees[i].IterateNodesPrefix()) {
98          if (node.Subtrees.Count() == 0) {
99            if (!occurances.ContainsKey(node.Symbol.Name))
100              occurances[node.Symbol.Name] = 0;
101            occurances[node.Symbol.Name]++;
102            n++;
103          }
104        }
105      }
106      StringBuilder strBuilder = new StringBuilder();
107      foreach (var function in occurances.Keys) {
108        strBuilder.Append(Environment.NewLine);
109        strBuilder.Append(function); strBuilder.Append(": ");
110        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
111      }
112      return "Terminal distribution: " + strBuilder;
113    }
114
115    public static void IsValid(ISymbolicExpressionTree tree) {
116      int reportedSize = tree.Length;
117      int actualSize = tree.IterateNodesPostfix().Count();
118      Assert.AreEqual(actualSize, reportedSize);
119
120      foreach (var defunTreeNode in tree.Root.Subtrees.OfType<DefunTreeNode>()) {
121        int arity = defunTreeNode.NumberOfArguments;
122
123        foreach (var argTreenode in defunTreeNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()) {
124          Assert.IsTrue(argTreenode.SubtreeCount == 0);
125          Assert.IsTrue(((Argument)argTreenode.Symbol).ArgumentIndex < arity);
126        }
127
128        foreach (var argSymbol in Enumerable.Range(0, defunTreeNode.NumberOfArguments).Select(x => new Argument(x))) {
129          Assert.IsTrue(defunTreeNode.Grammar.ContainsSymbol(argSymbol));
130          Assert.IsTrue(defunTreeNode.Grammar.GetMaximumSubtreeCount(argSymbol) == 0);
131          Assert.IsTrue(defunTreeNode.Grammar.GetMinimumSubtreeCount(argSymbol) == 0);
132        }
133
134        var invoke = new InvokeFunction(defunTreeNode.FunctionName);
135        foreach (var otherRootNode in tree.Root.Subtrees) {
136          if (otherRootNode.Grammar.ContainsSymbol(invoke)) {
137            Assert.IsTrue(otherRootNode.Grammar.GetMinimumSubtreeCount(invoke) == arity);
138            Assert.IsTrue(otherRootNode.Grammar.GetMaximumSubtreeCount(invoke) == arity);
139            Assert.IsFalse(otherRootNode.Grammar.IsAllowedChildSymbol(invoke, invoke));
140            for (int i = 0; i < arity; i++) {
141              Assert.IsFalse(otherRootNode.Grammar.IsAllowedChildSymbol(invoke, invoke, i));
142            }
143          }
144        }
145
146      }
147
148      foreach (var subtree in tree.Root.Subtrees) {
149        if (tree.Root.Grammar.GetType().Name != "EmptySymbolicExpressionTreeGrammar")
150          Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
151        IsValid(subtree.Grammar);
152      }
153
154      IsValid(tree.Root.Grammar);
155      IsValid(tree.Root);
156    }
157
158    public static void IsValid(ISymbolicExpressionTreeGrammar grammar) {
159      Assert.IsTrue(grammar.Symbols.Count() == grammar.Symbols.Distinct().Count());
160      foreach (ISymbol symbol in grammar.AllowedSymbols) {
161        Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol).Count() == grammar.GetAllowedChildSymbols(symbol).Distinct().Count());
162        for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++) {
163          Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol, i).Count() == grammar.GetAllowedChildSymbols(symbol, i).Distinct().Count());
164        }
165      }
166
167      foreach (var symbol in grammar.ModifyableSymbols) {
168        //check if every symbol has at least one allowed child
169        for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++)
170          Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol, i).Any());
171      }
172    }
173
174    public static void IsValid(ISymbolicExpressionTreeNode treeNode) {
175      var matchingSymbol = (from symb in treeNode.Grammar.Symbols
176                            where symb.Name == treeNode.Symbol.Name
177                            select symb).SingleOrDefault();
178      Assert.IsTrue(treeNode.Subtrees.Count() >= treeNode.Grammar.GetMinimumSubtreeCount(matchingSymbol));
179      Assert.IsTrue(treeNode.Subtrees.Count() <= treeNode.Grammar.GetMaximumSubtreeCount(matchingSymbol));
180      Assert.AreNotEqual(0.0, matchingSymbol.InitialFrequency); // check that no deactivated symbols occur in the tree
181      for (int i = 0; i < treeNode.Subtrees.Count(); i++) {
182        Assert.IsTrue(treeNode.Grammar.GetAllowedChildSymbols(treeNode.Symbol, i).Select(x => x.Name).Contains(treeNode.GetSubtree(i).Symbol.Name));
183        IsValid(treeNode.GetSubtree(i));
184      }
185    }
186  }
187}
Note: See TracBrowser for help on using the repository browser.