Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/09/14 16:40:29 (10 years ago)
Author:
bburlacu
Message:

#1772: Added fix to improve accuracy of bottom-up tree distance.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

    r11023 r11165  
    2626using System.Linq;
    2727using System.Text;
     28using System.Text.RegularExpressions;
    2829using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2930using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
     
    3637  /// </summary>
    3738  public static class BottomUpDistanceCalculator {
     39    /// <summary>
     40    /// Creates a compact representation of the two trees as a directed acyclic graph
     41    /// </summary>
     42    /// <param name="t1">The first tree</param>
     43    /// <param name="t2">The second tree</param>
     44    /// <returns>The compacted DAG representing the two trees</returns>
    3845    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    3946      var G = new DirectedGraph();
     
    7986            if (V.SequenceEqual(W)) {
    8087              K[v] = w;
     88              //              // merge vertices
     89              //              foreach (var a in K[v].InArcs) {
     90              //                a.Target = w;
     91              //              }
     92              //              G.RemoveVertex(K[v]);
     93
    8194              found = true;
    8295              break;
     
    148161      var K = Compact(t1, t2);
    149162      var M = Mapping(t1, t2, K);
     163
     164      var keys = M.Keys.ToList();
     165      for (int j = 0; j < keys.Count; ++j) {
     166        var key = keys[j];
     167        var value = M[key];
     168        if (key.Parent != null && value.Parent != null && !M.ContainsKey(key.Parent) && Label(key.Parent).Equals(Label(value.Parent))) {
     169          M.Add(key.Parent, value.Parent);
     170          keys.Add(key.Parent);
     171        }
     172      }
     173
    150174      int d = t1.Length - M.Count;
    151175      int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
     
    185209
    186210      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
    187         get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
    188       }
     211        get {
     212          var r1 = Item1.Root;
     213          var r2 = Item2.Root;
     214
     215          var virtualRootSymbol = new StartSymbol();
     216          var virtualRootNode = virtualRootSymbol.CreateTreeNode();
     217          virtualRootNode.AddSubtree(r1);
     218          virtualRootNode.AddSubtree(r2);
     219
     220          var nodes = virtualRootNode.IterateNodesPostfix().ToList();
     221
     222          virtualRootNode.RemoveSubtree(0);
     223          virtualRootNode.RemoveSubtree(0);
     224
     225          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
     226        }
     227      }
     228    }
     229
     230    public static string RemoveFirstLines(string text, int linesCount) {
     231      var lines = Regex.Split(text, "\r\n|\r|\n").Skip(linesCount);
     232      return string.Join(Environment.NewLine, lines.ToArray());
    189233    }
    190234
     
    198242      var m2 = formatter.Format(t2, out s2, 20);
    199243
     244      // skip first 6 lines of s2
     245      s2 = RemoveFirstLines(s2, 6);
     246
    200247      sb.Append(s1);
    201248      sb.Append(s2);
Note: See TracChangeset for help on using the changeset viewer.