#region License Information
/* HeuristicLab
* Copyright (C) 2002-2010 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 System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.EvolutionaryTracking {
[Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
public class GenealogyGraph : NamedItem, IGenealogyGraph where T : class {
private readonly Dictionary _dictionary;
public GenealogyGraph() {
_dictionary = new Dictionary();
}
public GenealogyGraph(GenealogyGraph g) {
_dictionary = new Dictionary(g._dictionary);
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GenealogyGraph(this, cloner);
}
public override Image ItemImage {
get { return Common.Resources.VSImageLibrary.Graph; }
}
[StorableConstructor]
protected GenealogyGraph(bool serializing)
: base(serializing) {
}
private GenealogyGraph(GenealogyGraph original, Cloner cloner)
: base(original, cloner) {
_dictionary = new Dictionary(original._dictionary);
}
public bool HasNode(T t) {
return _dictionary.ContainsKey(t);
}
public GenealogyGraphNode GetNode(T t) {
return HasNode(t) ? _dictionary[t] : null;
}
public IEnumerable Keys {
get { return _dictionary.Keys; }
}
public IEnumerable Values {
get { return _dictionary.Values; }
}
public bool IsEmpty {
get { return !_dictionary.Any(); }
}
public bool Any(Func, bool> predicate) {
return _dictionary.Any(predicate);
}
public void Clear() {
_dictionary.Clear();
}
///
/// Adds a node representing an individual
///
/// The symbolic expression tree
/// The quality value
/// The node label
/// The node rank
/// Specifies if this node is an elite
public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false) {
if (HasNode(t)) return;
_dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank };
}
///
/// more of a low level method to minimize memory usage when creating and returning subgraphs
///
/// The node to be added
public void AddNode(GenealogyGraphNode node) {
var t = (T)node.Data;
if (HasNode(t)) return;
_dictionary[t] = node;
}
///
/// Remove a node from the graph along with edges associated with it
///
/// The graph node
public void RemoveNode(T t) {
if (!_dictionary.ContainsKey(t)) return;
var node = _dictionary[t];
if (node.InEdges != null) {
foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
if (!e.Target.OutEdges.Any())
e.Target.OutEdges = null; // set to null to be a little more memory efficient
}
node.InEdges = null;
}
if (node.OutEdges != null) {
foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
e.Target.InEdges.RemoveAll(arc => arc.Target == node);
if (!e.Target.InEdges.Any())
e.Target.InEdges = null; // set to null to be a little more memory efficient
}
node.OutEdges = null;
}
_dictionary.Remove(t);
}
public double AverageDegree {
get { return Values.Average(x => x.Degree); }
}
///
/// Adds a graph arc from a to b
///
///
///
public void AddArc(T a, T b) {
GenealogyGraphNode src, dest;
if (!HasNode(a)) {
src = new GenealogyGraphNode { Data = a };
_dictionary[a] = src;
} else {
src = _dictionary[a];
}
if (!HasNode(b)) {
dest = new GenealogyGraphNode { Data = b };
_dictionary[b] = dest;
} else {
dest = _dictionary[b];
}
// add forward and reverse arcs
src.AddForwardArc(dest);
dest.AddReverseArc(src);
}
public void AddArcs(T[] a, T b) {
GenealogyGraphNode src, dest;
if (!HasNode(b)) {
dest = new GenealogyGraphNode { Data = b };
_dictionary[b] = dest;
} else {
dest = _dictionary[b];
}
foreach (var o in a) {
if (!HasNode(o)) {
src = new GenealogyGraphNode { Data = o };
_dictionary[o] = src;
} else {
src = _dictionary[o];
}
src.AddForwardArc(dest);
dest.AddReverseArc(src);
}
}
}
public class GenealogyGraphNode : IComparable {
public string Id { get; private set; }
public string Label { get; set; }
public bool IsElite { get; set; }
public object Data { get; set; }
public double Quality { get; set; }
public double Rank { get; set; }
public List InEdges { get; set; }
public List OutEdges { get; set; }
public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
public GenealogyGraphNode() { Id = Guid.NewGuid().ToString(); }
public GenealogyGraphNode(GenealogyGraphNode node) {
Id = Guid.NewGuid().ToString();
Rank = node.Rank;
Quality = node.Quality;
IsElite = node.IsElite;
Label = node.Label;
Data = node.Data;
InEdges = node.InEdges;
OutEdges = node.OutEdges;
}
///
/// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
///
/// All the ancestors of the current node
public IEnumerable Ancestors() {
var nodes = new HashSet { this };
int offset = 0;
int c0 = 1;
while (offset != c0) {
int c1 = c0;
for (int i = offset; i != c1; ++i) {
if (nodes.ElementAt(i).InEdges == null) continue;
foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
nodes.Add(p);
yield return p;
}
}
offset = c1;
c0 = nodes.Count;
}
}
///
/// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
///
/// All the descendants of the current node
public IEnumerable Descendants() {
var nodes = new HashSet { this };
int offset = 0;
int c0 = 1;
while (offset != c0) {
int c1 = c0;
for (int i = offset; i != c1; ++i) {
if (nodes.ElementAt(i).OutEdges == null) continue;
foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
nodes.Add(p);
yield return p;
}
}
offset = c1;
c0 = nodes.Count;
}
}
public void AddForwardArc(GenealogyGraphNode target) {
var e = new GenealogyGraphArc { Target = target };
if (OutEdges == null) OutEdges = new List { e };
else OutEdges.Add(e);
}
public void AddReverseArc(GenealogyGraphNode target) {
var e = new GenealogyGraphArc { Target = target };
if (InEdges == null) InEdges = new List { e };
else InEdges.Add(e);
}
// comparable
// may seem weird, it is actually implemented so higher quality means "less than" in terms of ordering
// if quality is equal, the elite node takes precedence
public int CompareTo(object obj) {
if (obj == null) return 1;
var other = obj as GenealogyGraphNode;
if (other == null) return 1;
if (Quality.Equals(other.Quality)) {
if (IsElite) return -1;
return other.IsElite ? 1 : -1;
}
return other.Quality.CompareTo(Quality);
}
}
///
/// An arc is an edge along with an orientation
///
public class GenealogyGraphArc {
public GenealogyGraphNode Target { get; set; }
// these two fields are not used, but they might be useful later
public string Label { get; set; } // might be useful later
public double Weight { get; set; } // might be useful later
}
}