Changeset 11646 for branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching
- Timestamp:
- 12/04/14 11:09:44 (10 years ago)
- Location:
- branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic
- Property svn:mergeinfo changed
-
branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs
r10562 r11646 1 using System; 1 #region License Information 2 3 /* HeuristicLab 4 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 5 * 6 * This file is part of HeuristicLab. 7 * 8 * HeuristicLab is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * HeuristicLab is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 22 #endregion 23 24 using System; 2 25 using System.Collections.Generic; 3 26 using System.Linq; … … 45 68 return matrix[m, n] + 1; 46 69 } 70 71 /// <summary> 72 /// Calculates the difference between two symbolic expression trees. 73 /// </summary> 74 /// <param name="tree">The first symbolic expression tree</param> 75 /// <param name="other">The second symbolic expression tree</param> 76 /// <returns>Returns the root of the subtree (from T1) by which T1 differs from T2, or null if no difference is found.</returns> 77 public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTree tree, ISymbolicExpressionTree other) { 78 return Difference(tree.Root, other.Root); 79 } 80 81 public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) { 82 var a = node.IterateNodesPrefix().ToList(); 83 var b = other.IterateNodesPrefix().ToList(); 84 var list = new List<ISymbolicExpressionTreeNode>(); 85 for (int i = 0, j = 0; i < a.Count && j < b.Count; ++i, ++j) { 86 var s1 = a[i].ToString(); 87 var s2 = b[j].ToString(); 88 if (s1 == s2) continue; 89 list.Add(a[i]); 90 // skip subtrees since the parents are already different 91 i += a[i].SubtreeCount; 92 j += b[j].SubtreeCount; 93 } 94 ISymbolicExpressionTreeNode result = list.Count > 0 ? LowestCommonAncestor(node, list) : null; 95 return result; 96 } 97 98 private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) { 99 if (nodes.Count == 0) 100 throw new ArgumentException("The nodes list should contain at least one element."); 101 102 if (nodes.Count == 1) 103 return nodes[0]; 104 105 int minLevel = nodes.Min(x => root.GetBranchLevel(x)); 106 107 // bring the nodes in the nodes to the same level (relative to the root) 108 for (int i = 0; i < nodes.Count; ++i) { 109 var node = nodes[i]; 110 var level = root.GetBranchLevel(node); 111 for (int j = minLevel; j < level; ++j) 112 node = node.Parent; 113 nodes[i] = node; 114 } 115 116 // while not all the elements in the nodes are equal, go one level up 117 while (nodes.Any(x => x != nodes[0])) { 118 for (int i = 0; i < nodes.Count; ++i) 119 nodes[i] = nodes[i].Parent; 120 } 121 122 return nodes[0]; 123 } 47 124 } 48 125 }
Note: See TracChangeset
for help on using the changeset viewer.