#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 _nodes;
public GenealogyGraph() {
_nodes = new Dictionary();
}
public GenealogyGraph(GenealogyGraph g) {
_nodes = new Dictionary(g._nodes);
}
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) {
_nodes = new Dictionary(original._nodes);
}
public bool HasNode(T t) { return _nodes.ContainsKey(t); }
public GenealogyGraphNode GetNode(T t) { return HasNode(t) ? _nodes[t] : null; }
public IEnumerable Keys { get { return _nodes.Keys; } }
public IEnumerable Values { get { return _nodes.Values; } }
public bool IsEmpty { get { return !_nodes.Any(); } }
public bool Any(Func, bool> predicate) { return _nodes.Any(predicate); }
public void Clear() { _nodes.Clear(); }
///
/// Adds a node representing an individual
///
/// The data this node is supposed to represent in the graph
public void AddNode(T t) {
if (HasNode(t)) return;
_nodes[t] = new GenealogyGraphNode(t) { Quality = 0.0, Label = "", IsElite = false, Rank = 0.0 };
}
///
/// 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;
_nodes[t] = node;
}
///
/// Remove a node from the graph along with edges associated with it
///
/// The graph node
public void RemoveNode(T t) {
if (!_nodes.ContainsKey(t)) return;
var node = _nodes[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.Count == 0)
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.Count == 0)
e.Target.InEdges = null; // set to null to be a little more memory efficient
}
node.OutEdges = null;
}
_nodes.Remove(t);
}
public double AverageDegree {
get { return Values.Average(x => x.Degree); }
}
///
/// Adds a graph arc from a to b
///
///
///
public void AddArc(T obj1, T obj2, object data1 = null, object data2 = null) {
GenealogyGraphNode src, dest;
if (!HasNode(obj1)) {
src = new GenealogyGraphNode(obj1);
_nodes[obj1] = src;
} else {
src = _nodes[obj1];
}
if (!HasNode(obj2)) {
dest = new GenealogyGraphNode(obj2);
_nodes[obj2] = dest;
} else {
dest = _nodes[obj2];
}
// add forward and reverse arcs
src.AddForwardArc(dest, data1);
dest.AddReverseArc(src, data2);
}
//public void AddArcs(T[] a, T b) {
// GenealogyGraphNode src, dest;
// if (!HasNode(b)) {
// dest = new GenealogyGraphNode(b);
// _nodes[b] = dest;
// } else {
// dest = _nodes[b];
// }
// foreach (var o in a) {
// if (!HasNode(o)) {
// src = new GenealogyGraphNode(o);
// _nodes[o] = src;
// } else {
// src = _nodes[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 double Quality { get; set; }
public double Rank { get; set; }
public List InEdges { get; set; }
public List OutEdges { get; set; }
private object _data;
public object Data {
get { return _data; }
set {
if (value == null)
throw new ArgumentException("Node data cannot be null.");
else {
_data = value; // data must be of type T
}
}
}
public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
public GenealogyGraphNode(object data) {
if (data == null) {
throw new ArgumentException("Node data cannot be null");
}
Id = Guid.NewGuid().ToString();
Data = data;
}
public GenealogyGraphNode(GenealogyGraphNode node) {
Id = Guid.NewGuid().ToString();
Rank = node.Rank;
Quality = node.Quality;
IsElite = node.IsElite;
Label = node.Label;
Data = node.Data;
InEdges = new List(node.InEdges);
OutEdges = new List(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 i = 0;
while (i != nodes.Count) {
if (nodes.ElementAt(i).InEdges != null) {
foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
nodes.Add(p);
yield return p;
}
}
++i;
}
}
///
/// 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 i = 0;
while (i != nodes.Count) {
if (nodes.ElementAt(i).OutEdges != null) {
foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
nodes.Add(p);
yield return p;
}
}
++i;
}
}
// this method can be used to add arcs towards targets that are not visible in the graph
// (they do not appear in the _nodes Dictionary). It is the programmers responsibility to
// enforce the correct and desired behavior.
public void AddForwardArc(GenealogyGraphNode target, object data = null) {
var e = new GenealogyGraphArc { Target = target, Data = data };
if (OutEdges == null) OutEdges = new List { e };
else OutEdges.Add(e);
}
public void AddReverseArc(GenealogyGraphNode target, object data = null) {
var e = new GenealogyGraphArc { Target = target, Data = data };
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
// object used to embed information about node interactions into the arc that connects them (therefore a graph arc will encode a relationship/interaction)
public object Data { get; set; }
}
}