Changeset 15676 for branches/GeneralizedQAP

Timestamp:

01/30/18 15:55:00 (7 years ago)

Author:

abeham

Message:

#1614:

• Refactored RLD view, added additional classes

File:

• branches/GeneralizedQAP/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs (modified) (25 diffs)

branches/GeneralizedQAP/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections;
 using System.Collections.Generic;
 using System.ComponentModel;
@@ -78 +79 @@
     }
 
+    private List<AlgorithmInstance> groups;
+
     private double[] targets;
     private double[] budgets;
@@ -141 +144 @@
       UpdateGroupAndProblemComboBox();
       UpdateDataTableComboBox();
+      GroupRuns();
       foreach (var run in e.Items)
         RegisterRunEvents(run);
@@ -152 +156 @@
       UpdateGroupAndProblemComboBox();
       UpdateDataTableComboBox();
+      GroupRuns();
       foreach (var run in e.Items)
         DeregisterRunEvents(run);
@@ -163 +168 @@
       UpdateGroupAndProblemComboBox();
       UpdateDataTableComboBox();
+      GroupRuns();
       foreach (var run in e.OldItems)
         DeregisterRunEvents(run);
@@ -215 +221 @@
         UpdateGroupAndProblemComboBox();
         UpdateDataTableComboBox();
+        GroupRuns();
       }
     }
@@ -258 +265 @@
         if (p.Key.Equals(selectedProblemItem)) problemComboBox.SelectedItem = p.Key;
       }
+
       SetEnabledStateOfControls();
     }
@@ -288 +296 @@
     }
 
-    private IEnumerable<AlgorithmInstance> GroupRuns() {
+    private void GroupRuns() {
+      groups = new List<AlgorithmInstance>();
+
       var table = (string)dataTableComboBox.SelectedItem;
-      if (string.IsNullOrEmpty(table)) yield break;
+      if (string.IsNullOrEmpty(table)) return;
 
       var selectedGroup = (string)groupComboBox.SelectedItem;
-      if (string.IsNullOrEmpty(selectedGroup)) yield break;
+      if (string.IsNullOrEmpty(selectedGroup)) return;
 
       var selectedProblem = (ProblemInstance)problemComboBox.SelectedItem;
-      if (selectedProblem == null) yield break;
-      
-      foreach (var x in (from r in Content
-                         where (selectedGroup == AllInstances || r.Parameters.ContainsKey(selectedGroup))
-                           && selectedProblem.Match(r)
-                           && r.Results.ContainsKey(table)
-                           && r.Visible
-                         let key = selectedGroup == AllInstances ? AllInstances : r.Parameters[selectedGroup].ToString()
-                         group r by key into g
-                         select new AlgorithmInstance(g.Key, g, problems))) {
-        yield return x;
+      if (selectedProblem == null) return;
+
+      foreach (var alg in from r in Content
+                          where (selectedGroup == AllInstances || r.Parameters.ContainsKey(selectedGroup))
+                            && r.Visible
+                            && selectedProblem.Match(r)
+                            && r.Results.ContainsKey(table)
+                            && r.Results[table] is IndexedDataTable<double>
+                          let key = selectedGroup == AllInstances ? AllInstances : r.Parameters[selectedGroup].ToString()
+                          group r by key into g
+                          select g) {
+        var trials = from run in alg
+                     from pd in problems
+                     where pd.Equals(new ProblemInstance(run))
+                     let cgraph = ((IndexedDataTable<double>)run.Results[table])
+                     group cgraph by pd into g
+                     select g;
+
+        groups.Add(new AlgorithmInstance(alg.Key, trials));
       }
     }
@@ -321 +339 @@
 
       if (targets == null) GenerateDefaultTargets();
-
-      var algInstances = GroupRuns().ToList();
-      if (algInstances.Count == 0) return;
+      
+      if (groups.Count == 0) return;
 
       var xAxisTitles = new HashSet<string>();
@@ -337 +354 @@
       var aggregate = aggregateTargetsCheckBox.Checked;
       double minEff = double.MaxValue, maxEff = double.MinValue;
-      foreach (var alg in algInstances) {
+      foreach (var alg in groups) {
         var noRuns = 0;
         SortedList<double, int> epdfHits = null, epdfMisses = null;
@@ -344 +361 @@
           misses[alg.Name] = epdfMisses = new SortedList<double, int>();
         }
-        foreach (var problem in alg.GetProblemInstances()) {
+        foreach (var problem in alg.GetCases()) {
           var max = problem.IsMaximization();
           var absTargets = GetAbsoluteTargets(problem).ToArray();
-          foreach (var run in alg.GetRuns(problem)) {
+          foreach (var run in alg.GetTrials(problem)) {
             noRuns++;
-            var resultsTable = (IndexedDataTable<double>)run.Results[table];
-            xAxisTitles.Add(resultsTable.VisualProperties.XAxisTitle);
-
-            var efforts = absTargets.Select(t => GetEffortToHitTarget(resultsTable.Rows.First().Values, t, max)).ToArray();
+            xAxisTitles.Add(run.XAxisName);
+
+            var efforts = absTargets.Select(t => GetEffortToHitTarget(run, t, max)).ToArray();
             minEff = Math.Min(minEff, efforts.Min(x => x.Item2));
             maxEff = Math.Max(maxEff, efforts.Max(x => x.Item2));
@@ -391 +407 @@
       targetChart.ChartAreas[0].CursorY.Interval = 0.05;
 
-      UpdateErtTables(algInstances);
+      UpdateErtTables();
     }
 
@@ -582 +598 @@
 
     private Tuple<bool, double> GetEffortToHitTarget(
-        ObservableList<Tuple<double, double>> convergenceGraph,
+        ConvergenceGraph cgraph,
         double absTarget, bool maximization) {
-      if (convergenceGraph.Count == 0)
+      if (cgraph.Points == 0)
         throw new ArgumentException("Convergence graph is empty.", "convergenceGraph");
       
-      var index = convergenceGraph.BinarySearch(Tuple.Create(0.0, absTarget), new TargetComparer(maximization));
+      var index = cgraph.BinarySearch(new ConvergenceGraphPoint(0.0, absTarget), new TargetComparer(maximization));
       if (index >= 0) {
-        return Tuple.Create(true, convergenceGraph[index].Item1);
+        return Tuple.Create(true, cgraph[index].Runlength);
       } else {
         index = ~index;
-        if (index >= convergenceGraph.Count)
-          return Tuple.Create(false, convergenceGraph.Last().Item1);
-        return Tuple.Create(true, convergenceGraph[index].Item1);
-      }
-    }
-
-    private void UpdateErtTables(List<AlgorithmInstance> algorithmInstances) {
+        if (index >= cgraph.Points)
+          return Tuple.Create(false, cgraph.Last().Runlength);
+        return Tuple.Create(true, cgraph[index].Runlength);
+      }
+    }
+
+    private void UpdateErtTables() {
       ertTableView.Content = null;
       var columns = targets.Length + 1;
-      var totalRows = algorithmInstances.Count * algorithmInstances.Max(x => x.GetNumberOfProblemInstances()) + algorithmInstances.Max(x => x.GetNumberOfProblemInstances());
+      var totalRows = groups.Count * groups.Max(x => x.GetNumberOfCases()) + groups.Max(x => x.GetNumberOfCases());
       var matrix = new StringMatrix(totalRows, columns);
       var rowNames = new List<string>();
@@ -611 +627 @@
       if (string.IsNullOrEmpty(tableName)) return;
       
-      var problems = algorithmInstances.SelectMany(x => x.GetProblemInstances()).Distinct().ToList();
+      var problems = groups.SelectMany(x => x.GetCases()).Distinct().ToList();
 
       foreach (var problem in problems) {
+        if (double.IsNaN(problem.BestKnownQuality)) continue;
+        rowNames.Add(problem.ToString());
         var max = problem.IsMaximization();
-        rowNames.Add(problem.ToString());
         var absTargets = GetAbsoluteTargetsWorstToBest(problem);
         if (targetsAreRelative) {
@@ -625 +642 @@
         rowCount++;
 
-        foreach (var alg in algorithmInstances) {
+        foreach (var alg in groups) {
           rowNames.Add(alg.Name);
-          var runs = alg.GetRuns(problem).ToList();
+          var runs = alg.GetTrials(problem).ToList();
           if (runs.Count == 0) {
             matrix[rowCount, columns - 1] = "N/A";
@@ -635 +652 @@
           var result = default(ErtCalculationResult);
           for (var i = 0; i < absTargets.Length; i++) {
-            result = ExpectedRuntimeHelper.CalculateErt(runs, tableName, absTargets[i], max);
+            result = ExpectedRuntimeHelper.CalculateErt(runs.Select(x => x.ToTuples()), absTargets[i], max);
             matrix[rowCount, i] = result.ToString();
           }
@@ -658 +675 @@
 
       if (budgets == null) GenerateDefaultBudgets(table);
-
-      var algInstances = GroupRuns().ToList();
-      if (algInstances.Count == 0) return;
+      
+      if (groups.Count == 0) return;
 
       var colorCount = 0;
       var lineStyleCount = 0;
       
-      foreach (var alg in algInstances) {
+      foreach (var alg in groups) {
         var hits = new Dictionary<string, SortedList<double, double>>();
 
-        foreach (var problem in alg.GetProblemInstances()) {
-          foreach (var run in alg.GetRuns(problem)) {
-            var resultsTable = (IndexedDataTable<double>)run.Results[table];
-
-            CalculateHitsForEachBudget(hits, resultsTable.Rows.First(), problem, alg.Name);
+        foreach (var problem in alg.GetCases()) {
+          foreach (var run in alg.GetTrials(problem)) {
+            CalculateHitsForEachBudget(hits, run, problem, alg.Name);
           }
         }
@@ -715 +729 @@
     }
 
-    private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, IndexedDataRow<double> row, ProblemInstance problem, string groupName) {
+    private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, ConvergenceGraph cgraph, ProblemInstance problem, string groupName) {
       var max = problem.IsMaximization();
       var prevIndex = 0;
       foreach (var b in budgets) {
         var key = groupName + "-" + b;
-        var index = row.Values.BinarySearch(prevIndex, row.Values.Count - prevIndex, Tuple.Create(b, 0.0), new CostComparer());
+        var index = cgraph.BinarySearch(prevIndex, cgraph.Points - prevIndex, new ConvergenceGraphPoint(b, 0.0), new CostComparer());
         if (index < 0) {
           index = ~index;
-          if (index >= row.Values.Count) break; // the run wasn't long enough to use up budget b (or any subsequent larger one)
+          if (index >= cgraph.Points) break; // the run wasn't long enough to use up budget b (or any subsequent larger one)
         }
         if (!hits.ContainsKey(key)) hits.Add(key, new SortedList<double, double>());
-        var v = row.Values[index];
-        var relTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, v.Item2) + 1;
+        var v = cgraph[index];
+        var relTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, v.Quality) + 1;
         if (hits[key].ContainsKey(relTgt))
           hits[key][relTgt]++;
@@ -874 +888 @@
         var pd = new ProblemInstance(run);
         pd = problems.Single(x => x.Equals(pd));
+        if (double.IsNaN(pd.BestKnownQuality)) continue;
+
         var max = pd.IsMaximization();
         var absTargets = GetAbsoluteTargetsWorstToBest(pd);
+        var cgraph = new ConvergenceGraph(resultsTable, max);
 
         var prevIndex = 0;
         for (var i = 0; i < absTargets.Length; i++) {
           var absTarget = absTargets[i];
-          var index = values.BinarySearch(prevIndex, values.Count - prevIndex, Tuple.Create(0.0, absTarget), new TargetComparer(max));
+          var index = cgraph.BinarySearch(prevIndex, values.Count - prevIndex, new ConvergenceGraphPoint(0.0, absTarget), new TargetComparer(max));
           if (index < 0) {
             index = ~index;
@@ -977 +994 @@
         var pd = new ProblemInstance(run);
         pd = problems.Single(x => x.Equals(pd));
-
+        var max = pd.IsMaximization();
+        var cgraph = new ConvergenceGraph(resultsTable, max);
         var prevIndex = 0;
         foreach (var b in budgets) {
-          var index = values.BinarySearch(prevIndex, values.Count - prevIndex, Tuple.Create(b, 0.0), new CostComparer());
+          var index = cgraph.BinarySearch(prevIndex, values.Count - prevIndex, new ConvergenceGraphPoint(b, 0.0), new CostComparer());
           if (index < 0) {
             index = ~index;
@@ -1011 +1029 @@
     private Dictionary<ProblemInstance, double> CalculateBestTargetPerProblemInstance(string table) {
       if (table == null) table = string.Empty;
-      return (from r in Content
-              where r.Visible
-              let pd = new ProblemInstance(r)
-              let target = r.Parameters.ContainsKey("BestKnownQuality")
-                           && r.Parameters["BestKnownQuality"] is DoubleValue
-                           && !double.IsNaN(((DoubleValue)r.Parameters["BestKnownQuality"]).Value)
-                ? ((DoubleValue)r.Parameters["BestKnownQuality"]).Value
-                : (r.Results.ContainsKey(table) && r.Results[table] is IndexedDataTable<double>
-                  ? ((IndexedDataTable<double>)r.Results[table]).Rows.First().Values.Last().Item2
-                  : double.NaN)
-              group target by pd into g
-              select new { Problem = g.Key, Target = g.Any(x => !double.IsNaN(x)) ? (g.Key.IsMaximization() ? g.Max() : g.Where(x => !double.IsNaN(x)).Min()) : double.NaN })
-        .ToDictionary(x => x.Problem, x => x.Target);
+      var dict = new Dictionary<ProblemInstance, double>();
+      foreach (var k in from r in Content where r.Visible let pd = new ProblemInstance(r) group r by pd into g select new { Problem = g.Key, Runs = g.ToList() }) {
+        var pd = new ProblemInstance(k.Runs[0]);
+        var values = GetQualityValues(k.Runs, table).ToList();
+        var target = double.NaN;
+        if (values.Count > 0) {
+          target = pd.IsMaximization() ? values.Max() : values.Min();
+        }
+        dict[pd] = target;
+      }
+      return dict;
+    }
+
+    private IEnumerable<double> GetQualityValues(List<IRun> runs, string table) {
+      foreach (var r in runs) {
+        IItem item;
+        if (r.Parameters.TryGetValue("BestKnownQuality", out item)) {
+          var dval = item as DoubleValue;
+          if (dval != null && !double.IsNaN(dval.Value))
+            yield return dval.Value;
+        }
+        if (r.Results.TryGetValue(table, out item)) {
+          var dt = item as IndexedDataTable<double>;
+          if (dt != null) {
+            var last = dt.Rows.First().Values.Last().Item2;
+            if (!double.IsNaN(last))
+              yield return last;
+          }
+        }
+      }
     }
 
@@ -1033 +1068 @@
       SuspendRepaint();
       try {
+        GroupRuns();
         UpdateResultsByTarget();
         UpdateResultsByCost();
@@ -1148 +1184 @@
       }
 
-      private Dictionary<ProblemInstance, List<IRun>> performanceData;
-
-      public int GetNumberOfProblemInstances() {
+      private Dictionary<ProblemInstance, List<ConvergenceGraph>> performanceData;
+
+      public int GetNumberOfCases() {
         return performanceData.Count;
       }
 
-      public IEnumerable<ProblemInstance> GetProblemInstances() {
+      public IEnumerable<ProblemInstance> GetCases() {
         return performanceData.Keys;
       }
 
-      public int GetNumberOfRuns(ProblemInstance p) {
+      public int GetNumberOfTrials(ProblemInstance p) {
         if (p == ProblemInstance.MatchAll) return performanceData.Select(x => x.Value.Count).Sum();
-        List<IRun> runs;
-        if (performanceData.TryGetValue(p, out runs))
-          return runs.Count;
+        List<ConvergenceGraph> trials;
+        if (performanceData.TryGetValue(p, out trials))
+          return trials.Count;
 
         return 0;
       }
 
-      public IEnumerable<IRun> GetRuns(ProblemInstance p) {
+      public IEnumerable<ConvergenceGraph> GetTrials(ProblemInstance p) {
         if (p == ProblemInstance.MatchAll) return performanceData.SelectMany(x => x.Value);
-        List<IRun> runs;
-        if (performanceData.TryGetValue(p, out runs))
-          return runs;
-
-        return Enumerable.Empty<IRun>();
-      }
-
-      public AlgorithmInstance(string name, IEnumerable<IRun> runs, IEnumerable<ProblemInstance> problems) {
+        List<ConvergenceGraph> trials;
+        if (performanceData.TryGetValue(p, out trials))
+          return trials;
+
+        return Enumerable.Empty<ConvergenceGraph>();
+      }
+
+      public AlgorithmInstance(string name, IEnumerable<IGrouping<ProblemInstance, IndexedDataTable<double>>> trials) {
         this.name = name;
 
-        var pDict = problems.ToDictionary(r => r, _ => new List<IRun>());
-        foreach (var y in runs) {
-          var pd = new ProblemInstance(y);
-          List<IRun> l;
-          if (pDict.TryGetValue(pd, out l)) l.Add(y);
-        }
-        performanceData = pDict.Where(x => x.Value.Count > 0).ToDictionary(x => x.Key, x => x.Value);
+        performanceData = new Dictionary<ProblemInstance, List<ConvergenceGraph>>();
+        foreach (var t in trials) {
+          if (double.IsNaN(t.Key.BestKnownQuality)) continue;
+          var max = t.Key.IsMaximization();
+          performanceData[t.Key] = t.Select(c => new ConvergenceGraph(c, max)).ToList();
+        }
       }
 
@@ -1387 +1422 @@
     }
 
-    private class CostComparer : Comparer<Tuple<double, double>> {
-      public override int Compare(Tuple<double, double> x, Tuple<double, double> y) {
-        return x.Item1.CompareTo(y.Item1);
-      }
-    }
-
-    private class TargetComparer : Comparer<Tuple<double, double>> {
+    private class CostComparer : Comparer<ConvergenceGraphPoint> {
+      public override int Compare(ConvergenceGraphPoint x, ConvergenceGraphPoint y) {
+        return x.Runlength.CompareTo(y.Runlength);
+      }
+    }
+
+    private class TargetComparer : Comparer<ConvergenceGraphPoint> {
       public bool Maximization { get; private set; }
       public TargetComparer(bool maximization) {
@@ -1399 +1434 @@
       }
 
-      public override int Compare(Tuple<double, double> x, Tuple<double, double> y) {
-        return Maximization ? x.Item2.CompareTo(y.Item2) : y.Item2.CompareTo(x.Item2);
+      public override int Compare(ConvergenceGraphPoint x, ConvergenceGraphPoint y) {
+        return Maximization ? x.Quality.CompareTo(y.Quality) : y.Quality.CompareTo(x.Quality);
+      }
+    }
+
+    private class ConvergenceGraph : IEnumerable<ConvergenceGraphPoint> {
+      private List<ConvergenceGraphPoint> data;
+      private bool maximization;
+      private string xAxisLabel;
+
+      public string XAxisName { get { return xAxisLabel; } }
+
+      public int Points {
+        get { return data.Count; }
+      }
+
+      public double TotalRunlength {
+        get { return data.Last().Runlength; }
+      }
+
+      public double BestQuality {
+        get { return data.Last().Quality; }
+      }
+
+      public double QualityAt(double runlength) {
+        var point = data.SkipWhile(x => x.Runlength < runlength).FirstOrDefault();
+        if (point == null) return double.NaN;
+        return point.Quality;
+      }
+
+      public double RunlengthFor(double quality) {
+        var point = (maximization ? data.SkipWhile(x => x.Quality < quality) : data.SkipWhile(x => x.Quality > quality)).FirstOrDefault();
+        if (point == null) return double.NaN;
+        return point.Runlength;
+      }
+
+      public ConvergenceGraphPoint this[int point] {
+        get { return data[point]; }
+      }
+
+      public ConvergenceGraph(IndexedDataTable<double> table, bool maximization) {
+        data = table.Rows.First().Values.Select(x => new ConvergenceGraphPoint() { Runlength = x.Item1, Quality = x.Item2 }).ToList();
+        xAxisLabel = table.VisualProperties.XAxisTitle;
+        this.maximization = maximization;
+      }
+
+      public IEnumerator<ConvergenceGraphPoint> GetEnumerator() {
+        return data.GetEnumerator();
+      }
+
+      IEnumerator IEnumerable.GetEnumerator() {
+        return data.GetEnumerator();
+      }
+
+      public int BinarySearch(ConvergenceGraphPoint item, IComparer<ConvergenceGraphPoint> comparer) {
+        return data.BinarySearch(item, comparer);
+      }
+
+      public int BinarySearch(int index, int count, ConvergenceGraphPoint point, IComparer<ConvergenceGraphPoint> comparer) {
+        return data.BinarySearch(index, count, point, comparer);
+      }
+
+      public IEnumerable<Tuple<double, double>> ToTuples() {
+        return data.Select(x => Tuple.Create(x.Runlength, x.Quality));
+      }
+    }
+
+    private class ConvergenceGraphPoint {
+      public double Runlength { get; set; }
+      public double Quality { get; set; }
+
+      public ConvergenceGraphPoint() {
+
+      }
+      public ConvergenceGraphPoint(double runlength, double quality) {
+        Runlength = runlength;
+        Quality = quality;
       }
     }