Index: /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs
===================================================================
--- /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs	(revision 14351)
+++ /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs	(revision 14352)
@@ -25,46 +25,71 @@
 using System.Collections.Generic;
 using System.Linq;
-
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   public static class GrammarUtils {
+    private static IEnumerable<ISymbol> GetTopmostSymbols(this ISymbolicExpressionGrammarBase grammar) {
+      // build parents list so we can find out the topmost symbol(s)
+      var parents = new Dictionary<ISymbol, List<ISymbol>>();
+      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) > 0)) {
+        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
+        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
+          foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
+            if (!parents.ContainsKey(childSymbol))
+              parents[childSymbol] = new List<ISymbol>();
+            parents[childSymbol].Add(symbol);
+          }
+        }
+      }
+      // the topmost symbols have no parents
+      return parents.Values.SelectMany(x => x).Distinct().Where(x => !parents.ContainsKey(x));
+    }
 
     public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
       Dictionary<string, int> minimumExpressionLengths) {
-
       minimumExpressionLengths.Clear();
       //terminal symbols => minimum expression length = 1
-      foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
-        minimumExpressionLengths[s.Name] = 1;
+      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) == 0))
+        minimumExpressionLengths.Add(symbol.Name, 1);
 
-      var symbolAdded = true;
-      while (symbolAdded) {
-        symbolAdded = false;
-        foreach (var remainingSymbol in grammar.Symbols) {
-          if (minimumExpressionLengths.ContainsKey(remainingSymbol.Name)) continue;
+      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
+        // sort symbols in reverse breadth order (starting from the topSymbol)
+        // each symbol is visited only once (this avoids infinite recursion)
+        var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
+        var visited = new HashSet<ISymbol> { topSymbol };
+        int i = 0, index = 0;
+        while (i < numberedSymbols.Count) {
+          var symbol = numberedSymbols[i].Item1;
+          var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
 
-          var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
-          int minLength = 1;
+          for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
+            foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
+              if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
+                continue;
 
-          foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
-            var capturedMinimumLengths = minimumExpressionLengths;
-            var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
-              .Where(c => c.InitialFrequency > 0.0 && capturedMinimumLengths.ContainsKey(c.Name));
+              if (visited.Add(childSymbol)) {
+                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
+              }
+            }
+          }
+          ++i;
+        }
+        numberedSymbols.Reverse(); // sort descending by index
 
-            if (!childSymbols.Any()) {
-              minLength = -1;
-              break;
-            }
-            var minLengthPerArgument = childSymbols.Min(c => capturedMinimumLengths[c.Name]);
-            minLength += minLengthPerArgument;
+        // going bottom-up (reverse breadth order), we ensure lengths are calculated bottom-up
+        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
+          long minLength = 1;
+          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
+            long length = grammar.GetAllowedChildSymbols(symbol, argIndex)
+              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
+              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
+            minLength += length;
           }
-
-          if (minLength != -1) {
-            minimumExpressionLengths[remainingSymbol.Name] = minLength;
-            symbolAdded = true;
-          }
+          int oldLength;
+          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
+            minLength = Math.Min(minLength, oldLength);
+          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
         }
       }
 
-      //set minLength to int.Maxvalue for all symbols that are not reacheable
+      //set minLength to int.MaxValue for all symbols that are not reacheable
       foreach (var remainingSymbols in grammar.Symbols) {
         if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
@@ -72,5 +97,4 @@
       }
     }
-
 
     public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
@@ -82,29 +106,41 @@
         minimumExpressionDepths[s.Name] = 1;
 
-      var symbolAdded = true;
-      while (symbolAdded) {
-        symbolAdded = false;
-        foreach (var remainingSymbol in grammar.Symbols) {
-          if (minimumExpressionDepths.ContainsKey(remainingSymbol.Name)) continue;
+      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
+        // sort symbols in reverse breadth order (starting from the topSymbol)
+        // each symbol is visited only once (this avoids infinite recursion)
+        var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
+        var visited = new HashSet<ISymbol> { topSymbol };
+        int i = 0, index = 0;
+        while (i < numberedSymbols.Count) {
+          var symbol = numberedSymbols[i].Item1;
+          var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
 
-          var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
-          int minDepth = -1;
+          for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
+            foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
+              if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
+                continue;
 
-          foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
-            var capturedMinimumDepths = minimumExpressionDepths;
-            var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
-              .Where(c => c.InitialFrequency > 0.0 && capturedMinimumDepths.ContainsKey(c.Name));
-            if (!childSymbols.Any()) {
-              minDepth = -1;
-              break;
+              if (visited.Add(childSymbol)) {
+                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
+              }
             }
-            var minDepthPerArgument = childSymbols.Min(c => capturedMinimumDepths[c.Name]);
-            minDepth = Math.Max(minDepth, 1 + minDepthPerArgument);
           }
+          ++i;
+        }
+        numberedSymbols.Reverse(); // sort descending by index
 
-          if (minDepth != -1) {
-            minimumExpressionDepths[remainingSymbol.Name] = minDepth;
-            symbolAdded = true;
+        // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
+        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
+          long minDepth = int.MaxValue;
+          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
+            long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
+              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
+              .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
+            minDepth = Math.Min(minDepth, depth + 1);
           }
+          int oldDepth;
+          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
+            minDepth = Math.Min(minDepth, oldDepth);
+          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
         }
       }
Index: /trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs
===================================================================
--- /trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs	(revision 14351)
+++ /trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs	(revision 14352)
@@ -30,13 +30,61 @@
     [TestProperty("Time", "short")]
     public void MinimumExpressionLengthTest() {
-      var grammar = CreateAbstractGrammar();
-
-      var prs = grammar.ProgramRootSymbol;
-      var a = grammar.Symbols.First(s => s.Name == "<a>");
-      var b = grammar.Symbols.First(s => s.Name == "<b>");
-
-      Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
-      Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
-      Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
+      {
+        var grammar = CreateTestGrammar1();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+
+        Assert.AreEqual(8, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(7, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(6, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar2();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+
+        Assert.AreEqual(13, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(12, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(11, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar3();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar4();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar5();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
+      }
     }
 
@@ -45,24 +93,91 @@
     [TestProperty("Time", "short")]
     public void MinimumExpressionDepthTest() {
-      var grammar = CreateAbstractGrammar();
-
-      var prs = grammar.ProgramRootSymbol;
-      var a = grammar.Symbols.First(s => s.Name == "<a>");
-      var b = grammar.Symbols.First(s => s.Name == "<b>");
-
-      Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
-      Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
-      Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
-    }
-
-    private static ISymbolicExpressionGrammar CreateAbstractGrammar() {
-      var grammar = new SimpleSymbolicExpressionGrammar();
-      var x = new SimpleSymbol("<x>", 1);
-      var s = new SimpleSymbol("<s>", 1);
+      {
+        var grammar = CreateTestGrammar1();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        var x = grammar.Symbols.First(s => s.Name == "x");
+        var y = grammar.Symbols.First(s => s.Name == "y");
+
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar2();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        var x = grammar.Symbols.First(s => s.Name == "x");
+        var y = grammar.Symbols.First(s => s.Name == "y");
+
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar3();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar4();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar5();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
+      }
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar1() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var z = new SimpleSymbol("<z>", 6);
       var a = new SimpleSymbol("<a>", 1);
       var b = new SimpleSymbol("<b>", 1);
       var c = new SimpleSymbol("<c>", 1);
       var d = new SimpleSymbol("<d>", 1);
-      var e = new SimpleSymbol("<e>", 1);
 
       var _x = new SimpleSymbol("x", 0);
@@ -70,24 +185,103 @@
 
       grammar.AddSymbol(x);
-      grammar.AddSymbol(s);
+      grammar.AddSymbol(z);
       grammar.AddSymbol(a);
       grammar.AddSymbol(b);
       grammar.AddSymbol(c);
       grammar.AddSymbol(d);
-      grammar.AddSymbol(e);
       grammar.AddSymbol(_x);
       grammar.AddSymbol(_y);
 
       grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
-      grammar.AddAllowedChildSymbol(x, s);
-      grammar.AddAllowedChildSymbol(x, _x);
-      grammar.AddAllowedChildSymbol(s, a);
+      //uncommenting the line below changes the minimum expression length for the symbol <x>
+      grammar.AddAllowedChildSymbol(x, z);
+      grammar.AddAllowedChildSymbol(z, _x);
+      grammar.AddAllowedChildSymbol(x, a);
       grammar.AddAllowedChildSymbol(a, b);
-      grammar.AddAllowedChildSymbol(a, c);
-      grammar.AddAllowedChildSymbol(b, x);
+      grammar.AddAllowedChildSymbol(b, c);
       grammar.AddAllowedChildSymbol(c, d);
-      grammar.AddAllowedChildSymbol(d, e);
-      grammar.AddAllowedChildSymbol(e, _y);
-
+      grammar.AddAllowedChildSymbol(d, _y);
+
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar2() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 2);
+      var z = new SimpleSymbol("<z>", 6);
+      var a = new SimpleSymbol("<a>", 1);
+      var b = new SimpleSymbol("<b>", 1);
+      var c = new SimpleSymbol("<c>", 1);
+      var d = new SimpleSymbol("<d>", 1);
+
+      var _x = new SimpleSymbol("x", 0);
+      var _y = new SimpleSymbol("y", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(z);
+      grammar.AddSymbol(a);
+      grammar.AddSymbol(b);
+      grammar.AddSymbol(c);
+      grammar.AddSymbol(d);
+      grammar.AddSymbol(_x);
+      grammar.AddSymbol(_y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      //uncommenting the line below changes the minimum expression length for the symbol <x>
+      grammar.AddAllowedChildSymbol(x, z);
+      grammar.AddAllowedChildSymbol(z, _x);
+      grammar.AddAllowedChildSymbol(x, a);
+      grammar.AddAllowedChildSymbol(a, b);
+      grammar.AddAllowedChildSymbol(b, c);
+      grammar.AddAllowedChildSymbol(c, d);
+      grammar.AddAllowedChildSymbol(d, _y);
+
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar3() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+
+      grammar.AddSymbol(x);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      return grammar;
+    }
+
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar4() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var y = new SimpleSymbol("<y>", 1);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      grammar.AddAllowedChildSymbol(x, y);
+      grammar.AddAllowedChildSymbol(y, x);
+      grammar.AddAllowedChildSymbol(y, y);
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar5() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var y = new SimpleSymbol("<y>", 1);
+      var _x = new SimpleSymbol("x", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(y);
+      grammar.AddSymbol(_x);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      grammar.AddAllowedChildSymbol(x, y);
+      grammar.AddAllowedChildSymbol(y, x);
+      grammar.AddAllowedChildSymbol(y, y);
+      grammar.AddAllowedChildSymbol(y, _x);
       return grammar;
     }
