Changeset 14352


Ignore:
Timestamp:
10/23/16 18:49:21 (4 years ago)
Author:
bburlacu
Message:

#2685: Refactored length and depth calculation and updated unit tests.

Location:
trunk/sources
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

    r14342 r14352  
    2525using System.Collections.Generic;
    2626using System.Linq;
    27 
    2827namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    2928  public static class GrammarUtils {
     29    private static IEnumerable<ISymbol> GetTopmostSymbols(this ISymbolicExpressionGrammarBase grammar) {
     30      // build parents list so we can find out the topmost symbol(s)
     31      var parents = new Dictionary<ISymbol, List<ISymbol>>();
     32      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) > 0)) {
     33        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
     34        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
     35          foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
     36            if (!parents.ContainsKey(childSymbol))
     37              parents[childSymbol] = new List<ISymbol>();
     38            parents[childSymbol].Add(symbol);
     39          }
     40        }
     41      }
     42      // the topmost symbols have no parents
     43      return parents.Values.SelectMany(x => x).Distinct().Where(x => !parents.ContainsKey(x));
     44    }
    3045
    3146    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
    3247      Dictionary<string, int> minimumExpressionLengths) {
    33 
    3448      minimumExpressionLengths.Clear();
    3549      //terminal symbols => minimum expression length = 1
    36       foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
    37         minimumExpressionLengths[s.Name] = 1;
     50      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) == 0))
     51        minimumExpressionLengths.Add(symbol.Name, 1);
    3852
    39       var symbolAdded = true;
    40       while (symbolAdded) {
    41         symbolAdded = false;
    42         foreach (var remainingSymbol in grammar.Symbols) {
    43           if (minimumExpressionLengths.ContainsKey(remainingSymbol.Name)) continue;
     53      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     54        // sort symbols in reverse breadth order (starting from the topSymbol)
     55        // each symbol is visited only once (this avoids infinite recursion)
     56        var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
     57        var visited = new HashSet<ISymbol> { topSymbol };
     58        int i = 0, index = 0;
     59        while (i < numberedSymbols.Count) {
     60          var symbol = numberedSymbols[i].Item1;
     61          var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
    4462
    45           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    46           int minLength = 1;
     63          for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
     64            foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
     65              if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
     66                continue;
    4767
    48           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    49             var capturedMinimumLengths = minimumExpressionLengths;
    50             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    51               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumLengths.ContainsKey(c.Name));
     68              if (visited.Add(childSymbol)) {
     69                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
     70              }
     71            }
     72          }
     73          ++i;
     74        }
     75        numberedSymbols.Reverse(); // sort descending by index
    5276
    53             if (!childSymbols.Any()) {
    54               minLength = -1;
    55               break;
    56             }
    57             var minLengthPerArgument = childSymbols.Min(c => capturedMinimumLengths[c.Name]);
    58             minLength += minLengthPerArgument;
     77        // going bottom-up (reverse breadth order), we ensure lengths are calculated bottom-up
     78        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     79          long minLength = 1;
     80          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
     81            long length = grammar.GetAllowedChildSymbols(symbol, argIndex)
     82              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
     83              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
     84            minLength += length;
    5985          }
    60 
    61           if (minLength != -1) {
    62             minimumExpressionLengths[remainingSymbol.Name] = minLength;
    63             symbolAdded = true;
    64           }
     86          int oldLength;
     87          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
     88            minLength = Math.Min(minLength, oldLength);
     89          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
    6590        }
    6691      }
    6792
    68       //set minLength to int.Maxvalue for all symbols that are not reacheable
     93      //set minLength to int.MaxValue for all symbols that are not reacheable
    6994      foreach (var remainingSymbols in grammar.Symbols) {
    7095        if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
     
    7297      }
    7398    }
    74 
    7599
    76100    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
     
    82106        minimumExpressionDepths[s.Name] = 1;
    83107
    84       var symbolAdded = true;
    85       while (symbolAdded) {
    86         symbolAdded = false;
    87         foreach (var remainingSymbol in grammar.Symbols) {
    88           if (minimumExpressionDepths.ContainsKey(remainingSymbol.Name)) continue;
     108      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     109        // sort symbols in reverse breadth order (starting from the topSymbol)
     110        // each symbol is visited only once (this avoids infinite recursion)
     111        var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
     112        var visited = new HashSet<ISymbol> { topSymbol };
     113        int i = 0, index = 0;
     114        while (i < numberedSymbols.Count) {
     115          var symbol = numberedSymbols[i].Item1;
     116          var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
    89117
    90           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    91           int minDepth = -1;
     118          for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
     119            foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
     120              if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
     121                continue;
    92122
    93           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    94             var capturedMinimumDepths = minimumExpressionDepths;
    95             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    96               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumDepths.ContainsKey(c.Name));
    97             if (!childSymbols.Any()) {
    98               minDepth = -1;
    99               break;
     123              if (visited.Add(childSymbol)) {
     124                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
     125              }
    100126            }
    101             var minDepthPerArgument = childSymbols.Min(c => capturedMinimumDepths[c.Name]);
    102             minDepth = Math.Max(minDepth, 1 + minDepthPerArgument);
    103127          }
     128          ++i;
     129        }
     130        numberedSymbols.Reverse(); // sort descending by index
    104131
    105           if (minDepth != -1) {
    106             minimumExpressionDepths[remainingSymbol.Name] = minDepth;
    107             symbolAdded = true;
     132        // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
     133        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     134          long minDepth = int.MaxValue;
     135          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
     136            long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
     137              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
     138              .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
     139            minDepth = Math.Min(minDepth, depth + 1);
    108140          }
     141          int oldDepth;
     142          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
     143            minDepth = Math.Min(minDepth, oldDepth);
     144          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
    109145        }
    110146      }
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs

    r14341 r14352  
    3030    [TestProperty("Time", "short")]
    3131    public void MinimumExpressionLengthTest() {
    32       var grammar = CreateAbstractGrammar();
    33 
    34       var prs = grammar.ProgramRootSymbol;
    35       var a = grammar.Symbols.First(s => s.Name == "<a>");
    36       var b = grammar.Symbols.First(s => s.Name == "<b>");
    37 
    38       Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
    39       Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
    40       Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
     32      {
     33        var grammar = CreateTestGrammar1();
     34
     35        var prs = grammar.ProgramRootSymbol;
     36        var ss = grammar.StartSymbol;
     37        var x = grammar.Symbols.First(s => s.Name == "<x>");
     38
     39        Assert.AreEqual(8, grammar.GetMinimumExpressionLength(prs));
     40        Assert.AreEqual(7, grammar.GetMinimumExpressionLength(ss));
     41        Assert.AreEqual(6, grammar.GetMinimumExpressionLength(x));
     42      }
     43
     44      {
     45        var grammar = CreateTestGrammar2();
     46
     47        var prs = grammar.ProgramRootSymbol;
     48        var ss = grammar.StartSymbol;
     49        var x = grammar.Symbols.First(s => s.Name == "<x>");
     50
     51        Assert.AreEqual(13, grammar.GetMinimumExpressionLength(prs));
     52        Assert.AreEqual(12, grammar.GetMinimumExpressionLength(ss));
     53        Assert.AreEqual(11, grammar.GetMinimumExpressionLength(x));
     54      }
     55
     56      {
     57        var grammar = CreateTestGrammar3();
     58        var prs = grammar.ProgramRootSymbol;
     59        var ss = grammar.StartSymbol;
     60        var x = grammar.Symbols.First(s => s.Name == "<x>");
     61        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
     62        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
     63        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
     64      }
     65
     66      {
     67        var grammar = CreateTestGrammar4();
     68        var prs = grammar.ProgramRootSymbol;
     69        var ss = grammar.StartSymbol;
     70        var x = grammar.Symbols.First(s => s.Name == "<x>");
     71        var y = grammar.Symbols.First(s => s.Name == "<y>");
     72        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
     73        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
     74        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
     75        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(y));
     76      }
     77
     78      {
     79        var grammar = CreateTestGrammar5();
     80        var prs = grammar.ProgramRootSymbol;
     81        var ss = grammar.StartSymbol;
     82        var x = grammar.Symbols.First(s => s.Name == "<x>");
     83        var y = grammar.Symbols.First(s => s.Name == "<y>");
     84        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(prs));
     85        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(ss));
     86        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(x));
     87        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
     88      }
    4189    }
    4290
     
    4593    [TestProperty("Time", "short")]
    4694    public void MinimumExpressionDepthTest() {
    47       var grammar = CreateAbstractGrammar();
    48 
    49       var prs = grammar.ProgramRootSymbol;
    50       var a = grammar.Symbols.First(s => s.Name == "<a>");
    51       var b = grammar.Symbols.First(s => s.Name == "<b>");
    52 
    53       Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
    54       Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
    55       Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
    56     }
    57 
    58     private static ISymbolicExpressionGrammar CreateAbstractGrammar() {
    59       var grammar = new SimpleSymbolicExpressionGrammar();
    60       var x = new SimpleSymbol("<x>", 1);
    61       var s = new SimpleSymbol("<s>", 1);
     95      {
     96        var grammar = CreateTestGrammar1();
     97
     98        var prs = grammar.ProgramRootSymbol;
     99        var ss = grammar.StartSymbol;
     100        var a = grammar.Symbols.First(s => s.Name == "<a>");
     101        var b = grammar.Symbols.First(s => s.Name == "<b>");
     102        var c = grammar.Symbols.First(s => s.Name == "<c>");
     103        var d = grammar.Symbols.First(s => s.Name == "<d>");
     104        var x = grammar.Symbols.First(s => s.Name == "x");
     105        var y = grammar.Symbols.First(s => s.Name == "y");
     106
     107        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     108        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     109        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
     110        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
     111        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
     112        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
     113        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
     114        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
     115      }
     116
     117      {
     118        var grammar = CreateTestGrammar2();
     119
     120        var prs = grammar.ProgramRootSymbol;
     121        var ss = grammar.StartSymbol;
     122        var a = grammar.Symbols.First(s => s.Name == "<a>");
     123        var b = grammar.Symbols.First(s => s.Name == "<b>");
     124        var c = grammar.Symbols.First(s => s.Name == "<c>");
     125        var d = grammar.Symbols.First(s => s.Name == "<d>");
     126        var x = grammar.Symbols.First(s => s.Name == "x");
     127        var y = grammar.Symbols.First(s => s.Name == "y");
     128
     129        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     130        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     131        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
     132        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
     133        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
     134        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
     135        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
     136        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
     137      }
     138
     139      {
     140        var grammar = CreateTestGrammar3();
     141        var prs = grammar.ProgramRootSymbol;
     142        var ss = grammar.StartSymbol;
     143        var x = grammar.Symbols.First(s => s.Name == "<x>");
     144        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
     145        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
     146        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
     147      }
     148
     149      {
     150        var grammar = CreateTestGrammar4();
     151        var prs = grammar.ProgramRootSymbol;
     152        var ss = grammar.StartSymbol;
     153        var x = grammar.Symbols.First(s => s.Name == "<x>");
     154        var y = grammar.Symbols.First(s => s.Name == "<y>");
     155        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
     156        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
     157        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
     158        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(y));
     159      }
     160
     161      {
     162        var grammar = CreateTestGrammar5();
     163        var prs = grammar.ProgramRootSymbol;
     164        var ss = grammar.StartSymbol;
     165        var x = grammar.Symbols.First(s => s.Name == "<x>");
     166        var y = grammar.Symbols.First(s => s.Name == "<y>");
     167        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     168        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     169        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(x));
     170        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
     171      }
     172    }
     173
     174    private static ISymbolicExpressionGrammar CreateTestGrammar1() {
     175      var grammar = new SimpleSymbolicExpressionGrammar();
     176      var x = new SimpleSymbol("<x>", 1);
     177      var z = new SimpleSymbol("<z>", 6);
    62178      var a = new SimpleSymbol("<a>", 1);
    63179      var b = new SimpleSymbol("<b>", 1);
    64180      var c = new SimpleSymbol("<c>", 1);
    65181      var d = new SimpleSymbol("<d>", 1);
    66       var e = new SimpleSymbol("<e>", 1);
    67182
    68183      var _x = new SimpleSymbol("x", 0);
     
    70185
    71186      grammar.AddSymbol(x);
    72       grammar.AddSymbol(s);
     187      grammar.AddSymbol(z);
    73188      grammar.AddSymbol(a);
    74189      grammar.AddSymbol(b);
    75190      grammar.AddSymbol(c);
    76191      grammar.AddSymbol(d);
    77       grammar.AddSymbol(e);
    78192      grammar.AddSymbol(_x);
    79193      grammar.AddSymbol(_y);
    80194
    81195      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
    82       grammar.AddAllowedChildSymbol(x, s);
    83       grammar.AddAllowedChildSymbol(x, _x);
    84       grammar.AddAllowedChildSymbol(s, a);
     196      //uncommenting the line below changes the minimum expression length for the symbol <x>
     197      grammar.AddAllowedChildSymbol(x, z);
     198      grammar.AddAllowedChildSymbol(z, _x);
     199      grammar.AddAllowedChildSymbol(x, a);
    85200      grammar.AddAllowedChildSymbol(a, b);
    86       grammar.AddAllowedChildSymbol(a, c);
    87       grammar.AddAllowedChildSymbol(b, x);
     201      grammar.AddAllowedChildSymbol(b, c);
    88202      grammar.AddAllowedChildSymbol(c, d);
    89       grammar.AddAllowedChildSymbol(d, e);
    90       grammar.AddAllowedChildSymbol(e, _y);
    91 
     203      grammar.AddAllowedChildSymbol(d, _y);
     204
     205      return grammar;
     206    }
     207
     208    private static ISymbolicExpressionGrammar CreateTestGrammar2() {
     209      var grammar = new SimpleSymbolicExpressionGrammar();
     210      var x = new SimpleSymbol("<x>", 2);
     211      var z = new SimpleSymbol("<z>", 6);
     212      var a = new SimpleSymbol("<a>", 1);
     213      var b = new SimpleSymbol("<b>", 1);
     214      var c = new SimpleSymbol("<c>", 1);
     215      var d = new SimpleSymbol("<d>", 1);
     216
     217      var _x = new SimpleSymbol("x", 0);
     218      var _y = new SimpleSymbol("y", 0);
     219
     220      grammar.AddSymbol(x);
     221      grammar.AddSymbol(z);
     222      grammar.AddSymbol(a);
     223      grammar.AddSymbol(b);
     224      grammar.AddSymbol(c);
     225      grammar.AddSymbol(d);
     226      grammar.AddSymbol(_x);
     227      grammar.AddSymbol(_y);
     228
     229      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     230      //uncommenting the line below changes the minimum expression length for the symbol <x>
     231      grammar.AddAllowedChildSymbol(x, z);
     232      grammar.AddAllowedChildSymbol(z, _x);
     233      grammar.AddAllowedChildSymbol(x, a);
     234      grammar.AddAllowedChildSymbol(a, b);
     235      grammar.AddAllowedChildSymbol(b, c);
     236      grammar.AddAllowedChildSymbol(c, d);
     237      grammar.AddAllowedChildSymbol(d, _y);
     238
     239      return grammar;
     240    }
     241
     242    private static ISymbolicExpressionGrammar CreateTestGrammar3() {
     243      var grammar = new SimpleSymbolicExpressionGrammar();
     244      var x = new SimpleSymbol("<x>", 1);
     245
     246      grammar.AddSymbol(x);
     247
     248      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     249      grammar.AddAllowedChildSymbol(x, x);
     250      return grammar;
     251    }
     252
     253
     254    private static ISymbolicExpressionGrammar CreateTestGrammar4() {
     255      var grammar = new SimpleSymbolicExpressionGrammar();
     256      var x = new SimpleSymbol("<x>", 1);
     257      var y = new SimpleSymbol("<y>", 1);
     258
     259      grammar.AddSymbol(x);
     260      grammar.AddSymbol(y);
     261
     262      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     263      grammar.AddAllowedChildSymbol(x, x);
     264      grammar.AddAllowedChildSymbol(x, y);
     265      grammar.AddAllowedChildSymbol(y, x);
     266      grammar.AddAllowedChildSymbol(y, y);
     267      return grammar;
     268    }
     269
     270    private static ISymbolicExpressionGrammar CreateTestGrammar5() {
     271      var grammar = new SimpleSymbolicExpressionGrammar();
     272      var x = new SimpleSymbol("<x>", 1);
     273      var y = new SimpleSymbol("<y>", 1);
     274      var _x = new SimpleSymbol("x", 0);
     275
     276      grammar.AddSymbol(x);
     277      grammar.AddSymbol(y);
     278      grammar.AddSymbol(_x);
     279
     280      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     281      grammar.AddAllowedChildSymbol(x, x);
     282      grammar.AddAllowedChildSymbol(x, y);
     283      grammar.AddAllowedChildSymbol(y, x);
     284      grammar.AddAllowedChildSymbol(y, y);
     285      grammar.AddAllowedChildSymbol(y, _x);
    92286      return grammar;
    93287    }
Note: See TracChangeset for help on using the changeset viewer.