Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs @ 12929

Last change on this file since 12929 was 12929, checked in by bburlacu, 9 years ago

#1772: Initial implementation of tree pattern matching algorithm by Götz et al. (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440). Added wildcard symbols and nodes and updated the matching code accordingly.

File size: 4.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26
27namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
28  [Item("SymbolicExpressionTreeNodeEqualityComparer", "An operator that checks node equality based on different similarity measures.")]
29  [StorableClass]
30  public class SymbolicExpressionTreeNodeEqualityComparer : Item, ISymbolicExpressionTreeNodeEqualityComparer {
31    [StorableConstructor]
32    protected SymbolicExpressionTreeNodeEqualityComparer(bool deserializing) : base(deserializing) { }
33    protected SymbolicExpressionTreeNodeEqualityComparer(SymbolicExpressionTreeNodeEqualityComparer original, Cloner cloner)
34      : base(original, cloner) {
35      matchConstantValues = original.matchConstantValues;
36      matchVariableNames = original.matchVariableNames;
37      matchVariableWeights = original.matchVariableWeights;
38    }
39    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeEqualityComparer(this, cloner); }
40
41    // more flexible matching criteria
42    [Storable]
43    private bool matchConstantValues;
44    public bool MatchConstantValues {
45      get { return matchConstantValues; }
46      set { matchConstantValues = value; }
47    }
48
49    [Storable]
50    private bool matchVariableNames;
51    public bool MatchVariableNames {
52      get { return matchVariableNames; }
53      set { matchVariableNames = value; }
54    }
55
56    [Storable]
57    private bool matchVariableWeights;
58    public bool MatchVariableWeights {
59      get { return matchVariableWeights; }
60      set { matchVariableWeights = value; }
61    }
62
63    [StorableHook(HookType.AfterDeserialization)]
64    private void AfterDeserialization() {
65    }
66
67    public SymbolicExpressionTreeNodeEqualityComparer() {
68      matchConstantValues = true;
69      matchVariableNames = true;
70      matchVariableWeights = true;
71    }
72
73    public int GetHashCode(ISymbolicExpressionTreeNode n) {
74      return n.ToString().ToLower().GetHashCode();
75    }
76
77    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
78      var sa = a as AnySubtree;
79      var sb = b as AnySubtree;
80
81      if (sa != null || sb != null)
82        return true;
83
84      if (a.SubtreeCount != b.SubtreeCount)
85        return false;
86
87      var na = a as AnyNode;
88      var nb = b as AnyNode;
89      if (na != null || nb != null)
90        return true;
91
92      var ta = a as SymbolicExpressionTreeTerminalNode;
93      var tb = b as SymbolicExpressionTreeTerminalNode;
94      if (ta != null && tb != null) {
95        var ca = a as ConstantTreeNode;
96        var cb = b as ConstantTreeNode;
97        if (ca != null && cb != null)
98          // both a and b are constants
99          return !MatchConstantValues || ca.Value.Equals(cb.Value);
100
101        var va = a as VariableTreeNode;
102        var vb = b as VariableTreeNode;
103        if (va != null && vb != null) {
104          // both a and b are variables
105          bool m1 = !MatchVariableNames || va.VariableName.Equals(vb.VariableName);
106          bool m2 = !MatchVariableWeights || va.Weight.IsAlmost(vb.Weight);
107          return m1 && m2;
108        }
109      }
110      if (ta == null && tb == null) {
111        // both a and b are non-terminal (function) nodes
112        return a.Symbol.Name.Equals(b.Symbol.Name);
113      }
114
115      // return false in all other cases
116      return false;
117    }
118  }
119}
Note: See TracBrowser for help on using the repository browser.