Changeset 11023 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic
- Timestamp:
- 06/17/14 10:30:25 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs
r11021 r11023 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-201 3Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 31 31 32 32 namespace 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> 33 37 public static class BottomUpDistanceCalculator { 34 38 private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) { … … 41 45 var nodes = F.Nodes.ToList(); 42 46 47 // for all leaf labels l in F 43 48 foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) { 44 49 var label = Label(l); … … 49 54 50 55 var Q = new Queue<ISymbolicExpressionTreeNode>(); 56 57 // for all nodes 51 58 foreach (var v in nodes) { 52 59 Children[v] = v.SubtreeCount; … … 62 69 } else { 63 70 bool found = false; 64 71 // for all nodes w in G in reverse order 65 72 foreach (var w in G.Vertices.Reverse()) { 66 if (Height(v) != Height(w) )73 if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label) 67 74 break; 68 if (v.SubtreeCount != w.OutDegree) 69 break; 70 if (Label(v) != w.Label) 71 break; 72 75 76 // sort V and W because we are dealing with unordered trees 73 77 var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label); 74 78 var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label); … … 91 95 } // 42: end if 92 96 93 if (v.Parent == null) continue; 94 var p = v.Parent; 95 Children[p]--; 96 if (Children[p] == 0) 97 Q.Enqueue(p); 97 if (v.Parent != null) { 98 var p = v.Parent; 99 Children[p]--; 100 if (Children[p] == 0) 101 Q.Enqueue(p); 102 } 98 103 }; 99 104 … … 118 123 if (!M_.ContainsKey(u)) { 119 124 w = u; 125 // commented out test below since we are dealing with unordered trees 120 126 // if (plist2.IndexOf(u) < pw) { 121 127 // w = u; … … 183 189 } 184 190 185 // draw the mapping between t1 and t2 191 // draw the mapping between t1 and t2 as a tikz picture 186 192 private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) { 187 193 var formatter = new SymbolicExpressionTreeLatexFormatter();
Note: See TracChangeset
for help on using the changeset viewer.