1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Drawing;
|
---|
4 | using System.Linq;
|
---|
5 | using HeuristicLab.Common;
|
---|
6 | using HeuristicLab.Core;
|
---|
7 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
8 |
|
---|
9 | namespace HeuristicLab.EvolutionaryTracking {
|
---|
10 | public class GenealogyGraph : NamedItem {
|
---|
11 | private readonly Dictionary<object, Node> _dictionary;
|
---|
12 |
|
---|
13 | public GenealogyGraph() {
|
---|
14 | _dictionary = new Dictionary<object, Node>();
|
---|
15 | }
|
---|
16 |
|
---|
17 | public GenealogyGraph(GenealogyGraph g) {
|
---|
18 | _dictionary = new Dictionary<object, Node>(g._dictionary);
|
---|
19 | }
|
---|
20 |
|
---|
21 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
22 | return new GenealogyGraph(this, cloner);
|
---|
23 | }
|
---|
24 |
|
---|
25 | public override string ItemName {
|
---|
26 | get { return "GenealogyGraph"; }
|
---|
27 | }
|
---|
28 |
|
---|
29 | public override string ItemDescription {
|
---|
30 | get { return "A graph describing the genealogies of all the individuals"; }
|
---|
31 | }
|
---|
32 |
|
---|
33 | public new Version ItemVersion {
|
---|
34 | get { return new Version(3, 3, 6); }
|
---|
35 | }
|
---|
36 |
|
---|
37 | public new Image ItemImage {
|
---|
38 | get { return Common.Resources.VSImageLibrary.Graph; }
|
---|
39 | }
|
---|
40 |
|
---|
41 | [StorableConstructor]
|
---|
42 | private GenealogyGraph(bool serializing)
|
---|
43 | : base(serializing) {
|
---|
44 | }
|
---|
45 |
|
---|
46 | private GenealogyGraph(GenealogyGraph original, Cloner cloner)
|
---|
47 | : base(original, cloner) {
|
---|
48 | _dictionary = new Dictionary<object, Node>(original._dictionary);
|
---|
49 | }
|
---|
50 |
|
---|
51 | public bool HasNode(object t) {
|
---|
52 | return _dictionary.ContainsKey(t);
|
---|
53 | }
|
---|
54 |
|
---|
55 | public Node GetNode(object t) {
|
---|
56 | return this.HasNode(t) ? _dictionary[t] : null;
|
---|
57 | }
|
---|
58 |
|
---|
59 | public IEnumerable<object> Keys {
|
---|
60 | get { return _dictionary.Keys; }
|
---|
61 | }
|
---|
62 |
|
---|
63 | public IEnumerable<Node> Values {
|
---|
64 | get { return _dictionary.Values; }
|
---|
65 | }
|
---|
66 |
|
---|
67 | public bool Any() {
|
---|
68 | return _dictionary.Any();
|
---|
69 | }
|
---|
70 |
|
---|
71 | public bool Any(Func<KeyValuePair<object, Node>, bool> predicate) {
|
---|
72 | return _dictionary.Any(predicate);
|
---|
73 | }
|
---|
74 |
|
---|
75 | public void Clear() {
|
---|
76 | _dictionary.Clear();
|
---|
77 | }
|
---|
78 |
|
---|
79 | /// <summary>
|
---|
80 | /// Adds a node representing an individual
|
---|
81 | /// </summary>
|
---|
82 | /// <param name="t">The symbolic expression tree</param>
|
---|
83 | /// <param name="q">The quality value </param>
|
---|
84 | /// <param name="l">The node label</param>
|
---|
85 | /// <param name="elite">Specifies if this node is an elite</param>
|
---|
86 | public void AddNode(object t, double q = 0.0, string l = "", int g = 0, bool elite = false) {
|
---|
87 | if (HasNode(t)) return;
|
---|
88 | var color = new Color { R = (byte)(255 - 255 * q), G = (byte)(255 * q), B = 50 };
|
---|
89 | _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Generation = g, Color = color };
|
---|
90 | }
|
---|
91 |
|
---|
92 | /// <summary>
|
---|
93 | /// more of a low level method to minimize memory usage when creating and returning subgraphs
|
---|
94 | /// </summary>
|
---|
95 | /// <param name="n"></param>
|
---|
96 | public void AddNode(Node n) {
|
---|
97 | var t = n.Data;
|
---|
98 | if (HasNode(t))
|
---|
99 | return;
|
---|
100 | _dictionary[t] = n;
|
---|
101 | }
|
---|
102 |
|
---|
103 | /// <summary>
|
---|
104 | /// Remove a node from the graph along with edges associated with it
|
---|
105 | /// </summary>
|
---|
106 | /// <param name="t">The graph node</param>
|
---|
107 | public void RemoveNode(object t) {
|
---|
108 | if (!_dictionary.ContainsKey(t))
|
---|
109 | return;
|
---|
110 | Node n = _dictionary[t];
|
---|
111 | if (n.InEdges != null) {
|
---|
112 | foreach (var e in n.InEdges.Where(e => e.Target.OutEdges != null)) {
|
---|
113 | e.Target.OutEdges.RemoveAll(arc => arc.Target == n);
|
---|
114 | if (!e.Target.OutEdges.Any())
|
---|
115 | e.Target.OutEdges = null; // set to null to be a little more memory efficient
|
---|
116 | }
|
---|
117 | n.InEdges = null;
|
---|
118 | }
|
---|
119 | if (n.OutEdges != null) {
|
---|
120 | foreach (var e in n.OutEdges.Where(e => e.Target.InEdges != null)) {
|
---|
121 | e.Target.InEdges.RemoveAll(arc => arc.Target == n);
|
---|
122 | if (!e.Target.InEdges.Any())
|
---|
123 | e.Target.InEdges = null; // set to null to be a little more memory efficient
|
---|
124 | }
|
---|
125 | n.OutEdges = null;
|
---|
126 | }
|
---|
127 | _dictionary.Remove(t);
|
---|
128 | }
|
---|
129 |
|
---|
130 | public double AverageDegree {
|
---|
131 | get { return Values.Average(x => x.Degree); }
|
---|
132 | }
|
---|
133 |
|
---|
134 | /// <summary>
|
---|
135 | /// Adds a graph arc from a to b
|
---|
136 | /// </summary>
|
---|
137 | /// <param name="a"></param>
|
---|
138 | /// <param name="b"></param>
|
---|
139 | /// <param name="label"></param>
|
---|
140 | public void AddArc(object a, object b, string label = "") {
|
---|
141 | Node src, dest;
|
---|
142 | if (!HasNode(a)) {
|
---|
143 | src = new Node { Data = a };
|
---|
144 | _dictionary[a] = src;
|
---|
145 | } else {
|
---|
146 | src = _dictionary[a];
|
---|
147 | }
|
---|
148 | if (!HasNode(b)) {
|
---|
149 | dest = new Node { Data = b };
|
---|
150 | _dictionary[b] = dest;
|
---|
151 | } else {
|
---|
152 | dest = _dictionary[b];
|
---|
153 | }
|
---|
154 | // add forward and reverse arcs
|
---|
155 | src.AddForwardArc(dest, label);
|
---|
156 | dest.AddReverseArc(src, label);
|
---|
157 | }
|
---|
158 |
|
---|
159 | public void AddArcs(object[] a, object b, string label) {
|
---|
160 | Node src, dest;
|
---|
161 | if (!HasNode(b)) {
|
---|
162 | dest = new Node { Data = b };
|
---|
163 | _dictionary[b] = dest;
|
---|
164 | } else {
|
---|
165 | dest = _dictionary[b];
|
---|
166 | }
|
---|
167 | foreach (var o in a) {
|
---|
168 | if (!HasNode(o)) {
|
---|
169 | src = new Node { Data = o };
|
---|
170 | _dictionary[o] = src;
|
---|
171 | } else {
|
---|
172 | src = _dictionary[o];
|
---|
173 | }
|
---|
174 | src.AddForwardArc(dest, label);
|
---|
175 | dest.AddReverseArc(src, label);
|
---|
176 | }
|
---|
177 | }
|
---|
178 | }
|
---|
179 |
|
---|
180 | public class Node {
|
---|
181 | public string Id { get; private set; }
|
---|
182 | public string Label { get; set; }
|
---|
183 | public bool IsElite { get; set; }
|
---|
184 | public List<Arc> InEdges { get; set; }
|
---|
185 | public List<Arc> OutEdges { get; set; }
|
---|
186 | public object Data { get; set; }
|
---|
187 | public double Quality { get; set; }
|
---|
188 | public int Generation { get; set; }
|
---|
189 | public Color Color { get; set; }
|
---|
190 |
|
---|
191 | public int Degree {
|
---|
192 | get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); }
|
---|
193 | }
|
---|
194 |
|
---|
195 | public Node() {
|
---|
196 | Id = Guid.NewGuid().ToString();
|
---|
197 | }
|
---|
198 |
|
---|
199 | /// <summary>
|
---|
200 | /// Returns a genealogical graph rooted in the current node, containing all ancestry information
|
---|
201 | /// </summary>
|
---|
202 | /// <returns></returns>
|
---|
203 | public GenealogyGraph Genealogy() {
|
---|
204 | var graph = new GenealogyGraph();
|
---|
205 | graph.AddNode(this);
|
---|
206 | foreach (var node in this.Ancestors())
|
---|
207 | graph.AddNode(node);
|
---|
208 | return graph;
|
---|
209 | }
|
---|
210 |
|
---|
211 | /// <summary>
|
---|
212 | /// Returns an enumerable of all the ancestors of the current node
|
---|
213 | /// </summary>
|
---|
214 | /// <returns></returns>
|
---|
215 | public IEnumerable<Node> Ancestors() {
|
---|
216 | var nodes = new HashSet<Node> { this };
|
---|
217 | int offset = 0;
|
---|
218 | int c0 = 1;
|
---|
219 | while (offset != c0) {
|
---|
220 | int c1 = c0;
|
---|
221 | for (int i = offset; i != c1; ++i) {
|
---|
222 | if (nodes.ElementAt(i).InEdges == null) continue;
|
---|
223 | foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
|
---|
224 | nodes.Add(p);
|
---|
225 | yield return p;
|
---|
226 | }
|
---|
227 | }
|
---|
228 | offset = c1;
|
---|
229 | c0 = nodes.Count;
|
---|
230 | }
|
---|
231 | }
|
---|
232 |
|
---|
233 | public void AddForwardArc(Node target, string label) {
|
---|
234 | var e = new Arc { Target = target, Label = label };
|
---|
235 | if (OutEdges == null)
|
---|
236 | OutEdges = new List<Arc> { e };
|
---|
237 | else
|
---|
238 | OutEdges.Add(e);
|
---|
239 | }
|
---|
240 |
|
---|
241 | public void AddReverseArc(Node target, string label) {
|
---|
242 | var e = new Arc { Target = target, Label = label };
|
---|
243 | if (InEdges == null)
|
---|
244 | InEdges = new List<Arc> { e };
|
---|
245 | else
|
---|
246 | InEdges.Add(e);
|
---|
247 | }
|
---|
248 | }
|
---|
249 |
|
---|
250 | /// <summary>
|
---|
251 | /// An arc is an edge along with an orientation
|
---|
252 | /// </summary>
|
---|
253 | public class Arc {
|
---|
254 | public Node Target { get; set; }
|
---|
255 | public string Label { get; set; }
|
---|
256 | public double Weight { get; set; }
|
---|
257 | // other attributes
|
---|
258 | }
|
---|
259 | // an edge can be represented as a tuple<Node, Node> TODO: figure it out (might be useful for easier querying)
|
---|
260 |
|
---|
261 | public struct Color {
|
---|
262 | public byte R { get; set; }
|
---|
263 | public byte G { get; set; }
|
---|
264 | public byte B { get; set; }
|
---|
265 | }
|
---|
266 | }
|
---|