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

#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 <http://www.gnu.org/licenses/>.
 */
#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<Key> {
      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<Key, HashSet<int>> table;

    [Storable]
    private Dictionary<int, HashSet<int>> 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<Key, HashSet<int>>();
      degrees = new Dictionary<int, HashSet<int>>();
      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<int> forwardSet;
      if (table.TryGetValue(key, out forwardSet)) {
        forwardSet.Add(id2);
        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, forwardSet.Count);
      } else {
        table[key] = new HashSet<int> {id2};
        maxNNeighborsByDegree = Math.Max(maxNNeighborsByDegree, 1);
      }
      HashSet<int> deg;
      if (degrees.TryGetValue(id1, out deg)) {
        deg.Add(degree);
      } else {
        degrees[id1] = new HashSet<int> {degree};
      }
    }

    public HashSet<int> GetNeighbors(int id, int degree) {
      return table[new Key(id, degree)];
    }

    public Dictionary<int, HashSet<int>>  GetNeighbors(int id) {
      return degrees[id].ToDictionary(deg => deg, deg => table[new Key(id, deg)]);
    }

    public HashSet<int>[] GetNeighborsFlat(int id) {
      HashSet<int> neighborDegrees;
      if (degrees.TryGetValue(id, out neighborDegrees))
        return neighborDegrees.OrderBy(d => d).Select(d => table[new Key(id, d)]).ToArray();
      return new HashSet<int>[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<string>();
      foreach (var key in table.Keys) {
        foreach (var neighbor in table[key]) {
          HashSet<int> 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<int, HashSet<int>>();
      foreach (var key in table.Keys) {
        HashSet<int> neighbors;
        if (!uniqueNeighbors.TryGetValue(key.Id, out neighbors)) {
          neighbors = new HashSet<int>();
        }
        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<string> ColumnNames {
      get {
        return new[] {"ID", "Degree"}.Concat(
          Enumerable.Range(0, maxNNeighborsByDegree).Select(n => string.Format("Neighbor {0}", n)));
      }
      set { throw new NotImplementedException(); }
    }
    public IEnumerable<string> 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<EventArgs<int, int>> ItemChanged;
    public event EventHandler Reset;

    #endregion

    public NeighborhoodTable CopyAndRemoveIndices(IEnumerable<int> removedIndices) {
      if (table.Count == 0)
        return new NeighborhoodTable();
      var removedIndexSet = new HashSet<int>(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;
    }
  }
}