Changeset 10229

Timestamp:

12/15/13 15:56:42 (11 years ago)

Author:

sawinkle

Message:

#2109: Implemented a DepthFirstMapper, which works similarly to the DepthFirstMapper, but uses a queue to enable a breath-first tree creation.

Location:

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers

Files:

• BreathFirstMapper.cs (modified) (4 diffs)
• DepthFirstMapper.cs (modified) (2 diffs)

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/BreathFirstMapper.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -25 +27 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GrammaticalEvolution {
@@ -30 +33 @@
   /// BreathFirstMapper
   /// </summary>
-  [Item("BreathFirstMapper", "")]
+  [Item("BreathFirstMapper", "Resolves the non-terminal symbols of the resulting phenotypic syntax tree in a breath-first manner.")]
   [StorableClass]
   public class BreathFirstMapper : GenotypeToPhenotypeMapper {
@@ -60 +63 @@
       tree.Root = rootNode;
 
-      // TODO
+      MapBreathFirstIteratively(startNode, genotype, grammar,
+                                genotype.Length, new MersenneTwister());
 
       return tree;
     }
+
+    /// <summary>
+    /// Genotype-to-Phenotype mapper (iterative breath-first approach, by using a queue -> FIFO).
+    /// </summary>
+    /// <param name="startNode">first node of the tree with arity 1</param>
+    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
+    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
+    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
+    /// <param name="random">random number generator</param>
+    private void MapBreathFirstIteratively(ISymbolicExpressionTreeNode startNode,
+                                          IntegerVector genotype,
+                                          ISymbolicExpressionGrammar grammar,
+                                          int maxSubtreeCount, IRandom random) {
+
+      Queue<Tuple<ISymbolicExpressionTreeNode, int>> queue
+        = new Queue<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>
+
+      int genotypeIndex = 0;
+      int currSubtreeCount = 1;
+
+      queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
+
+      while ((currSubtreeCount < maxSubtreeCount) && (queue.Count > 0)) {
+
+        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
+
+        // foreach subtree of the current node, create a new node and enqueue it, if it is no terminal node
+        for (int i = 0; i < current.Item2; ++i) {
+
+          var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
+          int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount);
+
+          if (arity < 0) {
+            current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
+          } else {
+            current.Item1.AddSubtree(newNode);
+            genotypeIndex++;
+            currSubtreeCount += arity;
+            if (arity > 0) {
+              // new node has subtrees so enqueue the node 
+              queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));
+            }
+          }
+        }
+      }
+
+      // maximum allowed subtree count was already reached, but there are still
+      // incomplete subtrees (non-terminal symbols) in the tree
+      // -> fill them with terminal symbols
+      while (queue.Count > 0) {
+        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
+        for (int i = 0; i < current.Item2; ++i) {
+          current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
+        }
+      }
+    }
   }
 }

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

@@ -33 +33 @@
   /// DepthFirstMapper
   /// </summary>
-  [Item("DepthFirstMapper", "")]
+  [Item("DepthFirstMapper", "Resolves the non-terminal symbols of the resulting phenotypic syntax tree in a depth-first manner.")]
   [StorableClass]
   public class DepthFirstMapper : GenotypeToPhenotypeMapper {
@@ -135 +135 @@
 
     /// <summary>
-    /// Genotype-to-Phenotype mapper (iterative depth-first approach).
+    /// Genotype-to-Phenotype mapper (iterative depth-first approach, by using a stack -> LIFO).
     /// </summary>
     /// <param name="startNode">first node of the tree with arity 1</param>