Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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
Files:
9 edited

Legend:

Unmodified
Added
Removed

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

    r11211 r11229  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2627namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2728  /// <summary>
    28   /// An arc that can have a weight, a label, and can old additional information in the Data object
     29  /// An arc that can have a weight, a label, and a data object for holding additional info
    2930  /// </summary>
    3031  [StorableClass]
    3132  public class Arc : Item, IArc {
    32     [Storable]
    33     public IVertex Source { get; set; }
     33    public event EventHandler Changed;
     34    protected virtual void OnChanged(object sender, EventArgs args) {
     35      var changed = Changed;
     36      if (changed != null)
     37        changed(sender, args);
     38    }
    3439
    3540    [Storable]
    36     public IVertex Target { get; set; }
     41    public IVertex Source { get; private set; }
    3742
    3843    [Storable]
    39     public string Label { get; set; }
     44    public IVertex Target { get; private set; }
    4045
    4146    [Storable]
    42     public double Weight { get; set; }
     47    protected string label;
     48    public string Label {
     49      get { return label; }
     50      set {
     51        label = value;
     52        OnChanged(this, EventArgs.Empty);
     53      }
     54    }
    4355
    4456    [Storable]
    45     public object Data { get; set; }
     57    protected double weight;
     58    public double Weight {
     59      get { return weight; }
     60      set {
     61        weight = value;
     62        OnChanged(this, EventArgs.Empty);
     63      }
     64    }
     65
     66    [Storable]
     67    protected object data;
     68    public object Data {
     69      get { return data; }
     70      set {
     71        data = value;
     72        OnChanged(this, EventArgs.Empty);
     73      }
     74    }
    4675
    4776    [StorableConstructor]
    4877    public Arc(bool deserializing) : base(deserializing) { }
    49 
    50     public override IDeepCloneable Clone(Cloner cloner) {
    51       return new Arc(this, cloner);
    52     }
    53     public Arc() { }
    5478
    5579    public Arc(IVertex source, IVertex target) {
    … …  
    6084    protected Arc(Arc original, Cloner cloner)
    6185      : base(original, cloner) {
    62       Source = original.Source;
    63       Target = original.Target;
    64       Label = original.Label;
    65       Weight = original.Weight;
    66       Data = original.Data;
     86      Source = cloner.Clone(original.Source);
     87      Target = cloner.Clone(original.Target);
     88      label = original.Label;
     89      weight = original.Weight;
     90      data = original;
     91    }
     92
     93    public override IDeepCloneable Clone(Cloner cloner) {
     94      return new Arc(this, cloner);
     95    }
     96  }
     97
     98  [StorableClass]
     99  public class Arc<T> : Arc, IArc<T> where T : class,IItem {
     100    public Arc(bool deserializing)
     101      : base(deserializing) {
     102    }
     103
     104    public Arc(IVertex source, IVertex target)
     105      : base(source, target) {
     106    }
     107
     108    protected Arc(Arc original, Cloner cloner)
     109      : base(original, cloner) {
     110    }
     111
     112    new public IVertex<T> Source {
     113      get { return (IVertex<T>)base.Source; }
     114    }
     115    new public IVertex<T> Target {
     116      get { return (IVertex<T>)base.Target; }
    67117    }
    68118  }

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

    r11211 r11229  
    2424using System.Drawing;
    2525using System.Linq;
    26 using System.Text;
    2726using HeuristicLab.Common;
    2827using HeuristicLab.Core;
    … …  
    3332  [StorableClass]
    3433  public class DirectedGraph : Item, IDirectedGraph {
    35     public bool AllowDuplicateContent { get; set; }
    36 
     34    protected HashSet<IVertex> vertices;
    3735    [Storable]
    38     protected readonly List<IVertex> vertices; // for performance reasons, maybe this should be a linked list (fast remove)
    3936    public IEnumerable<IVertex> Vertices {
    4037      get { return vertices; }
     38      private set { vertices = new HashSet<IVertex>(value); }
    4139    }
    4240
     41    protected HashSet<IArc> arcs;
    4342    [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;
    5143    public IEnumerable<IArc> Arcs {
    5244      get { return arcs; }
     45      private set { arcs = new HashSet<IArc>(value); }
    5346    }
    5447
    … …  
    6053    [StorableHook(HookType.AfterDeserialization)]
    6154    private void AfterDeserialization() {
    62       foreach (var arc in arcs) {
    63         arc.Source.AddForwardArc(arc);
    64         arc.Target.AddReverseArc(arc);
     55      foreach (var vertex in vertices) {
     56        vertex.ArcAdded += OnArcAdded;
     57        vertex.ArcRemoved += OnArcRemoved;
     58        vertex.Changed += OnVertexChanged;
    6559      }
    6660
    67       foreach (var vertex in vertices) {
    68         vertex.PreContentChanged += Vertex_PreContentChanged;
    69         vertex.PostContentChanged += Vertex_PostContentChanged;
     61      foreach (var arc in arcs) {
     62        var source = arc.Source;
     63        var target = arc.Target;
     64        source.AddArc(arc);
     65        target.AddArc(arc);
     66        arc.Changed += OnArcChanged;
    7067      }
    7168    }
    7269
    7370    public DirectedGraph() {
    74       vertices = new List<IVertex>();
    75       arcs = new List<IArc>();
    76       contentMap = new Dictionary<object, IVertex>();
    77       idMap = new Dictionary<string, IVertex>();
     71      vertices = new HashSet<IVertex>();
     72      arcs = new HashSet<IArc>();
    7873    }
    7974
    8075    protected DirectedGraph(DirectedGraph original, Cloner cloner)
    8176      : 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);
     77      vertices = new HashSet<IVertex>(original.vertices.Select(cloner.Clone));
     78      arcs = new HashSet<IArc>(original.arcs.Select(cloner.Clone));
    8679    }
    8780
    … …  
    9083    }
    9184
    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 
    12085    public virtual void Clear() {
    12186      vertices.Clear();
    122       contentMap.Clear();
    123       idMap.Clear();
     87      arcs.Clear();
    12488    }
    12589
    12690    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);
    13491      vertices.Add(vertex);
    135 
    136       vertex.PreContentChanged += Vertex_PreContentChanged;
    137       vertex.PostContentChanged += Vertex_PostContentChanged;
     92      // register event handlers
     93      vertex.Changed += OnVertexChanged;
     94      vertex.ArcAdded += OnArcAdded;
     95      vertex.ArcRemoved += OnArcRemoved;
     96      OnVertexAdded(this, EventArgs.Empty);
    13897    }
    13998
    14099    public virtual void RemoveVertex(IVertex vertex) {
    141       contentMap.Remove(vertex.Content);
    142       idMap.Remove(vertex.Id);
    143100      vertices.Remove(vertex);
    144 
    145101      // 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;
     102      foreach (var arc in vertex.InArcs.Concat(vertex.OutArcs))
     103        RemoveArc(arc);
     104      // deregister event handlers
     105      vertex.ArcAdded -= OnArcAdded;
     106      vertex.ArcRemoved -= OnArcRemoved;
     107      vertex.Changed -= OnVertexChanged;
     108      OnVertexRemoved(this, EventArgs.Empty);
    155109    }
    156110
    157     public virtual IArc AddArc(IVertex source, IVertex target) {
     111    public IArc AddArc(IVertex source, IVertex target) {
    158112      var arc = new Arc(source, target);
    159       source.AddForwardArc(arc);
    160       target.AddReverseArc(arc);
    161       arcs.Add(arc);
     113      AddArc(arc);
    162114      return arc;
    163115    }
    164116
    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       }
     117    public void AddArc(IArc arc) {
     118      var source = (Vertex)arc.Source;
     119      var target = (Vertex)arc.Target;
     120      source.AddArc(arc);
     121      target.AddArc(arc);
     122      arcs.Add(arc);
    170123    }
    171124
    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);
     125    public void RemoveArc(IArc arc) {
     126      arcs.Remove(arc);
     127      var source = (Vertex)arc.Source;
     128      var target = (Vertex)arc.Target;
     129      source.RemoveArc(arc);
     130      target.RemoveArc(arc);
    176131    }
     132
     133    public event EventHandler VertexAdded;
     134    protected virtual void OnVertexAdded(object sender, EventArgs args) {
     135      var added = VertexAdded;
     136      if (added != null)
     137        added(sender, args);
     138    }
     139
     140    public event EventHandler VertexChanged;
     141    protected virtual void OnVertexChanged(object sender, EventArgs args) {
     142      var changed = VertexChanged;
     143      if (changed != null)
     144        changed(sender, args);
     145    }
     146
     147    public event EventHandler VertexRemoved;
     148    protected virtual void OnVertexRemoved(object sender, EventArgs args) {
     149      var removed = VertexRemoved;
     150      if (removed != null)
     151        removed(sender, args);
     152    }
     153
     154    protected virtual void OnArcAdded(object sender, EventArgs<IArc> args) {
     155      var arc = args.Value;
     156      // the ArcAdded event is fired by a vertex when an arc from or towards another vertex is added to his list of connections
     157      // because the arc is added in both directions by both the source and the target, this event will get fired twice
     158      // here, we only want to add the arc once, so if its already contained, we return without complaining
     159      if (arcs.Contains(arc)) return;
     160      arcs.Add(arc);
     161      arc.Changed += OnArcChanged;
     162    }
     163
     164    protected virtual void OnArcRemoved(object sender, EventArgs<IArc> args) {
     165      var arc = args.Value;
     166      if (!arcs.Contains(arc)) return; // the same rationale as above
     167      arcs.Remove(arc);
     168      arc.Changed -= OnArcChanged;
     169    }
     170
     171    protected virtual void OnArcChanged(object sender, EventArgs args) { }
    177172
    178173    public override Image ItemImage {
    179174      get { return Common.Resources.VSImageLibrary.Graph; }
    180175    }
    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     }
    197176  }
    198177}

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

    r11211 r11229  
    2020#endregion
    2121
     22using System;
     23using HeuristicLab.Core;
    2224
    2325namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    24   public interface IArc {
    25     IVertex Source { get; set; }
    26     IVertex Target { get; set; }
     26  public interface IArc : IItem {
     27    event EventHandler Changed; // generic event for when the label, weight or data were changed
     28    IVertex Source { get; }
     29    IVertex Target { get; }
    2730    string Label { get; set; }
    2831    double Weight { get; set; }
    … …  
    3033  }
    3134
    32   public interface IArc<T> : IArc where T : class,IVertex {
    33     new T Source { get; set; }
    34     new T Target { get; set; }
     35  public interface IArc<T> : IArc where T : class,IItem {
     36    new IVertex<T> Source { get; }
     37    new IVertex<T> Target { get; }
    3538  }
    3639}

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

    r11211 r11229  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    2423using HeuristicLab.Core;
    … …  
    2625namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2726  public interface IDirectedGraph : IItem {
    28     bool Contains(IVertex vertex);
    29     bool Any(Func<IVertex, bool> predicate);
    3027    void Clear();
    3128    void AddVertex(IVertex vertex);
    3229    IArc AddArc(IVertex source, IVertex target);
     30    void AddArc(IArc arc);
    3331    void RemoveVertex(IVertex vertex);
     32    void RemoveArc(IArc arc);
    3433    IEnumerable<IVertex> Vertices { get; }
    35     bool Contains(object content);
    36     IVertex GetVertex(string id);
    37     IVertex GetVertex(object content);
     34    IEnumerable<IArc> Arcs { get; }
    3835  }
    3936}

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

    r11211 r11229  
    2222using System;
    2323using System.Collections.Generic;
     24using HeuristicLab.Common;
    2425using HeuristicLab.Core;
    2526
    2627namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2728  public interface IVertex : IItem {
    28     event EventHandler PreContentChanged;
    29     event EventHandler PostContentChanged;
     29    event EventHandler Changed; // generic event for when the content, label or weight have changed
     30    event EventHandler<EventArgs<IArc>> ArcAdded;
     31    event EventHandler<EventArgs<IArc>> ArcRemoved;
    3032
    31     string Id { get; }
    32     IEnumerable<IArc> InArcs { get; set; }
    33     IEnumerable<IArc> OutArcs { get; set; }
     33    IEnumerable<IArc> InArcs { get; }
     34    IEnumerable<IArc> OutArcs { get; }
    3435
    3536    int InDegree { get; }
    … …  
    4041    double Weight { get; set; }
    4142
    42     void AddForwardArc(IArc arc);
    43     void AddReverseArc(IArc arc);
     43    object Content { get; set; }
    4444
    45     object Content { get; set; }
     45    void AddArc(IArc arc);
     46    void RemoveArc(IArc arc);
     47    void RemoveArc(IVertex vertex);
    4648  }
    4749

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

    r11211 r11229  
    3030  [StorableClass]
    3131  public class Vertex : Item, IVertex {
    32     public event EventHandler PreContentChanged;
    33     protected virtual void OnPreContentChanged(object sender, EventArgs args) {
    34       var changed = PreContentChanged;
    35       if (changed != null) {
     32    // use the same event to signal a change in the content, weight or label
     33    public event EventHandler Changed;
     34    protected virtual void OnChanged(object sender, EventArgs args) {
     35      var changed = Changed;
     36      if (changed != null)
    3637        changed(sender, args);
    37       }
    3838    }
    3939
    40     public event EventHandler PostContentChanged;
    41     protected virtual void OnPostContentChanged(object sender, EventArgs args) {
    42       var changed = PostContentChanged;
    43       if (changed != null) {
    44         changed(sender, args);
     40    public event EventHandler<EventArgs<IArc>> ArcAdded;
     41    protected virtual void OnArcAdded(object sender, EventArgs<IArc> args) {
     42      var added = ArcAdded;
     43      if (added != null)
     44        added(sender, args);
     45    }
     46
     47    public event EventHandler<EventArgs<IArc>> ArcRemoved;
     48    protected virtual void OnArcRemoved(object sender, EventArgs<IArc> args) {
     49      var removed = ArcRemoved;
     50      if (removed != null)
     51        removed(sender, args);
     52    }
     53
     54    [Storable]
     55    protected string label;
     56    public string Label {
     57      get { return label; }
     58      set {
     59        label = value;
     60        OnChanged(this, EventArgs.Empty);
    4561      }
    4662    }
    4763
    4864    [Storable]
    49     private string id;
    50 
    51     public string Id {
    52       get { return id; }
     65    protected double weight;
     66    public double Weight {
     67      get { return weight; }
     68      set {
     69        weight = value;
     70        OnChanged(this, EventArgs.Empty);
     71      }
    5372    }
    54 
    55     [Storable]
    56     public string Label { get; set; }
    57 
    58     [Storable]
    59     public double Weight { get; set; }
    6073
    6174    [Storable]
    … …  
    6477      get { return content; }
    6578      set {
    66         OnPreContentChanged(this, EventArgs.Empty);
    6779        content = value;
    68         OnPostContentChanged(this, EventArgs.Empty);
     80        OnChanged(this, EventArgs.Empty);
    6981      }
    7082    }
    … …  
    7385    public IEnumerable<IArc> InArcs {
    7486      get { return inArcs ?? Enumerable.Empty<IArc>(); }
    75       set { inArcs = value.ToList(); }
    7687    }
    7788
    … …  
    7990    public IEnumerable<IArc> OutArcs {
    8091      get { return outArcs ?? Enumerable.Empty<IArc>(); }
    81       set { outArcs = value.ToList(); }
    8292    }
    8393
    … …  
    8595    public Vertex(bool deserializing) : base(deserializing) { }
    8696
    87     public Vertex() {
    88       id = Guid.NewGuid().ToString();
    89     }
     97    [StorableHook(HookType.AfterDeserialization)]
     98    private void AfterDeserialization() { }
     99
     100    private Vertex() { }
    90101
    91102    public Vertex(object content)
    … …  
    96107    protected Vertex(Vertex original, Cloner cloner)
    97108      : base(original, cloner) {
    98       id = Guid.NewGuid().ToString();
    99109      content = original.content;
    100       Label = original.Label;
    101       Weight = original.Weight;
    102       inArcs = new List<IArc>(original.inArcs);
    103       outArcs = new List<IArc>(original.outArcs);
     110      label = original.Label;
     111      weight = original.Weight;
     112
     113      inArcs = original.InArcs.Select(cloner.Clone).ToList();
     114      outArcs = original.OutArcs.Select(cloner.Clone).ToList();
    104115    }
    105116
    … …  
    108119    }
    109120
    110     [StorableHook(HookType.AfterDeserialization)]
    111     private void AfterDeserialization() {
    112       if (Id == null) {
    113         id = Guid.NewGuid().ToString();
     121    public void AddArc(IArc arc) {
     122      if (this != arc.Source && this != arc.Target)
     123        throw new InvalidOperationException("The current vertex must be either the arc source or the arc target.");
     124
     125      if (this == arc.Source) {
     126        if (outArcs == null)
     127          outArcs = new List<IArc>();
     128        else if (outArcs.Contains(arc) || outArcs.Any(a => a.Target == arc.Target && a.Source == arc.Source))
     129          throw new InvalidOperationException("Arc already added.");
     130        outArcs.Add(arc);
     131      } else if (this == arc.Target) {
     132        if (inArcs == null)
     133          inArcs = new List<IArc>();
     134        else if (inArcs.Contains(arc) || inArcs.Any(a => a.Target == arc.Target && a.Source == arc.Source))
     135          throw new InvalidOperationException("Arc already added.");
     136        inArcs.Add(arc);
     137      }
     138      OnArcAdded(this, new EventArgs<IArc>(arc));
     139    }
     140
     141    public void RemoveArc(IVertex vertex) {
     142      try {
     143        var arc = inArcs.Concat(outArcs).SingleOrDefault(x => x.Target == vertex || x.Source == vertex);
     144        RemoveArc(arc);
     145      }
     146      catch (Exception) {
     147        throw new InvalidOperationException("Only one arc allowed between two vertices");
    114148      }
    115149    }
    116150
    117     // this method can be used to add arcs towards targets that are not visible in the graph
    118     // (they do not appear in the nodes Dictionary). It is the programmers responsibility to
    119     // enforce the correct and desired behavior.
    120     public void AddForwardArc(IArc arc) {
    121       if (arc.Source != this) { throw new Exception("AddForwardArc: Source should be equal to this."); }
    122       if (outArcs == null)
    123         outArcs = new List<IArc>();
    124       outArcs.Add(arc);
     151    public void RemoveArc(IArc arc) {
     152      if (this != arc.Source && this != arc.Target)
     153        throw new InvalidOperationException("The current vertex must be either the arc source or the arc target.");
     154
     155      if (this == arc.Source && outArcs != null) {
     156        if (!outArcs.Remove(arc))
     157          throw new InvalidOperationException("Arc is not present in this vertex' outgoing arcs.");
     158      } else if (this == arc.Target && inArcs != null) {
     159        if (!inArcs.Remove(arc))
     160          throw new InvalidOperationException("Arc is not present in this vertex' incoming arcs.");
     161      }
     162      OnArcRemoved(this, new EventArgs<IArc>(arc));
    125163    }
    126     public void AddReverseArc(IArc arc) {
    127       if (arc.Target != this) { throw new Exception("AddReverseArc: Target should be equal to this."); };
    128       if (inArcs == null)
    129         inArcs = new List<IArc>();
    130       inArcs.Add(arc);
    131     }
     164
    132165    public int InDegree { get { return InArcs.Count(); } }
    133166    public int OutDegree { get { return OutArcs.Count(); } }
    … …  
    141174      set { base.Content = value; }
    142175    }
    143 
    144     public Vertex() { }
    145176
    146177    [StorableConstructor]

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs

    r10562 r11229  
    22using System.Collections.Generic;
    33
    4 namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Matching {
     4namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    55  public class MaxCommonSequenceCalculator<T, U>
    66    where T : class

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11225 r11229  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Drawing;
    25 using System.Globalization;
    2624using System.Linq;
    27 using System.Text;
    2825using HeuristicLab.Common;
    2926using HeuristicLab.Core;
    3027using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    31 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
    3228using HeuristicLab.Optimization.Operators;
    3329using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    7874
    7975      // visit nodes in order of decreasing height to ensure correct mapping
    80       foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Weight)) {
     76      foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Depth)) {
    8177        if (forwardMap.ContainsKey(v))
    8278          continue;
    … …  
    115111    /// Creates a compact representation of the two trees as a directed acyclic graph
    116112    /// </summary>
    117     /// <param name="t1">The first tree</param>
    118     /// <param name="t2">The second tree</param>
     113    /// <param name="n1">The root of the first tree</param>
     114    /// <param name="n2">The root of the second tree</param>
    119115    /// <returns>The compacted DAG representing the two trees</returns>
    120     private Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
    121       var nodesToVertices = new Dictionary<ISymbolicExpressionTreeNode, IVertex>(); // K
    122       var labelsToVertices = new Dictionary<string, IVertex>(); // L
     116    private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
     117      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
     118      var labelMap = new Dictionary<string, GraphNode>(); // L
    123119      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
    124       var vertices = new List<IVertex>(); // G
    125120
    126121      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
     122      var list = new List<GraphNode>();
    127123      var queue = new Queue<ISymbolicExpressionTreeNode>();
    128124
    … …  
    130126        if (n.SubtreeCount == 0) {
    131127          var label = n.ToString();
    132           if (!labelsToVertices.ContainsKey(label)) {
    133             var z = new Vertex { Content = n, Label = label };
    134             labelsToVertices[z.Label] = z;
    135             vertices.Add(z);
    136           }
    137           nodesToVertices[n] = labelsToVertices[label];
     128          if (!labelMap.ContainsKey(label)) {
     129            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
     130            labelMap[z.Label] = z;
     131            list.Add(z);
     132          }
     133          nodeMap[n] = labelMap[label];
    138134          queue.Enqueue(n);
    139135        } else {
    … …  
    141137        }
    142138      }
    143 
    144139      while (queue.Any()) {
    145         var v = queue.Dequeue();
    146 
    147         if (v.SubtreeCount > 0) {
    148           var label = v.Symbol.Name;
     140        var n = queue.Dequeue();
     141
     142        if (n.SubtreeCount > 0) {
     143          var label = n.Symbol.Name;
    149144          bool found = false;
    150           var height = v.GetDepth();
     145          var depth = n.GetDepth();
    151146
    152147          bool sort = commutativeSymbols.Contains(label);
    153           var vSubtrees = v.Subtrees.Select(x => nodesToVertices[x]).ToList();
    154           if (sort) vSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
    155 
    156           // for all nodes w in G in reverse order
    157           for (int i = vertices.Count - 1; i >= 0; --i) {
    158             var w = vertices[i];
    159             var n = (ISymbolicExpressionTreeNode)w.Content;
    160             if (v.SubtreeCount != n.SubtreeCount || label != w.Label || height != (int)w.Weight)
     148          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
     149          if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     150
     151          for (int i = list.Count - 1; i >= 0; --i) {
     152            var w = list[i];
     153
     154            if (!(n.SubtreeCount == w.ChildrenCount && label == w.Label && depth == w.Depth))
    161155              continue;
    162156
    163157            // sort V and W when the symbol is commutative because we are dealing with unordered trees
    164             var wSubtrees = n.Subtrees.Select(x => nodesToVertices[x]).ToList();
    165             if (sort) wSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
    166 
    167             if (vSubtrees.SequenceEqual(wSubtrees)) {
    168               nodesToVertices[v] = w;
     158            var m = w.SymbolicExpressionTreeNode;
     159            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
     160            if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     161
     162            if (nNodes.SequenceEqual(mNodes)) {
     163              nodeMap[n] = w;
    169164              found = true;
    170165              break;
    171166            }
    172           } // 32: end for
     167          }
    173168
    174169          if (!found) {
    175             var w = new Vertex { Content = v, Label = label, Weight = height };
    176             vertices.Add(w);
    177             nodesToVertices[v] = w;
    178 
    179             foreach (var u in v.Subtrees) {
    180               AddArc(w, nodesToVertices[u]);
    181             } // 40: end for
    182           } // 41: end if
    183         } // 42: end if
    184 
    185         var p = v.Parent;
     170            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
     171            list.Add(w);
     172            nodeMap[n] = w;
     173          }
     174        }
     175
     176        var p = n.Parent;
    186177        if (p == null)
    187178          continue;
    … …  
    193184      }
    194185
    195       return nodesToVertices;
     186      return nodeMap;
    196187    }
    197188
    … …  
    202193        var n = list[i];
    203194        if (n.SubtreeCount > 0) {
    204           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(s => s.ToString()) : n.Subtrees;
     195          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
    205196          list.AddRange(subtrees);
    206197        }
    … …  
    210201    }
    211202
    212     private static IArc AddArc(IVertex source, IVertex target) {
    213       var arc = new Arc(source, target);
    214       source.AddForwardArc(arc);
    215       target.AddReverseArc(arc);
    216       return arc;
    217     }
    218 
    219     // debugging
    220     private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
    221       var symbolNameMap = new Dictionary<string, string>
    222     {
    223       {"ProgramRootSymbol", "Prog"},
    224       {"StartSymbol","RPB"},
    225       {"Multiplication", "$\\times$"},
    226       {"Division", "$\\div$"},
    227       {"Addition", "$+$"},
    228       {"Subtraction", "$-$"},
    229       {"Exponential", "$\\exp$"},
    230       {"Logarithm", "$\\log$"}
    231     };
    232 
    233       var sb = new StringBuilder();
    234       var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
    235       int offset = 0;
    236       var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
    237       var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
    238 
    239       double ws = 0.5;
    240       double hs = 0.5;
    241 
    242       var nl = Environment.NewLine;
    243       sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
    244                  "\\usepackage{tikz}" + nl +
    245                  "\\begin{document}" + nl +
    246                  "\\begin{tikzpicture}" + nl +
    247                  "\\def\\ws{1}" + nl +
    248                  "\\def\\hs{0.7}" + nl +
    249                  "\\def\\offs{" + offset + "}" + nl);
    250 
    251       foreach (var node in t1.IterateNodesBreadth()) {
    252         var id = Guid.NewGuid().ToString();
    253         nodeIds[node] = id;
    254         var coord = nodeCoordinates[node];
    255         var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
    256         sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
    257       }
    258 
    259       foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
    260         var n = t;
    261         foreach (var s in t.Subtrees) {
    262           sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
    263         }
    264       }
    265 
    266       nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
    267 
    268       offset = 20;
    269       sb.Append("\\def\\offs{" + offset + "}" + nl);
    270       foreach (var node in t2.IterateNodesBreadth()) {
    271         var id = Guid.NewGuid().ToString();
    272         nodeIds[node] = id;
    273         var coord = nodeCoordinates[node];
    274         var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
    275         sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
    276       }
    277 
    278       foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
    279         var n = t;
    280         foreach (var s in t.Subtrees) {
    281           sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
    282         }
    283       }
    284 
    285       foreach (var p in map) {
    286         var id1 = nodeIds[p.Key];
    287         var id2 = nodeIds[p.Value];
    288 
    289         sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
    290       }
    291       sb.Append("\\end{tikzpicture}" + nl +
    292                 "\\end{document}" + nl);
    293       return sb.ToString();
    294     }
    295 
    296     private static string EscapeLatexString(string s) {
    297       return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
     203    private class GraphNode {
     204      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
     205      public string Label;
     206      public int Depth;
     207      public int ChildrenCount;
    298208    }
    299209  }

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs

    r11225 r11229  
    4747      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ (variable 2.4691 X7) -4.3072) (exp 2.1033)))", 4);
    4848
    49       var expr1 = "(* (- 1.2175e+1 (+ (/ (exp -1.4134e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (log 1.3011e+1))";
    50       var expr2 = "(* (- 1.2175e+1 (+ (/ (/ (+ (variable 3.0140 X9) (variable 1.3430 X8)) -1.0864e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (exp (variable 4.0899e-1 X7)))";
     49      const string expr1 = "(* (- 1.2175e+1 (+ (/ (exp -1.4134e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (log 1.3011e+1))";
     50      const string expr2 = "(* (- 1.2175e+1 (+ (/ (/ (+ (variable 3.0140 X9) (variable 1.3430 X8)) -1.0864e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (exp (variable 4.0899e-1 X7)))";
    5151
    5252      TestMatchedNodes(expr1, expr2, 23);
Note: See TracChangeset for help on using the changeset viewer.