1 | using System.Collections.Generic;
|
---|
2 | using System.Linq;
|
---|
3 | using HeuristicLab.Problems.DataAnalysis.Symbolic;
|
---|
4 |
|
---|
5 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
6 | public class SymbolicExpressionTreeNodeComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
|
---|
7 |
|
---|
8 | public SymbolicExpressionTreeNodeComparer(int similarityLevel) {
|
---|
9 | _similarityLevel = similarityLevel;
|
---|
10 | }
|
---|
11 |
|
---|
12 | public int GetHashCode(ISymbolicExpressionTreeNode n) {
|
---|
13 | return n.ToString().ToLower().GetHashCode();
|
---|
14 | }
|
---|
15 |
|
---|
16 | public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
|
---|
17 | if (a.SubtreeCount != b.SubtreeCount) { return false; }
|
---|
18 | if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
|
---|
19 | // compare leaf nodes according to desired similarity level
|
---|
20 | switch (_similarityLevel) {
|
---|
21 | case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
|
---|
22 | if (a is ConstantTreeNode && b is ConstantTreeNode) {
|
---|
23 | return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
|
---|
24 | }
|
---|
25 | if (a is VariableTreeNode && b is VariableTreeNode) {
|
---|
26 | return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
|
---|
27 | }
|
---|
28 | return false;
|
---|
29 | case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
|
---|
30 | return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
|
---|
31 | case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
|
---|
32 | return true;
|
---|
33 | default:
|
---|
34 | return false;
|
---|
35 | }
|
---|
36 | }
|
---|
37 |
|
---|
38 | private readonly int _similarityLevel;
|
---|
39 | }
|
---|
40 |
|
---|
41 | // tree equality
|
---|
42 | public class SymbolicExpressionTreeComparer : IEqualityComparer<ISymbolicExpressionTree> {
|
---|
43 | public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
|
---|
44 | return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
|
---|
45 | }
|
---|
46 |
|
---|
47 | public int GetHashCode(ISymbolicExpressionTree tree) {
|
---|
48 | return tree.Length;
|
---|
49 | }
|
---|
50 |
|
---|
51 | private int _mode;
|
---|
52 | public void SetComparisonMode(int mode) {
|
---|
53 | _mode = mode;
|
---|
54 | }
|
---|
55 | }
|
---|
56 |
|
---|
57 | public static class SymbolicExpressionTreeMatching {
|
---|
58 | public enum SimilarityLevel {
|
---|
59 | Exact, // everything is matched bit by bit (functions and terminals)
|
---|
60 | High, // symbols are matched. leaf node types are matched
|
---|
61 | Relaxed // only symbols are matched, leafs count as wildcards
|
---|
62 | }
|
---|
63 |
|
---|
64 | public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
|
---|
65 | return FindMatch(t1, t2, mode) == 0;
|
---|
66 | }
|
---|
67 | public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
|
---|
68 | return FindMatch(t1, t2, mode) == 0;
|
---|
69 | }
|
---|
70 |
|
---|
71 | public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
|
---|
72 | var nodes = tree.IterateNodesPostfix().ToArray();
|
---|
73 | var fragments = fragment.IterateNodesPostfix().ToArray();
|
---|
74 | return FindMatch(nodes, fragments, mode) != -1;
|
---|
75 | }
|
---|
76 |
|
---|
77 | #region FindMatch signatures
|
---|
78 | public static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTree t1, int mode) {
|
---|
79 | return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
|
---|
80 | }
|
---|
81 | private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTreeNode t1, int mode) {
|
---|
82 | return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
|
---|
83 | }
|
---|
84 | private static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTreeNode t1, int mode) {
|
---|
85 | return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
|
---|
86 | }
|
---|
87 | private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTree t1, int mode) {
|
---|
88 | return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
|
---|
89 | }
|
---|
90 | #endregion
|
---|
91 |
|
---|
92 | // convenience methods for less typing :)
|
---|
93 | private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
|
---|
94 | return tree.IterateNodesPostfix().GetEnumerator();
|
---|
95 | }
|
---|
96 | private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
|
---|
97 | return tree.IterateNodesPostfix().GetEnumerator();
|
---|
98 | }
|
---|
99 | // method for breath-width iteration of nodes
|
---|
100 | private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
|
---|
101 | return IterateNodes(tree.Root);
|
---|
102 | }
|
---|
103 |
|
---|
104 | private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTreeNode root) {
|
---|
105 | var list = new List<ISymbolicExpressionTreeNode> { root };
|
---|
106 | int offset = 0, count = 1;
|
---|
107 | while (offset != count) {
|
---|
108 | var c = count;
|
---|
109 | for (int i = offset; i != count; ++i) {
|
---|
110 | yield return list[i]; // TODO: look into yield performance (vs returning the whole list at the end)
|
---|
111 | if (!list[i].Subtrees.Any()) continue;
|
---|
112 | list.AddRange(list[i].Subtrees);
|
---|
113 | }
|
---|
114 | offset = c;
|
---|
115 | count = list.Count;
|
---|
116 | }
|
---|
117 | //return list;
|
---|
118 | }
|
---|
119 |
|
---|
120 | /// <summary>
|
---|
121 | /// This method finds the point where parent and child differ. For instance in the case of crossover,
|
---|
122 | /// it will return the node that was swapped into parent0 from parent1
|
---|
123 | /// Prerequisites: as the naming implies, heredity should exist between parent and child,
|
---|
124 | /// otherwise this method would not make much sense (it would always return the root of child)
|
---|
125 | /// </summary>
|
---|
126 | /// <param name="parent">The individual from the previous generation that was crossed over or mutated to produce child</param>
|
---|
127 | /// <param name="child">The result of a genetic operation applied on parent</param>
|
---|
128 | /// <returns>A symbolic expression tree node representing the difference fragment between parent and child</returns>
|
---|
129 | public static ISymbolicExpressionTreeNode GetFragmentDiff(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
|
---|
130 | var e1 = parent.Enumerator();
|
---|
131 | var e2 = child.Enumerator();
|
---|
132 | while (e1.MoveNext() && e2.MoveNext()) {
|
---|
133 | var comparer = new SymbolicExpressionTreeNodeComparer((int)SimilarityLevel.Exact);
|
---|
134 | if (!comparer.Equals(e1.Current, e2.Current)) { return e2.Current; } // return the fragment by which child differs from parent
|
---|
135 | }
|
---|
136 | return null;
|
---|
137 | }
|
---|
138 |
|
---|
139 | // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
|
---|
140 | // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
|
---|
141 | public static int FindMatch(ISymbolicExpressionTreeNode[] seq, ISymbolicExpressionTreeNode[] pat, int mode) {
|
---|
142 | int patlen = pat.Length;
|
---|
143 | int seqlen = seq.Length;
|
---|
144 | if (patlen == 0 || seqlen == 0) return -1;
|
---|
145 | var comparer = new SymbolicExpressionTreeNodeComparer(mode);
|
---|
146 | if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
|
---|
147 | //int i = patlen;
|
---|
148 | //while (i <= seqlen) {
|
---|
149 | // var ch = seq[i - 1];
|
---|
150 | // if (comparer.Equals(ch, pat.Last()))
|
---|
151 | // if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer))
|
---|
152 | // return i - patlen;
|
---|
153 | // ++i;
|
---|
154 | //}
|
---|
155 | for (int i = patlen; i <= seqlen; ++i) {
|
---|
156 | if (comparer.Equals(seq[i - 1], pat.Last())) // first check if last element is a match
|
---|
157 | if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer)) // then check the whole sequence
|
---|
158 | return i - patlen;
|
---|
159 | }
|
---|
160 | return -1;
|
---|
161 | }
|
---|
162 | }
|
---|
163 | }
|
---|