source: branches/HeuristicLab.Problems.BioBoost/HeuristicLab.Problems.BioBoost/3.3/ProblemDescription/NeighborhoodTable.cs @ 13071

Last change on this file since 13071 was 13071, checked in by gkronber, 7 years ago

#2499: added license headers and removed unused usings

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