source: addons/HeuristicLab.Problems.BioBoost/HeuristicLab.Problems.BioBoost/3.3/ProblemDescription/NeighborhoodTable.cs @ 17777

Last change on this file since 17777 was 17777, checked in by epitzer, 13 months ago

#3086 add transformers for GeometryFeatureProvider and IGeometry

File size: 8.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using System;
27using System.Collections.Generic;
28using System.Globalization;
29using System.Linq;
30using HEAL.Attic;
31
32namespace HeuristicLab.BioBoost.ProblemDescription {
33 
34  [StorableType("F7026CD3-DA57-4AEE-8AB7-F93BDFCE3CDE")]
35  public class NeighborhoodTable : Item, IStringConvertibleMatrix {
36
37    [StorableType("5830CD54-E24F-4194-AED0-95EB5C14C7F8")]
38    public struct Key : IComparable<Key> {
39      public Key(int id, int degree) {
40        Id = id;
41        Degree = degree;
42      }
43      public int Id;
44      public int Degree;
45
46      public int CompareTo(Key other) {
47        return Id.CompareTo(other.Id) == 0 ? Degree.CompareTo(other.Degree) : Id.CompareTo(other.Id);
48      }
49
50      public override string ToString() {
51        return string.Format("{0}[{1}]", Id, Degree);
52      }
53    }
54
55    [Storable]
56    private Dictionary<Key, HashSet<int>> table;
57
58    [Storable]
59    private Dictionary<int, HashSet<int>> degrees;
60
61    [Storable]
62    private int maxNNeighborsByDegree;
63
64    #region Construction & Cloning
65    [StorableConstructor]
66    protected NeighborhoodTable(StorableConstructorFlag _) : base(_) { }
67    protected NeighborhoodTable(NeighborhoodTable orig, Cloner cloner) : base(orig, cloner) {
68      table = orig.table.ToDictionary(p => p.Key, p => p.Value);
69      degrees = orig.degrees.ToDictionary(p => p.Key, p => p.Value);
70      maxNNeighborsByDegree = orig.maxNNeighborsByDegree;
71    }
72    public NeighborhoodTable() {
73      table = new Dictionary<Key, HashSet<int>>();
74      degrees = new Dictionary<int, HashSet<int>>();
75      maxNNeighborsByDegree = 0;
76    }
77    public override IDeepCloneable Clone(Cloner cloner) {
78      return new NeighborhoodTable(this, cloner);
79    }
80    #endregion
81
82    public void AddEntry(int id1, int id2, int degree) {
83      var key = new Key(id1, degree);
84      HashSet<int> forwardSet;
85      if (table.TryGetValue(key, out forwardSet)) {
86        forwardSet.Add(id2);
87        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, forwardSet.Count);
88      } else {
89        table[key] = new HashSet<int> {id2};
90        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, 1);
91      }
92      HashSet<int> deg;
93      if (degrees.TryGetValue(id1, out deg)) {
94        deg.Add(degree);
95      } else {
96        degrees[id1] = new HashSet<int> {degree};
97      }
98    }
99
100    public HashSet<int> GetNeighbors(int id, int degree) {
101      return table[new Key(id, degree)];
102    }
103
104    public Dictionary<int, HashSet<int>>  GetNeighbors(int id) {
105      return degrees[id].ToDictionary(deg => deg, deg => table[new Key(id, deg)]);
106    }
107
108    public HashSet<int>[] GetNeighborsFlat(int id) {
109      HashSet<int> neighborDegrees;
110      if (degrees.TryGetValue(id, out neighborDegrees))
111        return neighborDegrees.OrderBy(d => d).Select(d => table[new Key(id, d)]).ToArray();
112      return new HashSet<int>[0];
113    }
114
115    private double Sqr(double x) { return x*x; }
116
117    public int GetRandomNeighbor(int id, IRandom random, int maxId) {
118      var neighbors = GetNeighborsFlat(id);
119      if (neighbors.Length == 0) return id;
120      var classIndex = (int) Math.Round(Sqr(random.NextDouble())*(neighbors.Length));
121      if (classIndex >= neighbors.Length)
122        return random.Next(maxId);
123      var clazz = neighbors[classIndex];
124      return clazz.ElementAt(random.Next(clazz.Count));
125    }
126
127    public void Check() {
128      var errors = new List<string>();
129      foreach (var key in table.Keys) {
130        foreach (var neighbor in table[key]) {
131          HashSet<int> reverseNeighbors;
132          if (table.TryGetValue(new Key(neighbor, key.Degree), out reverseNeighbors))
133            if (reverseNeighbors.Contains(key.Id))
134              continue;
135          errors.Add(string.Format("Reverse relationship of {0}->{1} at degree {2} not found",
136            key.Id, neighbor, key.Degree));
137        }
138      }
139      var uniqueNeighbors = new Dictionary<int, HashSet<int>>();
140      foreach (var key in table.Keys) {
141        HashSet<int> neighbors;
142        if (!uniqueNeighbors.TryGetValue(key.Id, out neighbors)) {
143          neighbors = new HashSet<int>();
144        }
145        foreach (var neighbor in table[key]) {
146          if (neighbors.Contains(neighbor))
147            errors.Add(string.Format("Duplicate neighbor {0} of {1} with multiple degrees", neighbor, key.Id));
148        }
149      }
150      if (errors.Count > 0)
151        throw new Exception(string.Format("NeighborhoodTable Check Failed:\n{0}", string.Join("\n", errors)));
152    }
153
154    #region Implementation of IStringConvertibleMatrix
155
156    public bool Validate(string value, out string errorMessage) {
157      throw new NotImplementedException();
158    }
159
160    public string GetValue(int rowIndex, int columnIndex) {
161      return table.OrderBy(p => p.Key).ElementAt(rowIndex).Value.ElementAt(columnIndex).ToString(CultureInfo.InvariantCulture);
162    }
163
164    public bool SetValue(string value, int rowIndex, int columnIndex) {
165      throw new NotImplementedException();
166    }
167
168    public int Rows { get { return table.Count; } set { throw new NotImplementedException(); } }
169    public int Columns { get { return 2+maxNNeighborsByDegree; } set { throw new NotImplementedException(); } }
170
171    public IEnumerable<string> ColumnNames {
172      get {
173        return new[] {"ID", "Degree"}.Concat(
174          Enumerable.Range(0, maxNNeighborsByDegree).Select(n => string.Format("Neighbor {0}", n)));
175      }
176      set { throw new NotImplementedException(); }
177    }
178    public IEnumerable<string> RowNames {
179      get { return Enumerable.Range(0, Rows).Select(i => i.ToString(CultureInfo.InvariantCulture)); }
180      set { throw new NotImplementedException(); }
181    }
182
183    public bool SortableView { get { return false; } set { throw new NotImplementedException(); } }
184    public bool ReadOnly { get { return true; } }
185
186    public event EventHandler ColumnsChanged;
187    public event EventHandler RowsChanged;
188    public event EventHandler ColumnNamesChanged;
189    public event EventHandler RowNamesChanged;
190    public event EventHandler SortableViewChanged;
191    public event EventHandler<EventArgs<int, int>> ItemChanged;
192    public event EventHandler Reset;
193
194    #endregion
195
196    public NeighborhoodTable CopyAndRemoveIndices(IEnumerable<int> removedIndices) {
197      if (table.Count == 0)
198        return new NeighborhoodTable();
199      var removedIndexSet = new HashSet<int>(removedIndices);
200      int i = 0;
201      var mapping = Enumerable
202        .Range(0, table.Keys.Select(k => k.Id).Max() + 1)
203        .ToDictionary(
204          oldIdx => oldIdx,
205          oldIdx => {
206            if (removedIndexSet.Contains(oldIdx)) return -1;
207            return i++;
208          });
209      var newTable = new NeighborhoodTable();
210      foreach (var entry in table.Keys) {
211        foreach (var neighbor in table[entry]) {
212          var newSource = mapping[entry.Id];
213          var newTarget = mapping[neighbor];
214          if (newSource != -1 && newTarget != -1) {
215            newTable.AddEntry(newSource, newTarget, entry.Degree);
216          }
217        }
218      }
219      newTable.Check();
220      return newTable;
221    }
222  }
223}
Note: See TracBrowser for help on using the repository browser.