Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/DirectedGraph.cs @ 11021

Last change on this file since 11021 was 11021, checked in by bburlacu, 8 years ago

#1772: Added ExportDot method to DirectedGraph. Worked on the BottomUpDistanceCalculator.

File size: 6.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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 System.Text;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.EvolutionTracking {
32  [Item("DirectedGraph", "Generic class representing a directed graph with custom vertices and content")]
33  [StorableClass]
34  public class DirectedGraph : Item, IDirectedGraph {
35    public bool AllowDuplicateContent { get; set; }
36
37    [Storable]
38    protected readonly List<IVertex> vertices; // for performance reasons, maybe this should be a linked list (fast remove)
39    public IEnumerable<IVertex> Vertices {
40      get { return vertices; }
41    }
42
43    [Storable]
44    private readonly Dictionary<string, IVertex> idMap;
45
46    [Storable]
47    private readonly Dictionary<object, IVertex> contentMap;
48
49    [Storable]
50    protected readonly List<IArc> arcs;
51    public IEnumerable<IArc> Arcs {
52      get { return arcs; }
53    }
54
55    [StorableConstructor]
56    protected DirectedGraph(bool serializing)
57      : base(serializing) {
58    }
59
60    [StorableHook(HookType.AfterDeserialization)]
61    private void AfterDeserialization() {
62      foreach (var arc in arcs) {
63        arc.Source.AddForwardArc(arc);
64        arc.Target.AddReverseArc(arc);
65      }
66
67      foreach (var vertex in vertices) {
68        vertex.PreContentChanged += Vertex_PreContentChanged;
69        vertex.PostContentChanged += Vertex_PostContentChanged;
70      }
71    }
72
73    public DirectedGraph() {
74      vertices = new List<IVertex>();
75      arcs = new List<IArc>();
76      contentMap = new Dictionary<object, IVertex>();
77      idMap = new Dictionary<string, IVertex>();
78    }
79
80    protected DirectedGraph(DirectedGraph original, Cloner cloner)
81      : base(original, cloner) {
82      vertices = new List<IVertex>(original.vertices);
83      arcs = new List<IArc>(original.arcs);
84      contentMap = new Dictionary<object, IVertex>(original.contentMap);
85      idMap = new Dictionary<string, IVertex>(original.idMap);
86    }
87
88    public override IDeepCloneable Clone(Cloner cloner) {
89      return new DirectedGraph(this, cloner);
90    }
91
92    public bool Contains(IVertex t) {
93      return vertices.Contains(t);
94    }
95
96    public bool Contains(object content) {
97      return contentMap.ContainsKey(content);
98    }
99
100    public IVertex GetVertex(string id) {
101      IVertex result;
102      idMap.TryGetValue(id, out result);
103      return result;
104    }
105
106    public IVertex GetVertex(object content) {
107      IVertex result;
108      contentMap.TryGetValue(content, out result);
109      return result;
110    }
111
112    public virtual bool Any(Func<IVertex, bool> predicate) {
113      return vertices.Any(predicate);
114    }
115
116    public virtual bool IsEmpty {
117      get { return !vertices.Any(); }
118    }
119
120    public virtual void Clear() {
121      vertices.Clear();
122      contentMap.Clear();
123      idMap.Clear();
124    }
125
126    public virtual void AddVertex(IVertex vertex) {
127      if (vertex.Content != null) {
128        if (!AllowDuplicateContent && contentMap.ContainsKey(vertex.Content)) {
129          throw new Exception("Content already exists in the graph.");
130        }
131        contentMap[vertex.Content] = vertex;
132      }
133      idMap.Add(vertex.Id, vertex);
134      vertices.Add(vertex);
135
136      vertex.PreContentChanged += Vertex_PreContentChanged;
137      vertex.PostContentChanged += Vertex_PostContentChanged;
138    }
139
140    public virtual void RemoveVertex(IVertex vertex) {
141      contentMap.Remove(vertex.Content);
142      idMap.Remove(vertex.Id);
143      vertices.Remove(vertex);
144
145      // remove connections to/from the removed vertex
146      foreach (var arc in vertex.InArcs) {
147        arc.Source.OutArcs = arc.Source.OutArcs.Where(x => x.Target != vertex);
148      }
149      foreach (var arc in vertex.OutArcs) {
150        arc.Target.InArcs = arc.Target.InArcs.Where(x => x.Source != vertex);
151      }
152      // de-register event handlers
153      vertex.PreContentChanged -= Vertex_PreContentChanged;
154      vertex.PostContentChanged -= Vertex_PostContentChanged;
155    }
156
157    public virtual IArc AddArc(IVertex source, IVertex target) {
158      var arc = new Arc(source, target);
159      source.AddForwardArc(arc);
160      target.AddReverseArc(arc);
161      arcs.Add(arc);
162      return arc;
163    }
164
165    private void Vertex_PreContentChanged(object sender, EventArgs args) {
166      var vertex = (IVertex)sender;
167      if (contentMap.ContainsKey(vertex.Content)) {
168        contentMap.Remove(vertex.Content);
169      }
170    }
171
172    private void Vertex_PostContentChanged(object sender, EventArgs args) {
173      var vertex = (IVertex)sender;
174      if (vertex.Content != null)
175        contentMap.Add(vertex.Content, vertex);
176    }
177
178    public override Image ItemImage {
179      get { return Common.Resources.VSImageLibrary.Graph; }
180    }
181
182    public string ExportDot() {
183      var sb = new StringBuilder();
184      sb.Append("digraph g {");
185      foreach (var v in Vertices) {
186        sb.Append("\"" + v.Id + "\" [label=\"" + v.Label + "\"];" + Environment.NewLine);
187      }
188
189      foreach (var v in Vertices) {
190        foreach (var c in v.OutArcs.Select(x => x.Target)) {
191          sb.Append("\"" + v.Id + "\" -> \"" + c.Id + "\"" + Environment.NewLine);
192        }
193      }
194      sb.Append("}");
195      return sb.ToString();
196    }
197  }
198}
Note: See TracBrowser for help on using the repository browser.