#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;
}
}
}