Changeset 11488


Ignore:
Timestamp:
10/22/14 19:20:30 (8 years ago)
Author:
bburlacu
Message:

#1772: Merged changes from the BottomUpSimilarityCalculator branch.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.csmergedeligible
      /branches/Benchmarking/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs6917-7005
      /branches/CloningRefactoring/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs4656-4721
      /branches/DataAnalysis Refactoring/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5471-5473
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5815-6180
      /branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10598
      /branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs4458-4459,​4462,​4464
      /branches/DataPreprocessing/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10085-11101
      /branches/ExportSymbolicDataAnalysisSolutions/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs9511-9585
      /branches/GP.Grammar.Editor/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs6284-6795
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5060
      /branches/HLScript/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10331-10358
      /branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpTreeSimilarityCalculator.cs11237-11482
      /branches/HeuristicLab.DataAnalysis.Symbolic.LinearInterpreter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs9271-9826
      /branches/HeuristicLab.TimeSeries/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs7098-8789
      /branches/HeuristicLab.TreeSimplifier/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs8388-8942
      /branches/LogResidualEvaluator/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10202-10483
      /branches/NET40/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5138-5162
      /branches/ParallelEngine/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs6828
      /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10204-10479
      /branches/SuccessProgressAnalysis/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5370-5682
      /branches/Trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs6829-6865
      /branches/VNS/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5594-5752
      /branches/histogram/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs5959-6341
      /stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10032-10033,​11170,​11173
      /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs10269-11210
    r11482 r11488  
    2323using System.Collections.Generic;
    2424using System.Diagnostics;
     25using System.Globalization;
    2526using System.Linq;
    2627using HeuristicLab.Common;
     
    7172
    7273    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
     74      var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
    7375      var compactedGraph = Compact(n1, n2);
    7476
     
    7779
    7880      // visit nodes in order of decreasing height to ensure correct mapping
    79       foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Depth)) {
     81      var nodes1 = n1.IterateNodesPrefix().ToList();
     82      var nodes2 = n2.IterateNodesPrefix().ToList();
     83      foreach (var v in nodes1) {
    8084        if (forwardMap.ContainsKey(v))
    8185          continue;
    8286        var kv = compactedGraph[v];
    8387        ISymbolicExpressionTreeNode w = null;
    84         foreach (var t in n2.IterateNodesPrefix()) {
     88        foreach (var t in nodes2) {
    8589          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
    8690            continue;
     
    9296        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly (as in the paper) because the trees are unordered (subtree order might differ)
    9397        // the solution is to sort subtrees by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees
    94         var eV = IterateBreadthOrdered(v).GetEnumerator();
    95         var eW = IterateBreadthOrdered(w).GetEnumerator();
     98        var eV = IterateBreadthOrdered(v, comparer).GetEnumerator();
     99        var eW = IterateBreadthOrdered(w, comparer).GetEnumerator();
    96100
    97101        while (eV.MoveNext() && eW.MoveNext()) {
     
    148152          bool sort = commutativeSymbols.Contains(label);
    149153          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
    150           if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     154          if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    151155
    152156          for (int i = list.Count - 1; i >= 0; --i) {
     
    159163            var m = w.SymbolicExpressionTreeNode;
    160164            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
    161             if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     165            if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    162166
    163167            if (nNodes.SequenceEqual(mNodes)) {
     
    169173
    170174          if (!found) {
    171             var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
     175            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
    172176            list.Add(w);
    173177            nodeMap[n] = w;
     
    191195    }
    192196
    193     private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
     197    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
    194198      var list = new List<ISymbolicExpressionTreeNode> { node };
    195199      int i = 0;
     
    197201        var n = list[i];
    198202        if (n.SubtreeCount > 0) {
    199           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
     203          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
    200204          list.AddRange(subtrees);
    201205        }
     
    206210
    207211    private string Label(ISymbolicExpressionTreeNode node) {
     212      if (node.SubtreeCount > 0)
     213        return node.Symbol.Name;
     214
    208215      var constant = node as ConstantTreeNode;
    209       if (constant != null && !MatchConstantValues)
    210         return constant.Symbol.Name;
     216      if (constant != null)
     217        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
    211218      var variable = node as VariableTreeNode;
    212       if (variable != null && !MatchVariableWeights) {
    213         return variable.VariableName;
    214       }
     219      if (variable != null) {
     220        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
     221      }
     222
    215223      return node.ToString();
    216224    }
     
    220228      public string Label;
    221229      public int Depth;
    222       public int ChildrenCount;
     230      public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
    223231    }
    224232  }
Note: See TracChangeset for help on using the changeset viewer.