Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772: Changelog:

  • Removed GetCutIndex method, and corresponding index field in the GenealogyGraphNode.
  • Implemented tracking for mutated fragments.
  • Improved FindMatch method.
  • Added IterateNodesBreadth functionality to symbolic expression trees and nodes.
  • Added check conditions for clearing global tracking structures so that the 2 analyzers are not mutually exclusive anymore.
File size: 9.7 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> _dictionary;
34
35    public GenealogyGraph() {
36      _dictionary = new Dictionary<T, GenealogyGraphNode>();
37    }
38
39    public GenealogyGraph(GenealogyGraph<T> g) {
40      _dictionary = new Dictionary<T, GenealogyGraphNode>(g._dictionary);
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      _dictionary = new Dictionary<T, GenealogyGraphNode>(original._dictionary);
59    }
60
61    public bool HasNode(T t) {
62      return _dictionary.ContainsKey(t);
63    }
64
65    public GenealogyGraphNode GetNode(T t) {
66      return HasNode(t) ? _dictionary[t] : null;
67    }
68
69    public IEnumerable<T> Keys {
70      get { return _dictionary.Keys; }
71    }
72
73    public IEnumerable<GenealogyGraphNode> Values {
74      get { return _dictionary.Values; }
75    }
76
77    public bool IsEmpty {
78      get { return !_dictionary.Any(); }
79    }
80
81    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) {
82      return _dictionary.Any(predicate);
83    }
84
85    public void Clear() {
86      _dictionary.Clear();
87    }
88
89    /// <summary>
90    /// Adds a node representing an individual
91    /// </summary>
92    /// <param name="t">The symbolic expression tree</param>
93    /// <param name="quality">The quality value </param>
94    /// <param name="label">The node label</param>
95    /// <param name="rank">The node rank</param>
96    /// <param name="elite">Specifies if this node is an elite</param>
97    public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false) {
98      if (HasNode(t)) return;
99      _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank };
100    }
101
102    /// <summary>
103    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
104    /// </summary>
105    /// <param name="node">The node to be added</param>
106    public void AddNode(GenealogyGraphNode node) {
107      var t = (T)node.Data;
108      if (HasNode(t)) return;
109      _dictionary[t] = node;
110    }
111
112    /// <summary>
113    /// Remove a node from the graph along with edges associated with it
114    /// </summary>
115    /// <param name="t">The graph node</param>
116    public void RemoveNode(T t) {
117      if (!_dictionary.ContainsKey(t)) return;
118      var node = _dictionary[t];
119      if (node.InEdges != null) {
120        foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
121          e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
122          if (!e.Target.OutEdges.Any())
123            e.Target.OutEdges = null; // set to null to be a little more memory efficient
124        }
125        node.InEdges = null;
126      }
127      if (node.OutEdges != null) {
128        foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
129          e.Target.InEdges.RemoveAll(arc => arc.Target == node);
130          if (!e.Target.InEdges.Any())
131            e.Target.InEdges = null; // set to null to be a little more memory efficient
132        }
133        node.OutEdges = null;
134      }
135      _dictionary.Remove(t);
136    }
137
138    public double AverageDegree {
139      get { return Values.Average(x => x.Degree); }
140    }
141
142    /// <summary>
143    /// Adds a graph arc from a to b
144    /// </summary>
145    /// <param name="a"></param>
146    /// <param name="b"></param>
147    public void AddArc(T a, T b) {
148      GenealogyGraphNode src, dest;
149      if (!HasNode(a)) {
150        src = new GenealogyGraphNode { Data = a };
151        _dictionary[a] = src;
152      } else {
153        src = _dictionary[a];
154      }
155      if (!HasNode(b)) {
156        dest = new GenealogyGraphNode { Data = b };
157        _dictionary[b] = dest;
158      } else {
159        dest = _dictionary[b];
160      }
161      // add forward and reverse arcs
162      src.AddForwardArc(dest);
163      dest.AddReverseArc(src);
164    }
165
166    public void AddArcs(T[] a, T b) {
167      GenealogyGraphNode src, dest;
168      if (!HasNode(b)) {
169        dest = new GenealogyGraphNode { Data = b };
170        _dictionary[b] = dest;
171      } else {
172        dest = _dictionary[b];
173      }
174      foreach (var o in a) {
175        if (!HasNode(o)) {
176          src = new GenealogyGraphNode { Data = o };
177          _dictionary[o] = src;
178        } else {
179          src = _dictionary[o];
180        }
181        src.AddForwardArc(dest);
182        dest.AddReverseArc(src);
183      }
184    }
185  }
186
187  public class GenealogyGraphNode : IComparable {
188    public string Id { get; private set; }
189    public string Label { get; set; }
190    public bool IsElite { get; set; }
191    public object Data { get; set; }
192    public double Quality { get; set; }
193    public double Rank { get; set; }
194    public List<GenealogyGraphArc> InEdges { get; set; }
195    public List<GenealogyGraphArc> OutEdges { get; set; }
196
197    public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
198
199    public GenealogyGraphNode() { Id = Guid.NewGuid().ToString(); }
200
201    public GenealogyGraphNode(GenealogyGraphNode node) {
202      Id = Guid.NewGuid().ToString();
203      Rank = node.Rank;
204      Quality = node.Quality;
205      IsElite = node.IsElite;
206      Label = node.Label;
207      Data = node.Data;
208      InEdges = node.InEdges;
209      OutEdges = node.OutEdges;
210    }
211
212    /// <summary>
213    /// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
214    /// </summary>
215    /// <returns>All the ancestors of the current node</returns>
216    public IEnumerable<GenealogyGraphNode> Ancestors() {
217      var nodes = new HashSet<GenealogyGraphNode> { this };
218      int offset = 0;
219      int c0 = 1;
220      while (offset != c0) {
221        int c1 = c0;
222        for (int i = offset; i != c1; ++i) {
223          if (nodes.ElementAt(i).InEdges == null) continue;
224          foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
225            nodes.Add(p);
226            yield return p;
227          }
228        }
229        offset = c1;
230        c0 = nodes.Count;
231      }
232    }
233
234    /// <summary>
235    /// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
236    /// </summary>
237    /// <returns>All the descendants of the current node</returns>
238    public IEnumerable<GenealogyGraphNode> Descendants() {
239      var nodes = new HashSet<GenealogyGraphNode> { this };
240      int offset = 0;
241      int c0 = 1;
242      while (offset != c0) {
243        int c1 = c0;
244        for (int i = offset; i != c1; ++i) {
245          if (nodes.ElementAt(i).OutEdges == null) continue;
246          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
247            nodes.Add(p);
248            yield return p;
249          }
250        }
251        offset = c1;
252        c0 = nodes.Count;
253      }
254    }
255
256    public void AddForwardArc(GenealogyGraphNode target) {
257      var e = new GenealogyGraphArc { Target = target };
258      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
259      else OutEdges.Add(e);
260    }
261
262    public void AddReverseArc(GenealogyGraphNode target) {
263      var e = new GenealogyGraphArc { Target = target };
264      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
265      else InEdges.Add(e);
266    }
267
268    // comparable
269    // may seem weird, it is actually implemented so higher quality means "less than" in terms of ordering
270    // if quality is equal, the elite node takes precedence
271    public int CompareTo(object obj) {
272      if (obj == null) return 1;
273      var other = obj as GenealogyGraphNode;
274      if (other == null) return 1;
275      if (Quality.Equals(other.Quality)) {
276        if (IsElite) return -1;
277        return other.IsElite ? 1 : -1;
278      }
279      return other.Quality.CompareTo(Quality);
280    }
281  }
282
283  /// <summary>
284  /// An arc is an edge along with an orientation
285  /// </summary>
286  public class GenealogyGraphArc {
287    public GenealogyGraphNode Target { get; set; }
288    // these two fields are not used, but they might be useful later
289    public string Label { get; set; } // might be useful later
290    public double Weight { get; set; } // might be useful later
291  }
292}
Note: See TracBrowser for help on using the repository browser.