1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022014 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Globalization;


25  using System.IO;


26  using System.Linq;


27  using System.Text;


28  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


29  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;


30  using HeuristicLab.EvolutionTracking;


31 


32  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


33  /// <summary>


34  /// This class implements the bottomup tree distance described in the following paper:


35  /// G. Valiente, "An Efficient Bottomup 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  }

