source: branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs @ 17768

Last change on this file since 17768 was 17768, checked in by chaider, 14 months ago

#3073

  • Removed Region class and used IntervallCollection instead
  • Changed Parser to work with IntervalColletions
  • Moved CheckConstraint methods from Analyzer to IntervalUtil class
  • Added CheckConstraint method to interface to check if an interval is in a given constraint
  • Added possibility to stop splitting as soon as a constraint is fulfiled
File size: 23.8 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Collections.ObjectModel;
4using System.Linq;
5using HEAL.Attic;
6using HeuristicLab.Common;
7using HeuristicLab.Core;
8using HeuristicLab.Data;
9using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
10using HeuristicLab.Parameters;
11
12namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
13  [StorableType("C8539434-6FB0-47D0-9F5A-2CAE5D8B8B4F")]
14  [Item("IA Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
15  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
16    #region Parameters
17
18    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
19    private const string UseIntervalSplittingParameterName = "Use Interval splitting";
20    private const string SplittingIterationsParameterName = "Splitting Iterations";
21    private const string SplittingWidthParameterName = "Splitting width";
22
23    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter =>
24      (IFixedValueParameter<IntValue>) Parameters[EvaluatedSolutionsParameterName];
25
26    public IFixedValueParameter<BoolValue> UseIntervalSplittingParameter =>
27      (IFixedValueParameter<BoolValue>) Parameters[UseIntervalSplittingParameterName];
28
29    public IFixedValueParameter<IntValue> SplittingIterationsParameter =>
30      (IFixedValueParameter<IntValue>) Parameters[SplittingIterationsParameterName];
31
32    public IFixedValueParameter<DoubleValue> SplittingWidthParameter =>
33      (IFixedValueParameter<DoubleValue>) Parameters[SplittingWidthParameterName];
34
35    public int EvaluatedSolutions {
36      get => EvaluatedSolutionsParameter.Value.Value;
37      set => EvaluatedSolutionsParameter.Value.Value = value;
38    }
39
40    public bool UseIntervalSplitting {
41      get => UseIntervalSplittingParameter.Value.Value;
42      set => UseIntervalSplittingParameter.Value.Value = value;
43    }
44
45    public int SplittingIterations {
46      get => SplittingIterationsParameter.Value.Value;
47      set => SplittingIterationsParameter.Value.Value = value;
48    }
49
50    public double SplittingWidth {
51      get => SplittingWidthParameter.Value.Value;
52      set => SplittingWidthParameter.Value.Value = value;
53    }
54
55    #endregion
56
57    #region Constructors
58
59    [StorableConstructor]
60    private IABoundsEstimator(StorableConstructorFlag _) : base(_) { }
61
62    private IABoundsEstimator(IABoundsEstimator original, Cloner cloner) : base(original, cloner) { }
63
64    public IABoundsEstimator() : base("IA Bounds Estimator",
65      "Estimates the bounds of the model with interval arithmetic") {
66      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
67        "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
68      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
69        "Defines whether interval splitting is activated or not.", new BoolValue(false)));
70      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName,
71        "Defines the number of iterations of splitting.", new IntValue(200)));
72      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName,
73        "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
74    }
75
76    public override IDeepCloneable Clone(Cloner cloner) {
77      return new IABoundsEstimator(this, cloner);
78    }
79
80    #endregion
81
82    #region IStatefulItem Members
83
84    private readonly object syncRoot = new object();
85
86    public void InitializeState() {
87      EvaluatedSolutions = 0;
88    }
89
90    public void ClearState() { }
91
92    #endregion
93
94    #region Evaluation
95
96    private static Instruction[] PrepareInterpreterState(
97      ISymbolicExpressionTree tree,
98      IDictionary<string, Interval> variableRanges) {
99      if (variableRanges == null)
100        throw new ArgumentNullException("No variablew ranges are present!", nameof(variableRanges));
101
102      //Check if all variables used in the tree are present in the dataset
103      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName)
104                                   .Distinct())
105        if (!variableRanges.ContainsKey(variable))
106          throw new InvalidOperationException($"No ranges for variable {variable} is present");
107
108      var code = SymbolicExpressionTreeCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
109      foreach (var instr in code.Where(i => i.opCode == OpCodes.Variable)) {
110        var variableTreeNode = (VariableTreeNode) instr.dynamicNode;
111        instr.data = variableRanges[variableTreeNode.VariableName];
112      }
113
114      return code;
115    }
116
117    public static Interval Evaluate(
118      Instruction[] instructions, ref int instructionCounter,
119      IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
120      IDictionary<string, Interval> variableIntervals = null) {
121      var currentInstr = instructions[instructionCounter];
122      //Use ref parameter, because the tree will be iterated through recursively from the left-side branch to the right side
123      //Update instructionCounter, whenever Evaluate is called
124      instructionCounter++;
125      Interval result = null;
126
127      switch (currentInstr.opCode) {
128        //Variables, Constants, ...
129        case OpCodes.Variable: {
130          var variableTreeNode = (VariableTreeNode) currentInstr.dynamicNode;
131          var weightInterval = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
132
133          Interval variableInterval;
134          if (variableIntervals != null && variableIntervals.ContainsKey(variableTreeNode.VariableName))
135            variableInterval = variableIntervals[variableTreeNode.VariableName];
136          else
137            variableInterval = (Interval) currentInstr.data;
138
139          result = Interval.Multiply(variableInterval, weightInterval);
140          break;
141        }
142        case OpCodes.Constant: {
143          var constTreeNode = (ConstantTreeNode) currentInstr.dynamicNode;
144          result = new Interval(constTreeNode.Value, constTreeNode.Value);
145          break;
146        }
147        //Elementary arithmetic rules
148        case OpCodes.Add: {
149          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
150          for (var i = 1; i < currentInstr.nArguments; i++) {
151            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
152            result = Interval.Add(result, argumentInterval);
153          }
154
155          break;
156        }
157        case OpCodes.Sub: {
158          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
159          if (currentInstr.nArguments == 1)
160            result = Interval.Multiply(new Interval(-1, -1), result);
161
162          for (var i = 1; i < currentInstr.nArguments; i++) {
163            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
164            result = Interval.Subtract(result, argumentInterval);
165          }
166
167          break;
168        }
169        case OpCodes.Mul: {
170          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
171          for (var i = 1; i < currentInstr.nArguments; i++) {
172            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
173            result = Interval.Multiply(result, argumentInterval);
174          }
175
176          break;
177        }
178        case OpCodes.Div: {
179          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
180          if (currentInstr.nArguments == 1)
181            result = Interval.Divide(new Interval(1, 1), result);
182
183          for (var i = 1; i < currentInstr.nArguments; i++) {
184            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
185            result = Interval.Divide(result, argumentInterval);
186          }
187
188          break;
189        }
190        //Trigonometric functions
191        case OpCodes.Sin: {
192          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
193          result = Interval.Sine(argumentInterval);
194          break;
195        }
196        case OpCodes.Cos: {
197          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
198          result = Interval.Cosine(argumentInterval);
199          break;
200        }
201        case OpCodes.Tan: {
202          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
203          result = Interval.Tangens(argumentInterval);
204          break;
205        }
206        case OpCodes.Tanh: {
207          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
208          result = Interval.HyperbolicTangent(argumentInterval);
209          break;
210        }
211        //Exponential functions
212        case OpCodes.Log: {
213          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
214          result = Interval.Logarithm(argumentInterval);
215          break;
216        }
217        case OpCodes.Exp: {
218          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
219          result = Interval.Exponential(argumentInterval);
220          break;
221        }
222        case OpCodes.Square: {
223          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
224          result = Interval.Square(argumentInterval);
225          break;
226        }
227        case OpCodes.SquareRoot: {
228          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
229          result = Interval.SquareRoot(argumentInterval);
230          break;
231        }
232        case OpCodes.Cube: {
233          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
234          result = Interval.Cube(argumentInterval);
235          break;
236        }
237        case OpCodes.CubeRoot: {
238          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
239          result = Interval.CubicRoot(argumentInterval);
240          break;
241        }
242        case OpCodes.Absolute: {
243          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
244          result = Interval.Absolute(argumentInterval);
245          break;
246        }
247        case OpCodes.AnalyticQuotient: {
248          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
249          for (var i = 1; i < currentInstr.nArguments; i++) {
250            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
251            result = Interval.AnalyticalQuotient(result, argumentInterval);
252          }
253
254          break;
255        }
256        default:
257          throw new NotSupportedException(
258            $"The tree contains the unknown symbol {currentInstr.dynamicNode.Symbol}");
259      }
260
261      if (!(nodeIntervals == null || nodeIntervals.ContainsKey(currentInstr.dynamicNode)))
262        nodeIntervals.Add(currentInstr.dynamicNode, result);
263
264      return result;
265    }
266
267    #endregion
268
269    #region Helpers
270
271    private static IDictionary<string, Interval> GetOccurringVariableRanges(
272      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
273      var variables = tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(v => v.VariableName).Distinct()
274                          .ToList();
275
276      return variables.ToDictionary(x => x, x => variableRanges.GetReadonlyDictionary()[x]);
277    }
278
279    private static bool ContainsVariableMultipleTimes(ISymbolicExpressionTree tree, out List<String> variables) {
280      variables = new List<string>();
281      var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
282      foreach (var group in varlist) {
283        if (group.Count() > 1) {
284          variables.Add(group.Key);
285        }
286      }
287
288      return varlist.Any(group => group.Count() > 1);
289    }
290
291    // a multi-dimensional box with an associated bound
292    // boxbounds are ordered first by bound (smaller first), then by size of box (larger first) then by distance of bottom left corner to origin
293    private class BoxBound : IComparable<BoxBound> {
294      public List<Interval> box;
295      public double bound;
296
297      public BoxBound(IEnumerable<Interval> box, double bound) {
298        this.box = new List<Interval>(box);
299        this.bound = bound;
300      }
301
302      public int CompareTo(BoxBound other) {
303        if (bound != other.bound) return bound.CompareTo(other.bound);
304
305        var thisSize = box.Aggregate(1.0, (current, dimExtent) => current * dimExtent.Width);
306        var otherSize = other.box.Aggregate(1.0, (current, dimExtent) => current * dimExtent.Width);
307        if (thisSize != otherSize) return -thisSize.CompareTo(otherSize);
308
309        var thisDist = box.Sum(dimExtent => dimExtent.LowerBound * dimExtent.LowerBound);
310        var otherDist = other.box.Sum(dimExtent => dimExtent.LowerBound * dimExtent.LowerBound);
311        if (thisDist != otherDist) return thisDist.CompareTo(otherDist);
312
313        // which is smaller first along the dimensions?
314        for (int i = 0; i < box.Count; i++) {
315          if (box[i].LowerBound != other.box[i].LowerBound) return box[i].LowerBound.CompareTo(other.box[i].LowerBound);
316        }
317
318        return 0;
319      }
320    }
321
322    #endregion
323
324    #region Splitting
325
326    public static Interval EvaluateWithSplitting(Instruction[] instructions,
327                                                 IDictionary<string, Interval> variableIntervals,
328                                                 List<string> multipleOccurenceVariables, int splittingIterations,
329                                                 double splittingWidth,
330                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals =
331                                                   null) {
332      var min = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
333        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
334        minimization: true);
335      var max = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
336        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
337        minimization: false);
338
339      return new Interval(min, max);
340    }
341
342    private static double FindBound(Instruction[] instructions,
343                                    IDictionary<string, Interval> variableIntervals,
344                                    List<string> multipleOccurenceVariables, int splittingIterations,
345                                    double splittingWidth,
346                                    IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
347                                    bool minimization = true, bool stopAtLimit = false, double limit = 0) {
348      SortedSet<BoxBound> prioQ = new SortedSet<BoxBound>();
349      var ic = 0;
350      var stop = false;
351      //Calculate full box
352      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals: variableIntervals);
353      // the order of keys in a dictionary is guaranteed to be the same order as values in a dictionary
354      // https://docs.microsoft.com/en-us/dotnet/api/system.collections.idictionary.keys?view=netcore-3.1#remarks
355      //var box = variableIntervals.Values;
356      //Box only contains intervals from multiple occurence variables
357      var box = multipleOccurenceVariables.Select(k => variableIntervals[k]);
358      if (minimization) {
359        prioQ.Add(new BoxBound(box, interval.LowerBound));
360        if (stopAtLimit && interval.LowerBound >= limit) stop = true;
361      } else {
362        prioQ.Add(new BoxBound(box, -interval.UpperBound));
363        if (stopAtLimit && interval.UpperBound <= limit) stop = true;
364      }
365
366      var discardedBound = double.MaxValue;
367      var runningBound = double.MaxValue;
368      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0 && !stop; ++depth) {
369        var currentBound = prioQ.Min;
370        prioQ.Remove(currentBound);
371
372        if (currentBound.box.All(x => x.Width < splittingWidth)) {
373          discardedBound = Math.Min(discardedBound, currentBound.bound);
374          continue;
375        }
376
377        var newBoxes = Split(currentBound.box, splittingWidth);
378
379        var innerBound = double.MaxValue;
380        foreach (var newBox in newBoxes) {
381          //var intervalEnum = newBox.GetEnumerator();
382          //var keyEnum = readonlyRanges.Keys.GetEnumerator();
383          //while (intervalEnum.MoveNext() & keyEnum.MoveNext()) {
384          //  variableIntervals[keyEnum.Current] = intervalEnum.Current;
385          //}
386          //Set the splitted variables
387          var intervalEnum = newBox.GetEnumerator();
388          foreach (var key in multipleOccurenceVariables) {
389            intervalEnum.MoveNext();
390            variableIntervals[key] = intervalEnum.Current;
391          }
392
393          ic = 0;
394          var res = Evaluate(instructions, ref ic, nodeIntervals,
395            new ReadOnlyDictionary<string, Interval>(variableIntervals));
396
397          var boxBound = new BoxBound(newBox, minimization ? res.LowerBound : -res.UpperBound);
398          prioQ.Add(boxBound);
399          innerBound = Math.Min(innerBound, boxBound.bound);
400        }
401
402        runningBound = innerBound;
403
404        if (minimization) {
405          if (stopAtLimit && innerBound >= limit)
406            stop = true;
407        } else {
408          if (stopAtLimit && innerBound <= limit)
409            stop = true;
410        }
411      }
412
413      var bound = Math.Min(runningBound, discardedBound);
414      if (bound == double.MaxValue)
415        return minimization ? interval.LowerBound : interval.UpperBound;
416
417      return minimization ? bound : -bound;
418      //return minimization ? prioQ.First().bound : -prioQ.First().bound;
419    }
420
421    private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box) {
422      var boxes = box.Select(region => region.Split())
423                     .Select(split => new List<Interval> {split.Item1, split.Item2})
424                     .ToList();
425
426      return boxes.CartesianProduct();
427    }
428
429    private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box, double minWidth) {
430      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval> {t.Item1, t.Item2};
431      var boxes = box.Select(region => region.Width > minWidth ? toList(region.Split()) : new List<Interval> {region})
432                     .ToList();
433
434      return boxes.CartesianProduct();
435    }
436
437    #endregion
438
439    public Interval GetModelBound(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
440      lock (syncRoot) {
441        EvaluatedSolutions++;
442      }
443
444      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
445      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
446      Interval resultInterval;
447      if (!UseIntervalSplitting) {
448        var instructionCounter = 0;
449        resultInterval = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
450      } else {
451        var vars = ContainsVariableMultipleTimes(tree, out var variables);
452        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations,
453          SplittingWidth);
454      }
455
456      // because of numerical errors the bounds might be incorrect
457      if (resultInterval.IsInfiniteOrUndefined || resultInterval.LowerBound <= resultInterval.UpperBound)
458        return resultInterval;
459
460      return new Interval(resultInterval.UpperBound, resultInterval.LowerBound);
461    }
462
463    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(
464      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
465      throw new NotImplementedException();
466    }
467
468    public double CheckConstraint(
469      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint) {
470      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
471      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
472      if (!UseIntervalSplitting) {
473        var instructionCounter = 0;
474        var modelBound = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
475        if (constraint.Interval.Contains(modelBound)) return 0.0;
476        return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
477               Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
478      }
479
480      if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
481          double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
482        return 0.0;
483      }
484
485      ContainsVariableMultipleTimes(tree, out var variables);
486
487      var upperBound = 0.0;
488      var lowerBound = 0.0;
489      if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
490        upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
491          minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
492
493        return upperBound <= constraint.Interval.UpperBound
494          ? 0.0
495          : Math.Abs(upperBound - constraint.Interval.UpperBound);
496      }
497
498      if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
499        lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
500          minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
501
502        return lowerBound <= constraint.Interval.LowerBound
503          ? 0.0
504          : Math.Abs(lowerBound - constraint.Interval.LowerBound);
505      }
506
507      upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
508        minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
509      lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
510        minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
511
512
513      var res = 0.0;
514
515      res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
516      res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
517
518      return res;
519    }
520
521
522    public bool IsCompatible(ISymbolicExpressionTree tree) {
523      var containsUnknownSymbols = (
524        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
525        where
526          !(n.Symbol is Variable) &&
527          !(n.Symbol is Constant) &&
528          !(n.Symbol is StartSymbol) &&
529          !(n.Symbol is Addition) &&
530          !(n.Symbol is Subtraction) &&
531          !(n.Symbol is Multiplication) &&
532          !(n.Symbol is Division) &&
533          !(n.Symbol is Sine) &&
534          !(n.Symbol is Cosine) &&
535          !(n.Symbol is Tangent) &&
536          !(n.Symbol is HyperbolicTangent) &&
537          !(n.Symbol is Logarithm) &&
538          !(n.Symbol is Exponential) &&
539          !(n.Symbol is Square) &&
540          !(n.Symbol is SquareRoot) &&
541          !(n.Symbol is Cube) &&
542          !(n.Symbol is CubeRoot) &&
543          !(n.Symbol is Absolute) &&
544          !(n.Symbol is AnalyticQuotient)
545        select n).Any();
546      return !containsUnknownSymbols;
547    }
548  }
549}
Note: See TracBrowser for help on using the repository browser.