source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs @ 11016

Last change on this file since 11016 was 11016, checked in by bburlacu, 6 years ago

#1772: Made some progress with the BottomUpDistanceCalculator, still not entirely correct.

File size: 8.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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 System;
23using System.Collections.Generic;
24using System.Globalization;
25using System.IO;
26using System.Linq;
27using System.Text;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
30using HeuristicLab.EvolutionTracking;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  public static class BottomUpDistanceCalculator {
34    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
35      var G = new DirectedGraph();
36      var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
37      var F = new DisjointUnion(t1, t2);
38      var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
39      var L = new Dictionary<string, IVertex>();
40      foreach (var l in F.Nodes.Where(x => x.SubtreeCount == 0)) {
41        var z = new Vertex { Content = l, Label = Label(l) };
42        //        z.Weight = Height(l); // might be necessary (although not specified in the paper)
43        //        if (!L.ContainsKey(z.Label))
44        L[z.Label] = z; // will overwrite key values, possible bug
45        G.AddVertex(z);
46      }
47      var Q = new Queue<ISymbolicExpressionTreeNode>();
48      foreach (var v in F.Nodes) {
49        Children[v] = v.SubtreeCount;
50        if (v.SubtreeCount == 0) {
51          Q.Enqueue(v);
52        }
53      }
54      while (Q.Any()) {
55        var v = Q.Dequeue();
56        if (v.SubtreeCount == 0) {
57          K[v] = L[Label(v)]; // 18
58        } else {
59          bool found = false;
60
61          foreach (var w in G.Vertices.Reverse()) {
62            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
63              break;
64
65            // sort the lists before comparison, as required when dealing with unordered trees
66            var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
67            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
68            if (V.SequenceEqual(W)) {
69              K[v] = w;
70              found = true;
71              break;
72            }
73          } // 32: end for
74
75          if (!found) {
76            var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
77            G.AddVertex(w);
78            K[v] = w;
79
80            foreach (var u in v.Subtrees) {
81              G.AddArc(w, K[u]);
82            } // 40: end for
83          } // 41: end if
84        } // 42: end if
85
86        if (!F.IsRoot(v)) {
87          Children[v.Parent] = Children[v.Parent] - 1;
88          if (Children[v.Parent] == 0) {
89            Q.Enqueue(v.Parent);
90          } // 47: end if
91        } // 48: end if
92      };
93      return K;
94    }
95
96    private static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> Mapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, IVertex> K) {
97      var M = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
98      var M_ = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
99      //var plist1 = t1.IterateNodesPrefix().ToList();
100      var plist2 = t2.IterateNodesPrefix().ToList();
101      foreach (var v in t1.IterateNodesBreadth()) {
102        if (!M.ContainsKey(v)) {
103          var w = plist2.Last();
104          foreach (var u in plist2.Where(x => K[x] == K[v])) {
105            if (!M_.ContainsKey(u)) {
106              if (plist2.IndexOf(u) < plist2.IndexOf(w)) {
107                w = u;
108              }
109            }
110          }
111          if (K[v] == K[w]) {
112            // simultaneous preorder traversal of the two subtrees
113            var nodesV = v.IterateNodesPrefix().ToList();
114            var nodesW = w.IterateNodesPrefix().ToList();
115            for (int i = 0; i < Math.Min(nodesV.Count, nodesW.Count); ++i) {
116              var s = nodesV[i];
117              var t = nodesW[i];
118              M[s] = t;
119              M_[t] = s;
120            }
121            //            var e1 = v.IterateNodesPrefix().GetEnumerator();
122            //            var e2 = w.IterateNodesPrefix().GetEnumerator();
123            //            while (e1.MoveNext() && e2.MoveNext()) {
124            //              M[e1.Current] = e2.Current;
125            //              M_[e2.Current] = e1.Current;
126            //            }
127          }
128        }
129      }
130      return M;
131    }
132
133    public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
134      var K = Compact(t1, t2);
135      var M = Mapping(t1, t2, K);
136      int d = t1.Length - M.Count;
137      int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
138      int i = t2.Length - M.Count;
139
140      double distance = s * p + i * q + d * r;
141
142      if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
143        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.txt"))) {
144          var str = FormatMapping(t1, t2, M);
145          file.WriteLine(str);
146        }
147      }
148
149      return distance;
150    }
151
152    private static string Label(ISymbolicExpressionTreeNode n) {
153      return n.ToString();
154    }
155
156    private static int Height(IVertex v) {
157      return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
158    }
159
160    private static int Height(ISymbolicExpressionTreeNode n) {
161      var p = n;
162      while (p.Parent != null)
163        p = p.Parent;
164      return p.GetBranchLevel(n);
165    }
166
167    private class DisjointUnion : Tuple<ISymbolicExpressionTree, ISymbolicExpressionTree> {
168      public DisjointUnion(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2)
169        : base(t1, t2) {
170      }
171
172      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
173        get {
174          var nodes1 = Item1.Root.IterateNodesBreadth().Reverse();
175          var nodes2 = Item2.Root.IterateNodesBreadth().Reverse();
176
177          return nodes1.Concat(nodes2);
178
179          //          var nodes =
180          //            nodes1.Select(n => new { Node = n, Height = Item1.Root.GetBranchLevel(n) })
181          //              .Concat(nodes2.Select(n => new { Node = n, Height = Item2.Root.GetBranchLevel(n) }))
182          //              .OrderByDescending(x => x.Height)
183          //              .Select(x => x.Node);
184          //
185          //          return nodes;
186          //          //          var list = new List<ISymbolicExpressionTreeNode> { Item1.Root, Item2.Root };
187          //          //          int i = 0;
188          //          //          while (i != list.Count) {
189          //          //            var node = list[i];
190          //          //            if (node.SubtreeCount > 0) {
191          //          //              list.AddRange(node.Subtrees);
192          //          //            }
193          //          //            ++i;
194          //          //          }
195          //          //          list.Reverse(); // return nodes in order of decreasing height
196          //          //          return list;
197        }
198      }
199
200      public bool IsRoot(ISymbolicExpressionTreeNode n) {
201        return (n == Item1.Root || n == Item2.Root);
202      }
203    }
204
205    // draw the mapping between t1 and t2
206    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
207      var formatter = new SymbolicExpressionTreeLatexFormatter();
208      var sb = new StringBuilder();
209
210      string s1, s2;
211      var m1 = formatter.Format(t1, out s1);
212      var m2 = formatter.Format(t2, out s2, 20);
213
214      sb.Append(s1);
215      sb.Append(s2);
216
217      foreach (var p in map) {
218        var id1 = m1[p.Key];
219        var id2 = m2[p.Value];
220
221        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});", id1, id2));
222      }
223
224      return sb.ToString();
225    }
226  }
227}
Note: See TracBrowser for help on using the repository browser.