Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs @ 7800

Last change on this file since 7800 was 7800, checked in by bburlacu, 11 years ago

#1772: Fixed display of genetic fragments (received via crossover) in the GenealogyGraphView. Added parent, offspring and fragment lengths histogram.

File size: 9.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.EvolutionaryTracking {
31  [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
32  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
33    private readonly Dictionary<T, GenealogyGraphNode> _nodes;
34
35    public GenealogyGraph() {
36      _nodes = new Dictionary<T, GenealogyGraphNode>();
37    }
38
39    public GenealogyGraph(GenealogyGraph<T> g) {
40      _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
41    }
42
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new GenealogyGraph<T>(this, cloner);
45    }
46
47    public override Image ItemImage {
48      get { return Common.Resources.VSImageLibrary.Graph; }
49    }
50
51    [StorableConstructor]
52    protected GenealogyGraph(bool serializing)
53      : base(serializing) {
54    }
55
56    private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
57      : base(original, cloner) {
58      _nodes = new Dictionary<T, GenealogyGraphNode>(original._nodes);
59    }
60
61    public bool HasNode(T t) { return _nodes.ContainsKey(t); }
62    public GenealogyGraphNode GetNode(T t) { return HasNode(t) ? _nodes[t] : null; }
63    public IEnumerable<T> Keys { get { return _nodes.Keys; } }
64    public IEnumerable<GenealogyGraphNode> Values { get { return _nodes.Values; } }
65    public bool IsEmpty { get { return !_nodes.Any(); } }
66    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) { return _nodes.Any(predicate); }
67    public void Clear() { _nodes.Clear(); }
68
69    /// <summary>
70    /// Adds a node representing an individual
71    /// </summary>
72    /// <param name="t">The data this node is supposed to represent in the graph</param>
73    public void AddNode(T t) {
74      if (HasNode(t)) return;
75      _nodes[t] = new GenealogyGraphNode(t) { Quality = 0.0, Label = "", IsElite = false, Rank = 0.0 };
76    }
77
78    /// <summary>
79    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
80    /// </summary>
81    /// <param name="node">The node to be added</param>
82    public void AddNode(GenealogyGraphNode node) {
83      var t = (T)node.Data;
84      if (HasNode(t)) return;
85      _nodes[t] = node;
86    }
87
88    /// <summary>
89    /// Remove a node from the graph along with edges associated with it
90    /// </summary>
91    /// <param name="t">The graph node</param>
92    public void RemoveNode(T t) {
93      if (!_nodes.ContainsKey(t)) return;
94      var node = _nodes[t];
95      if (node.InEdges != null) {
96        foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
97          e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
98          if (e.Target.OutEdges.Count == 0)
99            e.Target.OutEdges = null; // set to null to be a little more memory efficient
100        }
101        node.InEdges = null;
102      }
103      if (node.OutEdges != null) {
104        foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
105          e.Target.InEdges.RemoveAll(arc => arc.Target == node);
106          if (e.Target.InEdges.Count == 0)
107            e.Target.InEdges = null; // set to null to be a little more memory efficient
108        }
109        node.OutEdges = null;
110      }
111      _nodes.Remove(t);
112    }
113
114    public double AverageDegree {
115      get { return Values.Average(x => x.Degree); }
116    }
117
118    /// <summary>
119    /// Adds a graph arc from a to b
120    /// </summary>
121    /// <param name="obj1"></param>
122    /// <param name="obj2"></param>
123    public void AddArc(T obj1, T obj2, object data1 = null, object data2 = null) {
124      GenealogyGraphNode src, dest;
125      if (!HasNode(obj1)) {
126        src = new GenealogyGraphNode(obj1);
127        _nodes[obj1] = src;
128      } else {
129        src = _nodes[obj1];
130      }
131      if (!HasNode(obj2)) {
132        dest = new GenealogyGraphNode(obj2);
133        _nodes[obj2] = dest;
134      } else {
135        dest = _nodes[obj2];
136      }
137      // add forward and reverse arcs
138      src.AddForwardArc(dest, data1);
139      dest.AddReverseArc(src, data2);
140    }
141
142    //public void AddArcs(T[] a, T b) {
143    //  GenealogyGraphNode src, dest;
144    //  if (!HasNode(b)) {
145    //    dest = new GenealogyGraphNode(b);
146    //    _nodes[b] = dest;
147    //  } else {
148    //    dest = _nodes[b];
149    //  }
150    //  foreach (var o in a) {
151    //    if (!HasNode(o)) {
152    //      src = new GenealogyGraphNode(o);
153    //      _nodes[o] = src;
154    //    } else {
155    //      src = _nodes[o];
156    //    }
157    //    src.AddForwardArc(dest);
158    //    dest.AddReverseArc(src);
159    //  }
160    //}
161  }
162
163  public class GenealogyGraphNode : IComparable {
164    public string Id { get; private set; }
165    public string Label { get; set; }
166    public bool IsElite { get; set; }
167    public double Quality { get; set; }
168    public double Rank { get; set; }
169    public List<GenealogyGraphArc> InEdges { get; set; }
170    public List<GenealogyGraphArc> OutEdges { get; set; }
171    private object _data;
172    public object Data {
173      get { return _data; }
174      set {
175        if (value == null)
176          throw new ArgumentException("Node data cannot be null.");
177        else {
178          _data = value; // data must be of type T
179        }
180      }
181    }
182
183    public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
184
185    public GenealogyGraphNode(object data) {
186      if (data == null) {
187        throw new ArgumentException("Node data cannot be null");
188      }
189      Id = Guid.NewGuid().ToString();
190      Data = data;
191    }
192
193    public GenealogyGraphNode(GenealogyGraphNode node) {
194      Id = Guid.NewGuid().ToString();
195      Rank = node.Rank;
196      Quality = node.Quality;
197      IsElite = node.IsElite;
198      Label = node.Label;
199      Data = node.Data;
200      InEdges = new List<GenealogyGraphArc>(node.InEdges);
201      OutEdges = new List<GenealogyGraphArc>(node.OutEdges);
202    }
203
204    /// <summary>
205    /// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
206    /// </summary>
207    /// <returns>All the ancestors of the current node</returns>
208    public IEnumerable<GenealogyGraphNode> Ancestors() {
209      var nodes = new HashSet<GenealogyGraphNode> { this };
210      int i = 0;
211      while (i != nodes.Count) {
212        if (nodes.ElementAt(i).InEdges != null) {
213          foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
214            nodes.Add(p);
215            yield return p;
216          }
217        }
218        ++i;
219      }
220    }
221
222    /// <summary>
223    /// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
224    /// </summary>
225    /// <returns>All the descendants of the current node</returns>
226    public IEnumerable<GenealogyGraphNode> Descendants() {
227      var nodes = new HashSet<GenealogyGraphNode> { this };
228      int i = 0;
229      while (i != nodes.Count) {
230        if (nodes.ElementAt(i).OutEdges != null) {
231          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
232            nodes.Add(p);
233            yield return p;
234          }
235        }
236        ++i;
237      }
238    }
239
240    // this method can be used to add arcs towards targets that are not visible in the graph
241    // (they do not appear in the _nodes Dictionary). It is the programmers responsibility to
242    // enforce the correct and desired behavior.
243    public void AddForwardArc(GenealogyGraphNode target, object data = null) {
244      var e = new GenealogyGraphArc { Target = target, Data = data };
245      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
246      else OutEdges.Add(e);
247    }
248
249    public void AddReverseArc(GenealogyGraphNode target, object data = null) {
250      var e = new GenealogyGraphArc { Target = target, Data = data };
251      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
252      else InEdges.Add(e);
253    }
254
255    // comparable
256    // may seem weird, it is actually implemented so higher quality means "less than" in terms of ordering
257    // if quality is equal, the elite node takes precedence
258    public int CompareTo(object obj) {
259      if (obj == null) return 1;
260      var other = obj as GenealogyGraphNode;
261      if (other == null) return 1;
262      if (Quality.Equals(other.Quality)) {
263        if (IsElite) return -1;
264        return other.IsElite ? 1 : -1;
265      }
266      return other.Quality.CompareTo(Quality);
267    }
268  }
269
270  /// <summary>
271  /// An arc is an edge along with an orientation
272  /// </summary>
273  public class GenealogyGraphArc {
274    public GenealogyGraphNode Target { get; set; }
275    // these two fields are not used, but they might be useful later
276    public string Label { get; set; } // might be useful later
277    public double Weight { get; set; } // might be useful later
278    // object used to embed information about node interactions into the arc that connects them (therefore a graph arc will encode a relationship/interaction)
279    public object Data { get; set; }
280  }
281}
Note: See TracBrowser for help on using the repository browser.