Changeset 11023


Ignore:
Timestamp:
06/17/14 10:30:25 (5 years ago)
Author:
bburlacu
Message:

#1772: Small cosmetic changes in BottomUpDistanceCalculator.cs

File:
1 edited

Legend:

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

    r11021 r11023  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    3131
    3232namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
     33  /// <summary>
     34  /// This class implements the bottom-up tree distance described in the following paper:
     35  /// G. Valiente, "An Efficient Bottom-up Distance Between Trees", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.7958
     36  /// </summary>
    3337  public static class BottomUpDistanceCalculator {
    3438    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     
    4145      var nodes = F.Nodes.ToList();
    4246
     47      // for all leaf labels l in F
    4348      foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) {
    4449        var label = Label(l);
     
    4954
    5055      var Q = new Queue<ISymbolicExpressionTreeNode>();
     56
     57      // for all nodes
    5158      foreach (var v in nodes) {
    5259        Children[v] = v.SubtreeCount;
     
    6269        } else {
    6370          bool found = false;
    64 
     71          // for all nodes w in G in reverse order
    6572          foreach (var w in G.Vertices.Reverse()) {
    66             if (Height(v) != Height(w))
     73            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
    6774              break;
    68             if (v.SubtreeCount != w.OutDegree)
    69               break;
    70             if (Label(v) != w.Label)
    71               break;
    72 
     75
     76            // sort V and W because we are dealing with unordered trees
    7377            var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
    7478            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
     
    9195        } // 42: end if
    9296
    93         if (v.Parent == null) continue;
    94         var p = v.Parent;
    95         Children[p]--;
    96         if (Children[p] == 0)
    97           Q.Enqueue(p);
     97        if (v.Parent != null) {
     98          var p = v.Parent;
     99          Children[p]--;
     100          if (Children[p] == 0)
     101            Q.Enqueue(p);
     102        }
    98103      };
    99104
     
    118123            if (!M_.ContainsKey(u)) {
    119124              w = u;
     125              // commented out test below since we are dealing with unordered trees
    120126              //              if (plist2.IndexOf(u) < pw) {
    121127              //                w = u;
     
    183189    }
    184190
    185     // draw the mapping between t1 and t2
     191    // draw the mapping between t1 and t2 as a tikz picture
    186192    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
    187193      var formatter = new SymbolicExpressionTreeLatexFormatter();
Note: See TracChangeset for help on using the changeset viewer.