#region License Information
/* HeuristicLab
* Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
using HeuristicLab.EvolutionTracking;
namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
public static class BottomUpDistanceCalculator {
private static Dictionary Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
var G = new DirectedGraph();
var K = new Dictionary();
var F = new DisjointUnion(t1, t2);
var Children = new Dictionary();
var L = new Dictionary();
foreach (var l in F.Nodes.Where(x => x.SubtreeCount == 0)) {
var z = new Vertex { Content = l, Label = Label(l) };
z.Weight = Height(l); // might be necessary
L[z.Label] = z;
G.AddVertex(z);
}
var Q = new Queue();
foreach (var v in F.Nodes) {
Children[v] = v.SubtreeCount;
if (v.SubtreeCount == 0) {
Q.Enqueue(v);
}
}
do {
var v = Q.Dequeue();
if (v.SubtreeCount == 0) {
K[v] = L[Label(v)]; // 18
} else {
bool found = false;
foreach (var w in G.Vertices.Reverse()) {
if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
break;
// sort the lists before comparison, as required when dealing with unordered trees
var V = v.Subtrees.OrderBy(Label).Select(s => K[s]);
var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
if (V.SequenceEqual(W)) {
K[v] = w;
found = true;
break;
}
} // 32: end for
if (!found) {
var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
K[v] = w;
foreach (var u in v.Subtrees) {
G.AddArc(w, K[u]);
} // 40: end for
} // 41: end if
} // 42: end if
if (!F.IsRoot(v)) {
Children[v.Parent] = Children[v.Parent] - 1;
if (Children[v.Parent] == 0) {
Q.Enqueue(v.Parent);
} // 47: end if
} // 48: end if
} while (Q.Count != 0);
return K;
}
private static Dictionary Mapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary K) {
var M = new Dictionary(); // nodes of t1 => nodes of t2
var M_ = new Dictionary(); // nodes of t2 => nodes of t1
//var plist1 = t1.IterateNodesPrefix().ToList();
var plist2 = t2.IterateNodesPrefix().ToList();
foreach (var v in t1.IterateNodesBreadth()) {
if (!M.ContainsKey(v)) {
var w = plist2.Last();
foreach (var u in plist2.Where(x => K[x] == K[v])) {
if (!M_.ContainsKey(u)) {
if (plist2.IndexOf(u) < plist2.IndexOf(w)) {
w = u;
}
}
}
if (K[v] == K[w]) {
// simultaneous preorder traversal of the two subtrees
var nodesV = v.IterateNodesPrefix().ToList();
var nodesW = w.IterateNodesPrefix().ToList();
for (int i = 0; i < Math.Min(nodesV.Count, nodesW.Count); ++i) {
var s = nodesV[i];
var t = nodesW[i];
M[s] = t;
M_[t] = s;
}
// var e1 = v.IterateNodesPrefix().GetEnumerator();
// var e2 = w.IterateNodesPrefix().GetEnumerator();
// while (e1.MoveNext() && e2.MoveNext()) {
// M[e1.Current] = e2.Current;
// M_[e2.Current] = e1.Current;
// }
}
}
}
return M;
}
public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
var K = Compact(t1, t2);
var M = Mapping(t1, t2, K);
int d = t1.Length - M.Count;
int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
int i = t2.Length - M.Count;
double distance = s * p + i * q + d * r;
if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.txt"))) {
var str = FormatMapping(t1, t2, M);
file.WriteLine(str);
}
}
return distance;
}
private static string Label(ISymbolicExpressionTreeNode n) {
return n.ToString();
}
private static int Height(IVertex v) {
return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
}
private static int Height(ISymbolicExpressionTreeNode n) {
var p = n;
while (p.Parent != null)
p = p.Parent;
return p.GetBranchLevel(n);
}
private class DisjointUnion : Tuple {
public DisjointUnion(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2)
: base(t1, t2) {
}
public IEnumerable Nodes {
get { return Item1.IterateNodesPrefix().Concat(Item2.IterateNodesPrefix()); }
}
public bool IsRoot(ISymbolicExpressionTreeNode n) {
return (n == Item1.Root || n == Item2.Root);
}
}
// draw the mapping between t1 and t2
private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary map) {
var formatter = new SymbolicExpressionTreeLatexFormatter();
var sb = new StringBuilder();
string s1, s2;
var m1 = formatter.Format(t1, out s1);
var m2 = formatter.Format(t2, out s2, 20);
sb.Append(s1);
sb.Append(s2);
foreach (var p in map) {
var id1 = m1[p.Key];
var id2 = m2[p.Value];
sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});", id1, id2));
}
return sb.ToString();
}
}
}