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

Last change on this file since 16575 was 16575, checked in by gkronber, 3 years ago

#2520: changed HeuristicLab.BioBoost addon to compile with new HL.Persistence

File size: 8.0 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    public struct Key : IComparable<Key> {
38      public Key(int id, int degree) {
39        Id = id;
40        Degree = degree;
41      }
42      public int Id;
43      public int Degree;
44
45      public int CompareTo(Key other) {
46        return Id.CompareTo(other.Id) == 0 ? Degree.CompareTo(other.Degree) : Id.CompareTo(other.Id);
47      }
48
49      public override string ToString() {
50        return string.Format("{0}[{1}]", Id, Degree);
51      }
52    }
53
54    [Storable]
55    private Dictionary<Key, HashSet<int>> table;
56
57    [Storable]
58    private Dictionary<int, HashSet<int>> degrees;
59
60    [Storable]
61    private int maxNNeighborsByDegree;
62
63    #region Construction & Cloning
64    [StorableConstructor]
65    protected NeighborhoodTable(StorableConstructorFlag _) : base(_) { }
66    protected NeighborhoodTable(NeighborhoodTable orig, Cloner cloner) : base(orig, cloner) {
67      table = orig.table.ToDictionary(p => p.Key, p => p.Value);
68      degrees = orig.degrees.ToDictionary(p => p.Key, p => p.Value);
69      maxNNeighborsByDegree = orig.maxNNeighborsByDegree;
70    }
71    public NeighborhoodTable() {
72      table = new Dictionary<Key, HashSet<int>>();
73      degrees = new Dictionary<int, HashSet<int>>();
74      maxNNeighborsByDegree = 0;
75    }
76    public override IDeepCloneable Clone(Cloner cloner) {
77      return new NeighborhoodTable(this, cloner);
78    }
79    #endregion
80
81    public void AddEntry(int id1, int id2, int degree) {
82      var key = new Key(id1, degree);
83      HashSet<int> forwardSet;
84      if (table.TryGetValue(key, out forwardSet)) {
85        forwardSet.Add(id2);
86        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, forwardSet.Count);
87      } else {
88        table[key] = new HashSet<int> {id2};
89        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, 1);
90      }
91      HashSet<int> deg;
92      if (degrees.TryGetValue(id1, out deg)) {
93        deg.Add(degree);
94      } else {
95        degrees[id1] = new HashSet<int> {degree};
96      }
97    }
98
99    public HashSet<int> GetNeighbors(int id, int degree) {
100      return table[new Key(id, degree)];
101    }
102
103    public Dictionary<int, HashSet<int>>  GetNeighbors(int id) {
104      return degrees[id].ToDictionary(deg => deg, deg => table[new Key(id, deg)]);
105    }
106
107    public HashSet<int>[] GetNeighborsFlat(int id) {
108      HashSet<int> neighborDegrees;
109      if (degrees.TryGetValue(id, out neighborDegrees))
110        return neighborDegrees.OrderBy(d => d).Select(d => table[new Key(id, d)]).ToArray();
111      return new HashSet<int>[0];
112    }
113
114    private double Sqr(double x) { return x*x; }
115
116    public int GetRandomNeighbor(int id, IRandom random, int maxId) {
117      var neighbors = GetNeighborsFlat(id);
118      if (neighbors.Length == 0) return id;
119      var classIndex = (int) Math.Round(Sqr(random.NextDouble())*(neighbors.Length));
120      if (classIndex >= neighbors.Length)
121        return random.Next(maxId);
122      var clazz = neighbors[classIndex];
123      return clazz.ElementAt(random.Next(clazz.Count));
124    }
125
126    public void Check() {
127      var errors = new List<string>();
128      foreach (var key in table.Keys) {
129        foreach (var neighbor in table[key]) {
130          HashSet<int> reverseNeighbors;
131          if (table.TryGetValue(new Key(neighbor, key.Degree), out reverseNeighbors))
132            if (reverseNeighbors.Contains(key.Id))
133              continue;
134          errors.Add(string.Format("Reverse relationship of {0}->{1} at degree {2} not found",
135            key.Id, neighbor, key.Degree));
136        }
137      }
138      var uniqueNeighbors = new Dictionary<int, HashSet<int>>();
139      foreach (var key in table.Keys) {
140        HashSet<int> neighbors;
141        if (!uniqueNeighbors.TryGetValue(key.Id, out neighbors)) {
142          neighbors = new HashSet<int>();
143        }
144        foreach (var neighbor in table[key]) {
145          if (neighbors.Contains(neighbor))
146            errors.Add(string.Format("Duplicate neighbor {0} of {1} with multiple degrees", neighbor, key.Id));
147        }
148      }
149      if (errors.Count > 0)
150        throw new Exception(string.Format("NeighborhoodTable Check Failed:\n{0}", string.Join("\n", errors)));
151    }
152
153    #region Implementation of IStringConvertibleMatrix
154
155    public bool Validate(string value, out string errorMessage) {
156      throw new NotImplementedException();
157    }
158
159    public string GetValue(int rowIndex, int columnIndex) {
160      return table.OrderBy(p => p.Key).ElementAt(rowIndex).Value.ElementAt(columnIndex).ToString(CultureInfo.InvariantCulture);
161    }
162
163    public bool SetValue(string value, int rowIndex, int columnIndex) {
164      throw new NotImplementedException();
165    }
166
167    public int Rows { get { return table.Count; } set { throw new NotImplementedException(); } }
168    public int Columns { get { return 2+maxNNeighborsByDegree; } set { throw new NotImplementedException(); } }
169
170    public IEnumerable<string> ColumnNames {
171      get {
172        return new[] {"ID", "Degree"}.Concat(
173          Enumerable.Range(0, maxNNeighborsByDegree).Select(n => string.Format("Neighbor {0}", n)));
174      }
175      set { throw new NotImplementedException(); }
176    }
177    public IEnumerable<string> RowNames {
178      get { return Enumerable.Range(0, Rows).Select(i => i.ToString(CultureInfo.InvariantCulture)); }
179      set { throw new NotImplementedException(); }
180    }
181
182    public bool SortableView { get { return false; } set { throw new NotImplementedException(); } }
183    public bool ReadOnly { get { return true; } }
184
185    public event EventHandler ColumnsChanged;
186    public event EventHandler RowsChanged;
187    public event EventHandler ColumnNamesChanged;
188    public event EventHandler RowNamesChanged;
189    public event EventHandler SortableViewChanged;
190    public event EventHandler<EventArgs<int, int>> ItemChanged;
191    public event EventHandler Reset;
192
193    #endregion
194
195    public NeighborhoodTable CopyAndRemoveIndices(IEnumerable<int> removedIndices) {
196      if (table.Count == 0)
197        return new NeighborhoodTable();
198      var removedIndexSet = new HashSet<int>(removedIndices);
199      int i = 0;
200      var mapping = Enumerable
201        .Range(0, table.Keys.Select(k => k.Id).Max() + 1)
202        .ToDictionary(
203          oldIdx => oldIdx,
204          oldIdx => {
205            if (removedIndexSet.Contains(oldIdx)) return -1;
206            return i++;
207          });
208      var newTable = new NeighborhoodTable();
209      foreach (var entry in table.Keys) {
210        foreach (var neighbor in table[entry]) {
211          var newSource = mapping[entry.Id];
212          var newTarget = mapping[neighbor];
213          if (newSource != -1 && newTarget != -1) {
214            newTable.AddEntry(newSource, newTarget, entry.Degree);
215          }
216        }
217      }
218      newTable.Check();
219      return newTable;
220    }
221  }
222}
Note: See TracBrowser for help on using the repository browser.