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

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

#2499: imported source code for HeuristicLab.BioBoost from private repository with some changes

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