Changeset 11229 for branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph

Timestamp:

07/29/14 16:20:08 (10 years ago)

Author:

bburlacu

Message:

#2215: Refactored and simplified DirectedGraph and related components API, simplified the BottomUpSimilarityCalculator by not using a directed graph and vertices but a simpler object so that the similarity calculator is self-contained.

Location:

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph

Files:

• Arc.cs (modified) (3 diffs)
• DirectedGraph.cs (modified) (4 diffs)
• Interfaces/IArc.cs (modified) (2 diffs)
• Interfaces/IDirectedGraph.cs (modified) (2 diffs)
• Interfaces/IVertex.cs (modified) (2 diffs)
• Vertex.cs (modified) (8 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Arc.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -26 +27 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   /// <summary>
-  /// An arc that can have a weight, a label, and can old additional information in the Data object
+  /// An arc that can have a weight, a label, and a data object for holding additional info
   /// </summary>
   [StorableClass]
   public class Arc : Item, IArc {
-    [Storable]
-    public IVertex Source { get; set; }
+    public event EventHandler Changed;
+    protected virtual void OnChanged(object sender, EventArgs args) {
+      var changed = Changed;
+      if (changed != null)
+        changed(sender, args);
+    }
 
     [Storable]
-    public IVertex Target { get; set; }
+    public IVertex Source { get; private set; }
 
     [Storable]
-    public string Label { get; set; }
+    public IVertex Target { get; private set; }
 
     [Storable]
-    public double Weight { get; set; }
+    protected string label;
+    public string Label {
+      get { return label; }
+      set {
+        label = value;
+        OnChanged(this, EventArgs.Empty);
+      }
+    }
 
     [Storable]
-    public object Data { get; set; }
+    protected double weight;
+    public double Weight {
+      get { return weight; }
+      set {
+        weight = value;
+        OnChanged(this, EventArgs.Empty);
+      }
+    }
+
+    [Storable]
+    protected object data;
+    public object Data {
+      get { return data; }
+      set {
+        data = value;
+        OnChanged(this, EventArgs.Empty);
+      }
+    }
 
     [StorableConstructor]
     public Arc(bool deserializing) : base(deserializing) { }
-
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new Arc(this, cloner);
-    }
-    public Arc() { }
 
     public Arc(IVertex source, IVertex target) {
@@ -60 +84 @@
     protected Arc(Arc original, Cloner cloner)
       : base(original, cloner) {
-      Source = original.Source;
-      Target = original.Target;
-      Label = original.Label;
-      Weight = original.Weight;
-      Data = original.Data;
+      Source = cloner.Clone(original.Source);
+      Target = cloner.Clone(original.Target);
+      label = original.Label;
+      weight = original.Weight;
+      data = original;
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Arc(this, cloner);
+    }
+  }
+
+  [StorableClass]
+  public class Arc<T> : Arc, IArc<T> where T : class,IItem {
+    public Arc(bool deserializing)
+      : base(deserializing) {
+    }
+
+    public Arc(IVertex source, IVertex target)
+      : base(source, target) {
+    }
+
+    protected Arc(Arc original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    new public IVertex<T> Source {
+      get { return (IVertex<T>)base.Source; }
+    }
+    new public IVertex<T> Target {
+      get { return (IVertex<T>)base.Target; }
     }
   }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/DirectedGraph.cs

@@ -24 +24 @@
 using System.Drawing;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -33 +32 @@
   [StorableClass]
   public class DirectedGraph : Item, IDirectedGraph {
-    public bool AllowDuplicateContent { get; set; }
-
+    protected HashSet<IVertex> vertices;
     [Storable]
-    protected readonly List<IVertex> vertices; // for performance reasons, maybe this should be a linked list (fast remove)
     public IEnumerable<IVertex> Vertices {
       get { return vertices; }
+      private set { vertices = new HashSet<IVertex>(value); }
     }
 
+    protected HashSet<IArc> arcs;
     [Storable]
-    private readonly Dictionary<string, IVertex> idMap;
-
-    [Storable]
-    private readonly Dictionary<object, IVertex> contentMap;
-
-    [Storable]
-    protected readonly List<IArc> arcs;
     public IEnumerable<IArc> Arcs {
       get { return arcs; }
+      private set { arcs = new HashSet<IArc>(value); }
     }
 
@@ -60 +53 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      foreach (var arc in arcs) {
-        arc.Source.AddForwardArc(arc);
-        arc.Target.AddReverseArc(arc);
+      foreach (var vertex in vertices) {
+        vertex.ArcAdded += OnArcAdded;
+        vertex.ArcRemoved += OnArcRemoved;
+        vertex.Changed += OnVertexChanged;
       }
 
-      foreach (var vertex in vertices) {
-        vertex.PreContentChanged += Vertex_PreContentChanged;
-        vertex.PostContentChanged += Vertex_PostContentChanged;
+      foreach (var arc in arcs) {
+        var source = arc.Source;
+        var target = arc.Target;
+        source.AddArc(arc);
+        target.AddArc(arc);
+        arc.Changed += OnArcChanged;
       }
     }
 
     public DirectedGraph() {
-      vertices = new List<IVertex>();
-      arcs = new List<IArc>();
-      contentMap = new Dictionary<object, IVertex>();
-      idMap = new Dictionary<string, IVertex>();
+      vertices = new HashSet<IVertex>();
+      arcs = new HashSet<IArc>();
     }
 
     protected DirectedGraph(DirectedGraph original, Cloner cloner)
       : base(original, cloner) {
-      vertices = new List<IVertex>(original.vertices);
-      arcs = new List<IArc>(original.arcs);
-      contentMap = new Dictionary<object, IVertex>(original.contentMap);
-      idMap = new Dictionary<string, IVertex>(original.idMap);
+      vertices = new HashSet<IVertex>(original.vertices.Select(cloner.Clone));
+      arcs = new HashSet<IArc>(original.arcs.Select(cloner.Clone));
     }
 
@@ -90 +83 @@
     }
 
-    public bool Contains(IVertex t) {
-      return vertices.Contains(t);
-    }
-
-    public bool Contains(object content) {
-      return contentMap.ContainsKey(content);
-    }
-
-    public IVertex GetVertex(string id) {
-      IVertex result;
-      idMap.TryGetValue(id, out result);
-      return result;
-    }
-
-    public IVertex GetVertex(object content) {
-      IVertex result;
-      contentMap.TryGetValue(content, out result);
-      return result;
-    }
-
-    public virtual bool Any(Func<IVertex, bool> predicate) {
-      return vertices.Any(predicate);
-    }
-
-    public virtual bool IsEmpty {
-      get { return !vertices.Any(); }
-    }
-
     public virtual void Clear() {
       vertices.Clear();
-      contentMap.Clear();
-      idMap.Clear();
+      arcs.Clear();
     }
 
     public virtual void AddVertex(IVertex vertex) {
-      if (vertex.Content != null) {
-        if (!AllowDuplicateContent && contentMap.ContainsKey(vertex.Content)) {
-          throw new Exception("Content already exists in the graph.");
-        }
-        contentMap[vertex.Content] = vertex;
-      }
-      idMap.Add(vertex.Id, vertex);
       vertices.Add(vertex);
-
-      vertex.PreContentChanged += Vertex_PreContentChanged;
-      vertex.PostContentChanged += Vertex_PostContentChanged;
+      // register event handlers
+      vertex.Changed += OnVertexChanged;
+      vertex.ArcAdded += OnArcAdded;
+      vertex.ArcRemoved += OnArcRemoved;
+      OnVertexAdded(this, EventArgs.Empty);
     }
 
     public virtual void RemoveVertex(IVertex vertex) {
-      contentMap.Remove(vertex.Content);
-      idMap.Remove(vertex.Id);
       vertices.Remove(vertex);
-
       // remove connections to/from the removed vertex
-      foreach (var arc in vertex.InArcs) {
-        arc.Source.OutArcs = arc.Source.OutArcs.Where(x => x.Target != vertex);
-      }
-      foreach (var arc in vertex.OutArcs) {
-        arc.Target.InArcs = arc.Target.InArcs.Where(x => x.Source != vertex);
-      }
-      // de-register event handlers
-      vertex.PreContentChanged -= Vertex_PreContentChanged;
-      vertex.PostContentChanged -= Vertex_PostContentChanged;
+      foreach (var arc in vertex.InArcs.Concat(vertex.OutArcs))
+        RemoveArc(arc);
+      // deregister event handlers
+      vertex.ArcAdded -= OnArcAdded;
+      vertex.ArcRemoved -= OnArcRemoved;
+      vertex.Changed -= OnVertexChanged;
+      OnVertexRemoved(this, EventArgs.Empty);
     }
 
-    public virtual IArc AddArc(IVertex source, IVertex target) {
+    public IArc AddArc(IVertex source, IVertex target) {
       var arc = new Arc(source, target);
-      source.AddForwardArc(arc);
-      target.AddReverseArc(arc);
-      arcs.Add(arc);
+      AddArc(arc);
       return arc;
     }
 
-    private void Vertex_PreContentChanged(object sender, EventArgs args) {
-      var vertex = (IVertex)sender;
-      if (contentMap.ContainsKey(vertex.Content)) {
-        contentMap.Remove(vertex.Content);
-      }
+    public void AddArc(IArc arc) {
+      var source = (Vertex)arc.Source;
+      var target = (Vertex)arc.Target;
+      source.AddArc(arc);
+      target.AddArc(arc);
+      arcs.Add(arc);
     }
 
-    private void Vertex_PostContentChanged(object sender, EventArgs args) {
-      var vertex = (IVertex)sender;
-      if (vertex.Content != null)
-        contentMap.Add(vertex.Content, vertex);
+    public void RemoveArc(IArc arc) {
+      arcs.Remove(arc);
+      var source = (Vertex)arc.Source;
+      var target = (Vertex)arc.Target;
+      source.RemoveArc(arc);
+      target.RemoveArc(arc);
     }
+
+    public event EventHandler VertexAdded;
+    protected virtual void OnVertexAdded(object sender, EventArgs args) {
+      var added = VertexAdded;
+      if (added != null)
+        added(sender, args);
+    }
+
+    public event EventHandler VertexChanged;
+    protected virtual void OnVertexChanged(object sender, EventArgs args) {
+      var changed = VertexChanged;
+      if (changed != null)
+        changed(sender, args);
+    }
+
+    public event EventHandler VertexRemoved;
+    protected virtual void OnVertexRemoved(object sender, EventArgs args) {
+      var removed = VertexRemoved;
+      if (removed != null)
+        removed(sender, args);
+    }
+
+    protected virtual void OnArcAdded(object sender, EventArgs<IArc> args) {
+      var arc = args.Value;
+      // the ArcAdded event is fired by a vertex when an arc from or towards another vertex is added to his list of connections
+      // because the arc is added in both directions by both the source and the target, this event will get fired twice 
+      // here, we only want to add the arc once, so if its already contained, we return without complaining
+      if (arcs.Contains(arc)) return;
+      arcs.Add(arc);
+      arc.Changed += OnArcChanged;
+    }
+
+    protected virtual void OnArcRemoved(object sender, EventArgs<IArc> args) {
+      var arc = args.Value;
+      if (!arcs.Contains(arc)) return; // the same rationale as above 
+      arcs.Remove(arc);
+      arc.Changed -= OnArcChanged;
+    }
+
+    protected virtual void OnArcChanged(object sender, EventArgs args) { }
 
     public override Image ItemImage {
       get { return Common.Resources.VSImageLibrary.Graph; }
     }
-
-    public string ExportDot() {
-      var sb = new StringBuilder();
-      sb.Append("digraph g {");
-      foreach (var v in Vertices) {
-        sb.Append("\"" + v.Id + "\" [label=\"" + v.Label + "\"];" + Environment.NewLine);
-      }
-
-      foreach (var v in Vertices) {
-        foreach (var c in v.OutArcs.Select(x => x.Target)) {
-          sb.Append("\"" + v.Id + "\" -> \"" + c.Id + "\"" + Environment.NewLine);
-        }
-      }
-      sb.Append("}");
-      return sb.ToString();
-    }
   }
 }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IArc.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using HeuristicLab.Core;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public interface IArc {
-    IVertex Source { get; set; }
-    IVertex Target { get; set; }
+  public interface IArc : IItem {
+    event EventHandler Changed; // generic event for when the label, weight or data were changed
+    IVertex Source { get; }
+    IVertex Target { get; }
     string Label { get; set; }
     double Weight { get; set; }
@@ -30 +33 @@
   }
 
-  public interface IArc<T> : IArc where T : class,IVertex {
-    new T Source { get; set; }
-    new T Target { get; set; }
+  public interface IArc<T> : IArc where T : class,IItem {
+    new IVertex<T> Source { get; }
+    new IVertex<T> Target { get; }
   }
 }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IDirectedGraph.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using HeuristicLab.Core;
@@ -26 +25 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public interface IDirectedGraph : IItem {
-    bool Contains(IVertex vertex);
-    bool Any(Func<IVertex, bool> predicate);
     void Clear();
     void AddVertex(IVertex vertex);
     IArc AddArc(IVertex source, IVertex target);
+    void AddArc(IArc arc);
     void RemoveVertex(IVertex vertex);
+    void RemoveArc(IArc arc);
     IEnumerable<IVertex> Vertices { get; }
-    bool Contains(object content);
-    IVertex GetVertex(string id);
-    IVertex GetVertex(object content);
+    IEnumerable<IArc> Arcs { get; }
   }
 }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IVertex.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public interface IVertex : IItem {
-    event EventHandler PreContentChanged;
-    event EventHandler PostContentChanged;
+    event EventHandler Changed; // generic event for when the content, label or weight have changed
+    event EventHandler<EventArgs<IArc>> ArcAdded;
+    event EventHandler<EventArgs<IArc>> ArcRemoved;
 
-    string Id { get; }
-    IEnumerable<IArc> InArcs { get; set; }
-    IEnumerable<IArc> OutArcs { get; set; }
+    IEnumerable<IArc> InArcs { get; }
+    IEnumerable<IArc> OutArcs { get; }
 
     int InDegree { get; }
@@ -40 +41 @@
     double Weight { get; set; }
 
-    void AddForwardArc(IArc arc);
-    void AddReverseArc(IArc arc);
+    object Content { get; set; }
 
-    object Content { get; set; }
+    void AddArc(IArc arc);
+    void RemoveArc(IArc arc);
+    void RemoveArc(IVertex vertex);
   }
 

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Vertex.cs

@@ -30 +30 @@
   [StorableClass]
   public class Vertex : Item, IVertex {
-    public event EventHandler PreContentChanged;
-    protected virtual void OnPreContentChanged(object sender, EventArgs args) {
-      var changed = PreContentChanged;
-      if (changed != null) {
+    // use the same event to signal a change in the content, weight or label
+    public event EventHandler Changed;
+    protected virtual void OnChanged(object sender, EventArgs args) {
+      var changed = Changed;
+      if (changed != null)
         changed(sender, args);
-      }
     }
 
-    public event EventHandler PostContentChanged;
-    protected virtual void OnPostContentChanged(object sender, EventArgs args) {
-      var changed = PostContentChanged;
-      if (changed != null) {
-        changed(sender, args);
+    public event EventHandler<EventArgs<IArc>> ArcAdded;
+    protected virtual void OnArcAdded(object sender, EventArgs<IArc> args) {
+      var added = ArcAdded;
+      if (added != null)
+        added(sender, args);
+    }
+
+    public event EventHandler<EventArgs<IArc>> ArcRemoved;
+    protected virtual void OnArcRemoved(object sender, EventArgs<IArc> args) {
+      var removed = ArcRemoved;
+      if (removed != null)
+        removed(sender, args);
+    }
+
+    [Storable]
+    protected string label;
+    public string Label {
+      get { return label; }
+      set {
+        label = value;
+        OnChanged(this, EventArgs.Empty);
       }
     }
 
     [Storable]
-    private string id;
-
-    public string Id {
-      get { return id; }
+    protected double weight;
+    public double Weight {
+      get { return weight; }
+      set {
+        weight = value;
+        OnChanged(this, EventArgs.Empty);
+      }
     }
-
-    [Storable]
-    public string Label { get; set; }
-
-    [Storable]
-    public double Weight { get; set; }
 
     [Storable]
@@ -64 +77 @@
       get { return content; }
       set {
-        OnPreContentChanged(this, EventArgs.Empty);
         content = value;
-        OnPostContentChanged(this, EventArgs.Empty);
+        OnChanged(this, EventArgs.Empty);
       }
     }
@@ -73 +85 @@
     public IEnumerable<IArc> InArcs {
       get { return inArcs ?? Enumerable.Empty<IArc>(); }
-      set { inArcs = value.ToList(); }
     }
 
@@ -79 +90 @@
     public IEnumerable<IArc> OutArcs {
       get { return outArcs ?? Enumerable.Empty<IArc>(); }
-      set { outArcs = value.ToList(); }
     }
 
@@ -85 +95 @@
     public Vertex(bool deserializing) : base(deserializing) { }
 
-    public Vertex() {
-      id = Guid.NewGuid().ToString();
-    }
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() { }
+
+    private Vertex() { }
 
     public Vertex(object content)
@@ -96 +107 @@
     protected Vertex(Vertex original, Cloner cloner)
       : base(original, cloner) {
-      id = Guid.NewGuid().ToString();
       content = original.content;
-      Label = original.Label;
-      Weight = original.Weight;
-      inArcs = new List<IArc>(original.inArcs);
-      outArcs = new List<IArc>(original.outArcs);
+      label = original.Label;
+      weight = original.Weight;
+
+      inArcs = original.InArcs.Select(cloner.Clone).ToList();
+      outArcs = original.OutArcs.Select(cloner.Clone).ToList();
     }
 
@@ -108 +119 @@
     }
 
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      if (Id == null) {
-        id = Guid.NewGuid().ToString();
+    public void AddArc(IArc arc) {
+      if (this != arc.Source && this != arc.Target)
+        throw new InvalidOperationException("The current vertex must be either the arc source or the arc target.");
+
+      if (this == arc.Source) {
+        if (outArcs == null)
+          outArcs = new List<IArc>();
+        else if (outArcs.Contains(arc) || outArcs.Any(a => a.Target == arc.Target && a.Source == arc.Source))
+          throw new InvalidOperationException("Arc already added.");
+        outArcs.Add(arc);
+      } else if (this == arc.Target) {
+        if (inArcs == null)
+          inArcs = new List<IArc>();
+        else if (inArcs.Contains(arc) || inArcs.Any(a => a.Target == arc.Target && a.Source == arc.Source))
+          throw new InvalidOperationException("Arc already added.");
+        inArcs.Add(arc);
+      }
+      OnArcAdded(this, new EventArgs<IArc>(arc));
+    }
+
+    public void RemoveArc(IVertex vertex) {
+      try {
+        var arc = inArcs.Concat(outArcs).SingleOrDefault(x => x.Target == vertex || x.Source == vertex);
+        RemoveArc(arc);
+      }
+      catch (Exception) {
+        throw new InvalidOperationException("Only one arc allowed between two vertices");
       }
     }
 
-    // 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(IArc arc) {
-      if (arc.Source != this) { throw new Exception("AddForwardArc: Source should be equal to this."); }
-      if (outArcs == null)
-        outArcs = new List<IArc>();
-      outArcs.Add(arc);
+    public void RemoveArc(IArc arc) {
+      if (this != arc.Source && this != arc.Target)
+        throw new InvalidOperationException("The current vertex must be either the arc source or the arc target.");
+
+      if (this == arc.Source && outArcs != null) {
+        if (!outArcs.Remove(arc))
+          throw new InvalidOperationException("Arc is not present in this vertex' outgoing arcs.");
+      } else if (this == arc.Target && inArcs != null) {
+        if (!inArcs.Remove(arc))
+          throw new InvalidOperationException("Arc is not present in this vertex' incoming arcs.");
+      }
+      OnArcRemoved(this, new EventArgs<IArc>(arc));
     }
-    public void AddReverseArc(IArc arc) {
-      if (arc.Target != this) { throw new Exception("AddReverseArc: Target should be equal to this."); };
-      if (inArcs == null)
-        inArcs = new List<IArc>();
-      inArcs.Add(arc);
-    }
+
     public int InDegree { get { return InArcs.Count(); } }
     public int OutDegree { get { return OutArcs.Count(); } }
@@ -141 +174 @@
       set { base.Content = value; }
     }
-
-    public Vertex() { }
 
     [StorableConstructor]