Changeset 13892


Ignore:
Timestamp:
06/12/16 22:34:22 (3 years ago)
Author:
bburlacu
Message:

#1772: Fix bug in tree matching with wildcards (used by the genealogy graph view instead of the query match) and improved subtree selection and matching functionality in the genealogy graph view.

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  
    4141    private TraceData lastTd;
    4242
     43    private ISymbolicExpressionTreeNode clonedSubtree;
     44    private Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> clonedMap;
     45
    4346    private ISymbolicExpressionTreeNode selectedSubtree;
    4447    private ISymbolicExpressionTreeNode SelectedSubtree {
    4548      get { return selectedSubtree; }
    4649      set {
    47         if (value == null || selectedSubtree == value) return;
     50        if (value == null) return;
    4851        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    }
    5563
    5664    // we use the symbolic expression tree chart to call the drawing routines
     
    7482        genealogyGraphChart.GenealogyGraph = Content;
    7583      }
     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();
    7696    }
    7797
     
    110130      var nodes = graphNode.Data.IterateNodesPrefix().ToList();
    111131      // 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));
    113133      if (max.IsAlmost(0)) max = 1;
    114134      // we skip the program root node because it's useless for display and it just takes space in the chart
     
    121141      }
    122142
    123       if (!graphNode.InArcs.Any()) return;
     143      if (!graphNode.InArcs.Any())
     144        return;
    124145      var data = graphNode.InArcs.Last().Data;
    125146      var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
     
    133154      } else if (td != null) {
    134155        // 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        }
    137165      }
    138166    }
     
    149177        var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(node);
    150178        var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: false, updateSubtreeWeights: false, cacheTraceNodes: true);
     179
     180        if (!traceGraph.Vertices.Any())
     181          return;
     182
    151183        genealogyGraphChart.SuspendRendering();
    152184        genealogyGraphChart.ClearPrimitives(); // clear everything
    153185        var rankMaximums = new Dictionary<double, double>();
     186
     187        if (openNew_CheckBox.Checked) {
     188          MainFormManager.MainForm.ShowContent(traceGraph);
     189        } else {
     190        }
    154191        // fill each vertex in the graph with a grayscale color according to average subtree weight
    155192
    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        //        }
    190229        genealogyGraphChart.ResumeRendering();
    191230      } else {
     
    203242
    204243    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);
    219259    }
    220260    #endregion
     
    223263      var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
    224264      var subtree = visualNode.Content;
    225       // highlight the selected subtree inside the displayed tree on the right hand side
    226       treeChart_ClearColors();
    227       treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
    228265
    229266      switch (args.Button) {
    230267        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
    231272            OnTreeNodeLeftClicked(subtree);
    232273            break;
     
    240281    #endregion
    241282
    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
    253284
    254285    private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
     
    304335      }
    305336
     337      var comp = new SymbolicExpressionTreeNodeEqualityComparer();
     338
    306339      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
    319376      }
    320377      if (arc == null) return;
     
    338395
    339396      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        });
    348410      }
    349411      if (arc == null) return;
     
    364426    return NodeAt(tree.Root, position);
    365427  }
     428
    366429  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
    367430    return root.IterateNodesPrefix().ElementAt(position);
    368431  }
     432
    369433  internal static bool IsIsomorphicWith(this ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    370434    return a.Difference(b) == null;
    371435  }
     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  }
    372466}
    373467#endregion
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs

    r13875 r13892  
    4242      // we can have multiple matches of the same node
    4343
    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);
    4545    }
    4646
     
    5656      // AnySubtree wildcards mach everything
    5757      if (a is AnySubtree)
    58         return b.GetLength();
     58        return 1;
    5959      if (b is AnySubtree)
    60         return a.GetLength();
     60        return 1;
    6161
    6262      int m = a.SubtreeCount;
Note: See TracChangeset for help on using the changeset viewer.