Ignore:
Timestamp:
07/29/14 16:20:08 (8 years ago)
Author:
bburlacu
Message:

#2215: Refactored and simplified DirectedGraph and related components API, simplified the BottomUpSimilarityCalculator by not using a directed graph and vertices but a simpler object so that the similarity calculator is self-contained.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11225 r11229  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Drawing;
    25 using System.Globalization;
    2624using System.Linq;
    27 using System.Text;
    2825using HeuristicLab.Common;
    2926using HeuristicLab.Core;
    3027using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    31 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
    3228using HeuristicLab.Optimization.Operators;
    3329using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    7874
    7975      // visit nodes in order of decreasing height to ensure correct mapping
    80       foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Weight)) {
     76      foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Depth)) {
    8177        if (forwardMap.ContainsKey(v))
    8278          continue;
     
    115111    /// Creates a compact representation of the two trees as a directed acyclic graph
    116112    /// </summary>
    117     /// <param name="t1">The first tree</param>
    118     /// <param name="t2">The second tree</param>
     113    /// <param name="n1">The root of the first tree</param>
     114    /// <param name="n2">The root of the second tree</param>
    119115    /// <returns>The compacted DAG representing the two trees</returns>
    120     private Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
    121       var nodesToVertices = new Dictionary<ISymbolicExpressionTreeNode, IVertex>(); // K
    122       var labelsToVertices = new Dictionary<string, IVertex>(); // L
     116    private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
     117      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
     118      var labelMap = new Dictionary<string, GraphNode>(); // L
    123119      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
    124       var vertices = new List<IVertex>(); // G
    125120
    126121      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
     122      var list = new List<GraphNode>();
    127123      var queue = new Queue<ISymbolicExpressionTreeNode>();
    128124
     
    130126        if (n.SubtreeCount == 0) {
    131127          var label = n.ToString();
    132           if (!labelsToVertices.ContainsKey(label)) {
    133             var z = new Vertex { Content = n, Label = label };
    134             labelsToVertices[z.Label] = z;
    135             vertices.Add(z);
    136           }
    137           nodesToVertices[n] = labelsToVertices[label];
     128          if (!labelMap.ContainsKey(label)) {
     129            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
     130            labelMap[z.Label] = z;
     131            list.Add(z);
     132          }
     133          nodeMap[n] = labelMap[label];
    138134          queue.Enqueue(n);
    139135        } else {
     
    141137        }
    142138      }
    143 
    144139      while (queue.Any()) {
    145         var v = queue.Dequeue();
    146 
    147         if (v.SubtreeCount > 0) {
    148           var label = v.Symbol.Name;
     140        var n = queue.Dequeue();
     141
     142        if (n.SubtreeCount > 0) {
     143          var label = n.Symbol.Name;
    149144          bool found = false;
    150           var height = v.GetDepth();
     145          var depth = n.GetDepth();
    151146
    152147          bool sort = commutativeSymbols.Contains(label);
    153           var vSubtrees = v.Subtrees.Select(x => nodesToVertices[x]).ToList();
    154           if (sort) vSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
    155 
    156           // for all nodes w in G in reverse order
    157           for (int i = vertices.Count - 1; i >= 0; --i) {
    158             var w = vertices[i];
    159             var n = (ISymbolicExpressionTreeNode)w.Content;
    160             if (v.SubtreeCount != n.SubtreeCount || label != w.Label || height != (int)w.Weight)
     148          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
     149          if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     150
     151          for (int i = list.Count - 1; i >= 0; --i) {
     152            var w = list[i];
     153
     154            if (!(n.SubtreeCount == w.ChildrenCount && label == w.Label && depth == w.Depth))
    161155              continue;
    162156
    163157            // sort V and W when the symbol is commutative because we are dealing with unordered trees
    164             var wSubtrees = n.Subtrees.Select(x => nodesToVertices[x]).ToList();
    165             if (sort) wSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
    166 
    167             if (vSubtrees.SequenceEqual(wSubtrees)) {
    168               nodesToVertices[v] = w;
     158            var m = w.SymbolicExpressionTreeNode;
     159            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
     160            if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     161
     162            if (nNodes.SequenceEqual(mNodes)) {
     163              nodeMap[n] = w;
    169164              found = true;
    170165              break;
    171166            }
    172           } // 32: end for
     167          }
    173168
    174169          if (!found) {
    175             var w = new Vertex { Content = v, Label = label, Weight = height };
    176             vertices.Add(w);
    177             nodesToVertices[v] = w;
    178 
    179             foreach (var u in v.Subtrees) {
    180               AddArc(w, nodesToVertices[u]);
    181             } // 40: end for
    182           } // 41: end if
    183         } // 42: end if
    184 
    185         var p = v.Parent;
     170            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
     171            list.Add(w);
     172            nodeMap[n] = w;
     173          }
     174        }
     175
     176        var p = n.Parent;
    186177        if (p == null)
    187178          continue;
     
    193184      }
    194185
    195       return nodesToVertices;
     186      return nodeMap;
    196187    }
    197188
     
    202193        var n = list[i];
    203194        if (n.SubtreeCount > 0) {
    204           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(s => s.ToString()) : n.Subtrees;
     195          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
    205196          list.AddRange(subtrees);
    206197        }
     
    210201    }
    211202
    212     private static IArc AddArc(IVertex source, IVertex target) {
    213       var arc = new Arc(source, target);
    214       source.AddForwardArc(arc);
    215       target.AddReverseArc(arc);
    216       return arc;
    217     }
    218 
    219     // debugging
    220     private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
    221       var symbolNameMap = new Dictionary<string, string>
    222     {
    223       {"ProgramRootSymbol", "Prog"},
    224       {"StartSymbol","RPB"},
    225       {"Multiplication", "$\\times$"},
    226       {"Division", "$\\div$"},
    227       {"Addition", "$+$"},
    228       {"Subtraction", "$-$"},
    229       {"Exponential", "$\\exp$"},
    230       {"Logarithm", "$\\log$"}
    231     };
    232 
    233       var sb = new StringBuilder();
    234       var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
    235       int offset = 0;
    236       var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
    237       var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
    238 
    239       double ws = 0.5;
    240       double hs = 0.5;
    241 
    242       var nl = Environment.NewLine;
    243       sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
    244                  "\\usepackage{tikz}" + nl +
    245                  "\\begin{document}" + nl +
    246                  "\\begin{tikzpicture}" + nl +
    247                  "\\def\\ws{1}" + nl +
    248                  "\\def\\hs{0.7}" + nl +
    249                  "\\def\\offs{" + offset + "}" + nl);
    250 
    251       foreach (var node in t1.IterateNodesBreadth()) {
    252         var id = Guid.NewGuid().ToString();
    253         nodeIds[node] = id;
    254         var coord = nodeCoordinates[node];
    255         var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
    256         sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
    257       }
    258 
    259       foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
    260         var n = t;
    261         foreach (var s in t.Subtrees) {
    262           sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
    263         }
    264       }
    265 
    266       nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
    267 
    268       offset = 20;
    269       sb.Append("\\def\\offs{" + offset + "}" + nl);
    270       foreach (var node in t2.IterateNodesBreadth()) {
    271         var id = Guid.NewGuid().ToString();
    272         nodeIds[node] = id;
    273         var coord = nodeCoordinates[node];
    274         var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
    275         sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
    276       }
    277 
    278       foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
    279         var n = t;
    280         foreach (var s in t.Subtrees) {
    281           sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
    282         }
    283       }
    284 
    285       foreach (var p in map) {
    286         var id1 = nodeIds[p.Key];
    287         var id2 = nodeIds[p.Value];
    288 
    289         sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
    290       }
    291       sb.Append("\\end{tikzpicture}" + nl +
    292                 "\\end{document}" + nl);
    293       return sb.ToString();
    294     }
    295 
    296     private static string EscapeLatexString(string s) {
    297       return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
     203    private class GraphNode {
     204      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
     205      public string Label;
     206      public int Depth;
     207      public int ChildrenCount;
    298208    }
    299209  }
Note: See TracChangeset for help on using the changeset viewer.