Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11023 was 11023, checked in by bburlacu, 8 years ago

#1772: Small cosmetic changes in BottomUpDistanceCalculator.cs

File size: 7.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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  /// <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>
37  public static class BottomUpDistanceCalculator {
38    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
39      var G = new DirectedGraph();
40      var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
41      var F = new DisjointUnion(t1, t2);
42      var L = new Dictionary<string, IVertex>();
43      var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
44
45      var nodes = F.Nodes.ToList();
46
47      // for all leaf labels l in F
48      foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) {
49        var label = Label(l);
50        var z = new Vertex { Content = l, Label = label };
51        L[z.Label] = z;
52        G.AddVertex(z);
53      }
54
55      var Q = new Queue<ISymbolicExpressionTreeNode>();
56
57      // for all nodes
58      foreach (var v in nodes) {
59        Children[v] = v.SubtreeCount;
60        if (v.SubtreeCount == 0) {
61          Q.Enqueue(v);
62        }
63      }
64
65      while (Q.Any()) {
66        var v = Q.Dequeue();
67        if (v.SubtreeCount == 0) {
68          K[v] = L[Label(v)]; // 18
69        } else {
70          bool found = false;
71          // for all nodes w in G in reverse order
72          foreach (var w in G.Vertices.Reverse()) {
73            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
74              break;
75
76            // sort V and W because we are dealing with unordered trees
77            var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
78            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
79            if (V.SequenceEqual(W)) {
80              K[v] = w;
81              found = true;
82              break;
83            }
84          } // 32: end for
85
86          if (!found) {
87            var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
88            G.AddVertex(w);
89            K[v] = w;
90
91            foreach (var u in v.Subtrees) {
92              G.AddArc(w, K[u]);
93            } // 40: end for
94          } // 41: end if
95        } // 42: end if
96
97        if (v.Parent != null) {
98          var p = v.Parent;
99          Children[p]--;
100          if (Children[p] == 0)
101            Q.Enqueue(p);
102        }
103      };
104
105      using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "graph.dot"))) {
106        var str = G.ExportDot();
107        file.WriteLine(str);
108      }
109
110      return K;
111    }
112
113    private static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> Mapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, IVertex> K) {
114      var M = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
115      var M_ = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
116      var plist2 = t2.IterateNodesPrefix().ToList();
117      foreach (var n in t1.IterateNodesBreadth()) {
118        ISymbolicExpressionTreeNode v = n;
119        if (!M.ContainsKey(v)) {
120          var w = plist2.Last();
121          var pw = plist2.IndexOf(w); // preorder index of node w
122          foreach (var u in plist2.Where(x => K[x] == K[v])) {
123            if (!M_.ContainsKey(u)) {
124              w = u;
125              // commented out test below since we are dealing with unordered trees
126              //              if (plist2.IndexOf(u) < pw) {
127              //                w = u;
128              //              }
129            }
130          }
131          if (K[v] == K[w]) {
132            // simultaneous preorder traversal of the two subtrees
133            var nodesV = v.IterateNodesPrefix().ToList();
134            var nodesW = w.IterateNodesPrefix().ToList();
135            for (int i = 0; i < Math.Min(nodesV.Count, nodesW.Count); ++i) {
136              var s = nodesV[i];
137              var t = nodesW[i];
138              M[s] = t;
139              M_[t] = s;
140            }
141          }
142        }
143      }
144      return M;
145    }
146
147    public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
148      var K = Compact(t1, t2);
149      var M = Mapping(t1, t2, K);
150      int d = t1.Length - M.Count;
151      int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
152      int i = t2.Length - M.Count;
153
154      double distance = s * p + i * q + d * r;
155
156      if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
157        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.tex"))) {
158          var str = FormatMapping(t1, t2, M);
159          file.WriteLine(str);
160        }
161      }
162
163      return distance;
164    }
165
166    private static string Label(ISymbolicExpressionTreeNode n) {
167      return n.ToString();
168    }
169
170    private static int Height(IVertex v) {
171      return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
172    }
173
174    private static int Height(ISymbolicExpressionTreeNode n) {
175      var p = n;
176      while (p.Parent != null)
177        p = p.Parent;
178      return p.GetBranchLevel(n);
179    }
180
181    private class DisjointUnion : Tuple<ISymbolicExpressionTree, ISymbolicExpressionTree> {
182      public DisjointUnion(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2)
183        : base(t1, t2) {
184      }
185
186      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
187        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
188      }
189    }
190
191    // draw the mapping between t1 and t2 as a tikz picture
192    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
193      var formatter = new SymbolicExpressionTreeLatexFormatter();
194      var sb = new StringBuilder();
195
196      string s1, s2;
197      var m1 = formatter.Format(t1, out s1);
198      var m2 = formatter.Format(t2, out s2, 20);
199
200      sb.Append(s1);
201      sb.Append(s2);
202
203      foreach (var p in map) {
204        var id1 = m1[p.Key];
205        var id2 = m2[p.Value];
206
207        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
208      }
209
210      return sb.ToString();
211    }
212  }
213}
Note: See TracBrowser for help on using the repository browser.