Changeset 13892
- Timestamp:
- 06/12/16 22:34:22 (8 years ago)
- Location:
- branches/HeuristicLab.EvolutionTracking
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs
r13877 r13892 41 41 private TraceData lastTd; 42 42 43 private ISymbolicExpressionTreeNode clonedSubtree; 44 private Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> clonedMap; 45 43 46 private ISymbolicExpressionTreeNode selectedSubtree; 44 47 private ISymbolicExpressionTreeNode SelectedSubtree { 45 48 get { return selectedSubtree; } 46 49 set { 47 if (value == null || selectedSubtree == value) return;50 if (value == null) return; 48 51 selectedSubtree = value; 49 ClonedSubtree = (ISymbolicExpressionTreeNode)selectedSubtree.Clone(); 50 } 51 } 52 // the clone is necessary in order to deselect parts of a tree (by removing subtrees) 53 // and do "high level" matching of the remaining part 54 private ISymbolicExpressionTreeNode ClonedSubtree { get; set; } 52 // the code below enables a "shadow" copy of the selected subtree which is used for matching against the graph 53 clonedSubtree = (ISymbolicExpressionTreeNode)selectedSubtree.Clone(); 54 clonedMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); 55 var e1 = selectedSubtree.IterateNodesPrefix().GetEnumerator(); 56 var e2 = clonedSubtree.IterateNodesPrefix().GetEnumerator(); 57 58 while (e1.MoveNext() && e2.MoveNext()) { 59 clonedMap.Add(e1.Current, e2.Current); 60 } 61 } 62 } 55 63 56 64 // we use the symbolic expression tree chart to call the drawing routines … … 74 82 genealogyGraphChart.GenealogyGraph = Content; 75 83 } 84 } 85 86 protected override void RegisterContentEvents() { 87 base.RegisterContentEvents(); 88 if (SymbolicExpressionTreeChart != null) 89 SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionTreeNodeClicked; 90 } 91 92 protected override void DeregisterContentEvents() { 93 if (SymbolicExpressionTreeChart != null) 94 SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionTreeNodeClicked; 95 base.DeregisterContentEvents(); 76 96 } 77 97 … … 110 130 var nodes = graphNode.Data.IterateNodesPrefix().ToList(); 111 131 // calculate max only in the current generation 112 var max = Content.Vertices.Max(x => ((IGenealogyGraphNode<ISymbolicExpressionTree>)x).Data.IterateNodesPrefix().Max(n => n.NodeWeight));132 var max = Content.Vertices.Max(x => x.Data.IterateNodesPrefix().Max(n => n.NodeWeight)); 113 133 if (max.IsAlmost(0)) max = 1; 114 134 // we skip the program root node because it's useless for display and it just takes space in the chart … … 121 141 } 122 142 123 if (!graphNode.InArcs.Any()) return; 143 if (!graphNode.InArcs.Any()) 144 return; 124 145 var data = graphNode.InArcs.Last().Data; 125 146 var fragment = data as IFragment<ISymbolicExpressionTreeNode>; … … 133 154 } else if (td != null) { 134 155 // highlight traced subtree and fragment 135 treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange); 136 treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue); 156 if (td.SubtreeIndex == td.FragmentIndex) { 157 treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Purple); 158 } else if (td.SubtreeIndex < td.FragmentIndex) { 159 treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange); 160 treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue); 161 } else { 162 treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue); 163 treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange); 164 } 137 165 } 138 166 } … … 149 177 var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(node); 150 178 var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: false, updateSubtreeWeights: false, cacheTraceNodes: true); 179 180 if (!traceGraph.Vertices.Any()) 181 return; 182 151 183 genealogyGraphChart.SuspendRendering(); 152 184 genealogyGraphChart.ClearPrimitives(); // clear everything 153 185 var rankMaximums = new Dictionary<double, double>(); 186 187 if (openNew_CheckBox.Checked) { 188 MainFormManager.MainForm.ShowContent(traceGraph); 189 } else { 190 } 154 191 // fill each vertex in the graph with a grayscale color according to average subtree weight 155 192 156 int colorCount = ColorGradient.GrayscaledColors.Count - 1; 157 var colorGradient = ColorGradient.GrayscaledColors; 158 foreach (var r in Content.Ranks) { 159 var vertices = r.Value.Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList(); 160 var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList(); 161 var max = averages.Max(); 162 rankMaximums.Add(r.Key, max); 163 if (max.IsAlmost(0.0)) continue; 164 for (int i = 0; i < vertices.Count; ++i) { 165 var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)]; 166 var vNode = genealogyGraphChart.GetMappedNode(vertices[i]); 167 vNode.Brush = new SolidBrush(color); 168 } 169 } 170 // fill vertices that are part of the trace with a rgb color according to average subtree weight 171 if (traceGraph.Vertices.Any()) { 172 var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank); 173 foreach (var g in ranks) { 174 var vertices = g.ToList(); 175 var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList(); 176 double max = rankMaximums[g.Key]; 177 if (max.IsAlmost(0.0)) continue; 178 for (int i = 0; i < vertices.Count; ++i) { 179 var vNode = genealogyGraphChart.GetMappedNode(vertices[i]); 180 // use a grayscale gradient 181 var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)]; 182 vNode.Brush = new SolidBrush(color); 183 } 184 } 185 186 if (openNew_CheckBox.Checked) { 187 MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen 188 } 189 } 193 /* 194 var colorGradient = ColorGradient.GrayscaledColors; 195 var colorCount = colorGradient.Count - 1; 196 foreach (var r in Content.Ranks) { 197 var vertices = r.Value.Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList(); 198 var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList(); 199 var max = averages.Max(); 200 rankMaximums.Add(r.Key, max); 201 if (max.IsAlmost(0.0)) continue; 202 for (int i = 0; i < vertices.Count; ++i) { 203 var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)]; 204 var vNode = genealogyGraphChart.GetMappedNode(vertices[i]); 205 vNode.Brush = new SolidBrush(color); 206 } 207 } 208 // fill vertices that are part of the trace with a rgb color according to average subtree weight 209 if (traceGraph.Vertices.Any()) { 210 var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank); 211 foreach (var g in ranks) { 212 var vertices = g.ToList(); 213 var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList(); 214 double max = rankMaximums[g.Key]; 215 if (max.IsAlmost(0.0)) continue; 216 for (int i = 0; i < vertices.Count; ++i) { 217 var vNode = genealogyGraphChart.GetMappedNode(vertices[i]); 218 // use a grayscale gradient 219 var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)]; 220 vNode.Brush = new SolidBrush(color); 221 } 222 } 223 */ 224 225 // if (openNew_CheckBox.Checked) { 226 // MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen 227 // } 228 // } 190 229 genealogyGraphChart.ResumeRendering(); 191 230 } else { … … 203 242 204 243 private void OnTreeNodeMiddleClicked(ISymbolicExpressionTreeNode node) { 205 var index = SelectedSubtree.IterateNodesPrefix().ToList().IndexOf(node); 206 if (index > 0) { 207 var s = ClonedSubtree.NodeAt(index); 208 s.Parent.RemoveSubtree(s.Parent.IndexOfSubtree(s)); 209 210 var trees = Content.Vertices.Select(x => x.Data); 211 comparer.MatchVariableWeights = matchingModeButton.Checked; 212 comparer.MatchConstantValues = matchingModeButton.Checked; 213 var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(ClonedSubtree, comparer)); 214 215 var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x)); 216 treeChart_HighlightSubtree(node, Color.Black, Color.White); 217 graphChart_HighlightMatchingVertices(matchingVertices); 218 } 244 ISymbolicExpressionTreeNode clone; 245 if (!clonedMap.TryGetValue(node, out clone)) return; 246 if (clone.Parent == null) return; 247 var cloneParent = clone.Parent; 248 var cloneIndex = cloneParent.IndexOfSubtree(clone); 249 cloneParent.RemoveSubtree(cloneIndex); 250 cloneParent.InsertSubtree(cloneIndex, new AnySubtreeSymbol().CreateTreeNode()); 251 252 var trees = Content.Vertices.Select(x => x.Data); 253 comparer.MatchVariableWeights = comparer.MatchConstantValues = matchingModeButton.Checked; 254 var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(clonedSubtree, comparer)); 255 256 var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x)); 257 treeChart_HighlightSubtree(node, Color.Black, Color.White); 258 graphChart_HighlightMatchingVertices(matchingVertices); 219 259 } 220 260 #endregion … … 223 263 var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender; 224 264 var subtree = visualNode.Content; 225 // highlight the selected subtree inside the displayed tree on the right hand side226 treeChart_ClearColors();227 treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);228 265 229 266 switch (args.Button) { 230 267 case MouseButtons.Left: { 268 // highlight the selected subtree inside the displayed tree on the right hand side 269 treeChart_ClearColors(); 270 treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue); 271 231 272 OnTreeNodeLeftClicked(subtree); 232 273 break; … … 240 281 #endregion 241 282 242 protected override void RegisterContentEvents() { 243 base.RegisterContentEvents(); 244 if (SymbolicExpressionTreeChart != null) 245 SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionTreeNodeClicked; 246 } 247 248 protected override void DeregisterContentEvents() { 249 if (SymbolicExpressionTreeChart != null) 250 SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionTreeNodeClicked; 251 base.DeregisterContentEvents(); 252 } 283 253 284 254 285 private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) { … … 304 335 } 305 336 337 var comp = new SymbolicExpressionTreeNodeEqualityComparer(); 338 306 339 if (lastTd != null && graphNode.InDegree > 1) { 307 var c = graphNode.Data; 308 var s = c.NodeAt(lastTd.SubtreeIndex); 309 var f = c.NodeAt(lastTd.FragmentIndex); 310 arc = graphNode.InArcs.FirstOrDefault( 311 a => { 312 var td = a.Data as TraceData; 313 if (td == null) return false; 314 var p = (ISymbolicExpressionTree)a.Source.Data; 315 var d = s.Difference(p.NodeAt(td.SubtreeIndex)); 316 if (d == null) return true; 317 return f.IterateNodesPrefix().Any(x => x.IsIsomorphicWith(d)); 318 }); 340 var descendant = graphNode.Data; 341 // going left (in the direction of the traced subtree): 342 // the ancestor shares the same structure with the descendant, with the exception of the fragment 343 // thus we identify the right ancestor by comparing the remaining nodes 344 //var descendantNodes = descendant.Root.IterateNodesPrefix(lastTd.FragmentIndex); 345 // calculate the relative fragment preorder index. it will always be > 0 due to the way the trace graph is constructed 346 var relativeFragmentIndex = lastTd.FragmentIndex - lastTd.SubtreeIndex; 347 var descendantNodes = descendant.NodeAt(lastTd.SubtreeIndex).IterateNodesPrefix(relativeFragmentIndex); 348 349 var filteredArcs = graphNode.InArcs.Where(a => { 350 var td = a.Data as TraceData; 351 if (td == null) 352 return false; 353 if (!(td.LastSubtreeIndex == lastTd.SubtreeIndex && td.LastFragmentIndex == lastTd.FragmentIndex)) 354 return false; 355 return true; 356 }).ToList(); 357 358 if (filteredArcs.Count == 0) 359 return; 360 361 if (filteredArcs.Count == 1) { 362 arc = filteredArcs[0]; 363 } else { 364 arc = filteredArcs.FirstOrDefault( 365 a => { 366 var ancestor = (ISymbolicExpressionTree)a.Source.Data; 367 var td = a.Data as TraceData; 368 if (td == null) 369 return false; 370 var ancestorNodes = ancestor.NodeAt(td.SubtreeIndex).IterateNodesPrefix(skipIndex: relativeFragmentIndex); 371 return descendantNodes.SequenceEqual(ancestorNodes, comp); 372 }); 373 } 374 375 319 376 } 320 377 if (arc == null) return; … … 338 395 339 396 if (lastTd != null && graphNode.InDegree > 1) { 340 var c = graphNode.Data; 341 var f = c.NodeAt(lastTd.FragmentIndex); 342 arc = graphNode.InArcs.FirstOrDefault( 343 a => { 344 var td = a.Data as TraceData; 345 var p = (ISymbolicExpressionTree)a.Source.Data; 346 return td != null && p.NodeAt(td.SubtreeIndex).Difference(f) == null; 347 }); 397 var descendant = graphNode.Data; 398 // going right (in the direction of the fragment): 399 // 1) fragment was swapped by crossover 400 // 2) fragment was introduced by mutation 401 // in some cases mutation changes things completely so we do not know which way to go 402 403 var f = descendant.NodeAt(lastTd.FragmentIndex); 404 arc = graphNode.InArcs.FirstOrDefault(a => { 405 var td = a.Data as TraceData; 406 if (td == null) return false; 407 var ancestor = (ISymbolicExpressionTree)a.Source.Data; 408 return f.Difference(ancestor.NodeAt(td.SubtreeIndex)) == null; 409 }); 348 410 } 349 411 if (arc == null) return; … … 364 426 return NodeAt(tree.Root, position); 365 427 } 428 366 429 internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) { 367 430 return root.IterateNodesPrefix().ElementAt(position); 368 431 } 432 369 433 internal static bool IsIsomorphicWith(this ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) { 370 434 return a.Difference(b) == null; 371 435 } 436 437 internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, int skipIndex) { 438 var e = node.IterateNodesPrefix().GetEnumerator(); 439 var i = 0; 440 while (e.MoveNext()) { 441 var n = e.Current; 442 if (i == skipIndex) { 443 var len = n.GetLength(); 444 while (--len >= 0 && e.MoveNext()) ; 445 n = e.Current; 446 } 447 if (n != null) 448 yield return n; 449 ++i; 450 } 451 } 452 453 internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode skipNode) { 454 var e = node.IterateNodesPrefix().GetEnumerator(); 455 while (e.MoveNext()) { 456 var n = e.Current; 457 if (n == skipNode) { 458 int len = n.GetLength(); 459 while (--len >= 0 && e.MoveNext()) ; 460 n = e.Current; 461 } 462 if (n != null) 463 yield return n; 464 } 465 } 372 466 } 373 467 #endregion -
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs
r13875 r13892 42 42 // we can have multiple matches of the same node 43 43 44 return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) == fragmentLength);44 return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) >= fragmentLength); 45 45 } 46 46 … … 56 56 // AnySubtree wildcards mach everything 57 57 if (a is AnySubtree) 58 return b.GetLength();58 return 1; 59 59 if (b is AnySubtree) 60 return a.GetLength();60 return 1; 61 61 62 62 int m = a.SubtreeCount;
Note: See TracChangeset
for help on using the changeset viewer.