#region License Information /* HeuristicLab * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using System; using System.Collections.Generic; using System.Globalization; using System.Linq; namespace HeuristicLab.BioBoost.ProblemDescription { [StorableClass] public class NeighborhoodTable : Item, IStringConvertibleMatrix { public struct Key : IComparable { public Key(int id, int degree) { Id = id; Degree = degree; } public int Id; public int Degree; public int CompareTo(Key other) { return Id.CompareTo(other.Id) == 0 ? Degree.CompareTo(other.Degree) : Id.CompareTo(other.Id); } public override string ToString() { return string.Format("{0}[{1}]", Id, Degree); } } [Storable] private Dictionary> table; [Storable] private Dictionary> degrees; [Storable] private int maxNNeighborsByDegree; #region Construction & Cloning [StorableConstructor] protected NeighborhoodTable(bool isDeserializing) : base(isDeserializing) {} protected NeighborhoodTable(NeighborhoodTable orig, Cloner cloner) : base(orig, cloner) { table = orig.table.ToDictionary(p => p.Key, p => p.Value); degrees = orig.degrees.ToDictionary(p => p.Key, p => p.Value); maxNNeighborsByDegree = orig.maxNNeighborsByDegree; } public NeighborhoodTable() { table = new Dictionary>(); degrees = new Dictionary>(); maxNNeighborsByDegree = 0; } public override IDeepCloneable Clone(Cloner cloner) { return new NeighborhoodTable(this, cloner); } #endregion public void AddEntry(int id1, int id2, int degree) { var key = new Key(id1, degree); HashSet forwardSet; if (table.TryGetValue(key, out forwardSet)) { forwardSet.Add(id2); maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, forwardSet.Count); } else { table[key] = new HashSet {id2}; maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, 1); } HashSet deg; if (degrees.TryGetValue(id1, out deg)) { deg.Add(degree); } else { degrees[id1] = new HashSet {degree}; } } public HashSet GetNeighbors(int id, int degree) { return table[new Key(id, degree)]; } public Dictionary> GetNeighbors(int id) { return degrees[id].ToDictionary(deg => deg, deg => table[new Key(id, deg)]); } public HashSet[] GetNeighborsFlat(int id) { HashSet neighborDegrees; if (degrees.TryGetValue(id, out neighborDegrees)) return neighborDegrees.OrderBy(d => d).Select(d => table[new Key(id, d)]).ToArray(); return new HashSet[0]; } private double Sqr(double x) { return x*x; } public int GetRandomNeighbor(int id, IRandom random, int maxId) { var neighbors = GetNeighborsFlat(id); if (neighbors.Length == 0) return id; var classIndex = (int) Math.Round(Sqr(random.NextDouble())*(neighbors.Length)); if (classIndex >= neighbors.Length) return random.Next(maxId); var clazz = neighbors[classIndex]; return clazz.ElementAt(random.Next(clazz.Count)); } public void Check() { var errors = new List(); foreach (var key in table.Keys) { foreach (var neighbor in table[key]) { HashSet reverseNeighbors; if (table.TryGetValue(new Key(neighbor, key.Degree), out reverseNeighbors)) if (reverseNeighbors.Contains(key.Id)) continue; errors.Add(string.Format("Reverse relationship of {0}->{1} at degree {2} not found", key.Id, neighbor, key.Degree)); } } var uniqueNeighbors = new Dictionary>(); foreach (var key in table.Keys) { HashSet neighbors; if (!uniqueNeighbors.TryGetValue(key.Id, out neighbors)) { neighbors = new HashSet(); } foreach (var neighbor in table[key]) { if (neighbors.Contains(neighbor)) errors.Add(string.Format("Duplicate neighbor {0} of {1} with multiple degrees", neighbor, key.Id)); } } if (errors.Count > 0) throw new Exception(string.Format("NeighborhoodTable Check Failed:\n{0}", string.Join("\n", errors))); } #region Implementation of IStringConvertibleMatrix public bool Validate(string value, out string errorMessage) { throw new NotImplementedException(); } public string GetValue(int rowIndex, int columnIndex) { return table.OrderBy(p => p.Key).ElementAt(rowIndex).Value.ElementAt(columnIndex).ToString(CultureInfo.InvariantCulture); } public bool SetValue(string value, int rowIndex, int columnIndex) { throw new NotImplementedException(); } public int Rows { get { return table.Count; } set { throw new NotImplementedException(); } } public int Columns { get { return 2+maxNNeighborsByDegree; } set { throw new NotImplementedException(); } } public IEnumerable ColumnNames { get { return new[] {"ID", "Degree"}.Concat( Enumerable.Range(0, maxNNeighborsByDegree).Select(n => string.Format("Neighbor {0}", n))); } set { throw new NotImplementedException(); } } public IEnumerable RowNames { get { return Enumerable.Range(0, Rows).Select(i => i.ToString(CultureInfo.InvariantCulture)); } set { throw new NotImplementedException(); } } public bool SortableView { get { return false; } set { throw new NotImplementedException(); } } public bool ReadOnly { get { return true; } } public event EventHandler ColumnsChanged; public event EventHandler RowsChanged; public event EventHandler ColumnNamesChanged; public event EventHandler RowNamesChanged; public event EventHandler SortableViewChanged; public event EventHandler> ItemChanged; public event EventHandler Reset; #endregion public NeighborhoodTable CopyAndRemoveIndices(IEnumerable removedIndices) { if (table.Count == 0) return new NeighborhoodTable(); var removedIndexSet = new HashSet(removedIndices); int i = 0; var mapping = Enumerable .Range(0, table.Keys.Select(k => k.Id).Max() + 1) .ToDictionary( oldIdx => oldIdx, oldIdx => { if (removedIndexSet.Contains(oldIdx)) return -1; return i++; }); var newTable = new NeighborhoodTable(); foreach (var entry in table.Keys) { foreach (var neighbor in table[entry]) { var newSource = mapping[entry.Id]; var newTarget = mapping[neighbor]; if (newSource != -1 && newTarget != -1) { newTable.AddEntry(newSource, newTarget, entry.Degree); } } } newTable.Check(); return newTable; } } }