Free cookie consent management tool by TermsFeed Policy Generator

source: branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/UniqueThresholdCalculator.cs @ 12064

Last change on this file since 12064 was 7128, checked in by epitzer, 13 years ago

#1696 Integrate fitness landscape analysis plugins from Heureka! repository.

File size: 5.5 KB
RevLine 
[7128]1using System;
2using System.Linq;
3using System.Collections.Generic;
4using System.Text;
5using System.Diagnostics;
6
7namespace HeuristicLab.Analysis {
8
9  public static class UniqueThresholdCalculator {
10
11    private sealed class IndexRange {
12
13      public int Start, End, N;
14      public readonly bool Merge;
15      private readonly List<IndexRange> receivers, distributors;
16
17      public IndexRange(int start, int end, int n, bool merge) {
18        Start = start;
19        End = end;
20        N = n;
21        Merge = merge;
22        receivers = new List<IndexRange>();
23        distributors = new List<IndexRange>();
24      }
25
26      public void AddReceiver(IndexRange receiver) {
27        if (receiver != null) {
28          receivers.Add(receiver);
29          receiver.distributors.Add(this);
30        }
31      }
32
33      public void Distribute() {
34        int n = N - 1;
35        Debug.Assert(n >= 0);
36        switch (receivers.Count) {
37          case 0: break; // No receivers indexes are lost :-(
38          case 1: receivers[0].N += n; N = 1; break;
39          case 2: receivers[0].N += n / 2; receivers[1].N += n - n / 2; N = 1; break;
40          default: throw new InvalidOperationException("More than two receivers registered");
41        }
42        var followers = distributors.Where(d => d.Start > End).ToList();
43        if (followers.Count > 0)
44          End = followers.Min(g => g.Start);
45        var predecessors = distributors.Where(d => d.End < Start).ToList();
46        if (predecessors.Count > 0)
47          Start = predecessors.Max(g => g.End);
48      }
49
50      public override string ToString() {
51        return string.Format("[{0}-{1}, n={2}, {3}]", Start, End, N, Merge ? "Merge" : "Spread");
52      }
53    }
54
55    public static IEnumerable<double> DetermineThresholds(IEnumerable<double> differences, int n) {
56      var thresholds = differences.Select(d => Math.Abs(d)).ToList();
57      thresholds.Sort();
58      if (thresholds.Count <= n) {
59        foreach (var t in thresholds)
60          yield return t;
61      } else {
62        double min = thresholds[0];
63        double max = thresholds[thresholds.Count-1];
64        if (min == max) {
65          yield return min;
66        } else {
67          yield return min;
68          foreach (var t in DetermineInnerThresholds(thresholds, n-2))
69            yield return t;
70          yield return max;
71        }
72      }
73    }
74
75    private static IEnumerable<double> DetermineInnerThresholds(List<double> thresholds, int n) {
76      n = Math.Min(thresholds.Count - 2, n);
77      var indexes = Enumerable.Range(0, n + 2).Select(i => (int)Math.Round(1.0 * i * (thresholds.Count - 1) / (n + 1))).ToList();
78      var ranges = CreateRanges(thresholds, indexes);
79      RedistributeIndexes(ranges);
80      TrimBoundaryRanges(ranges);
81      if (ranges.Count == 1 && ranges[0].Start == 0 && ranges[0].End == thresholds.Count - 1 && ranges[0].N == n) {
82        if (ranges[0].Merge)
83          yield return thresholds[ranges[0].Start];
84        else
85          foreach (var i in indexes.Where(i => ranges[0].Start < i && i < ranges[0].End))
86            yield return thresholds[i];
87      } else {
88        foreach (var range in ranges) {
89          if (range.Merge)
90            yield return thresholds[range.Start];
91          else
92            foreach (var t in DetermineInnerThresholds(thresholds.GetRange(range.Start, range.End - range.Start + 1), range.N))
93              yield return t;
94        }
95      }
96    }
97
98    private static void TrimBoundaryRanges(List<IndexRange> ranges) {
99      if (ranges.Count > 0)
100        if (ranges[0].Merge)
101          ranges.RemoveAt(0);
102        else
103          ranges[0].N--;
104      if (ranges.Count > 0)
105        if (ranges[ranges.Count - 1].Merge)
106          ranges.RemoveAt(ranges.Count - 1);
107        else
108          ranges[ranges.Count - 1].N--;
109    }
110
111    private static void RedistributeIndexes(List<IndexRange> ranges) {
112      IndexRange lastReceiver = null;
113      List<IndexRange> lastDistributors = new List<IndexRange>();
114      foreach (var range in ranges) {
115        if (range.Merge) {
116          range.AddReceiver(lastReceiver);
117          lastDistributors.Add(range);
118        } else {
119          foreach (var d in lastDistributors)
120            d.AddReceiver(range);
121          lastDistributors = new List<IndexRange>();
122          lastReceiver = range;
123        }
124      }
125      foreach (var range in ranges) {
126        range.Distribute();
127      }
128    }
129
130    private static List<IndexRange> CreateRanges(List<double> thresholds, List<int> indexes) {
131      var values = indexes.Select(i => new { i, v = thresholds[i] }).ToList();
132      var mergedRanges = values.GroupBy(iv => iv.v)
133        .Select(g => g.Count() == 1 ?
134          new IndexRange(g.First().i, g.First().i, 1, false) :
135          new IndexRange(g.Min(iv => iv.i), g.Max(iv => iv.i), g.Count(), true)).ToList();
136      IndexRange lastSpreadRange = null;
137      var ranges = new List<IndexRange>();
138      foreach (var group in mergedRanges) {
139        if (group.Merge) {
140          if (lastSpreadRange != null) {
141            ranges.Add(lastSpreadRange);
142            lastSpreadRange = null;
143          }
144          ranges.Add(group);
145        } else {
146          if (lastSpreadRange != null) {
147            lastSpreadRange.End = group.End;
148            lastSpreadRange.N++;
149          } else {
150            lastSpreadRange = group;
151          }
152        }
153      }
154      if (lastSpreadRange != null)
155        ranges.Add(lastSpreadRange);
156      return ranges;
157    }
158  }
159}
Note: See TracBrowser for help on using the repository browser.