source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/ExtendedSymbolicExpressionTreeCanvas.cs @ 9963

Last change on this file since 9963 was 9963, checked in by bburlacu, 8 years ago

#1772: Merged changes from the trunk and other branches. Added new ExtendedSymbolicExpressionTreeCanvas control for the visual exploration of tree genealogies. Reorganized some files and folders.

File size: 16.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Drawing;
4using System.Linq;
5using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
6using HeuristicLab.EvolutionaryTracking.Views.Primitives;
7using HeuristicLab.Visualization;
8
9namespace HeuristicLab.EvolutionaryTracking.Views {
10  public class ExtendedSymbolicExpressionTreeCanvas : ChartControl {
11    private const int HSize = 20;
12    private const int VSize = 15;
13    private const int HDistance = 5;
14    private const int VDistance = 5;
15    private const int MinGroupHorizontalSpacing = 200;
16    private const int MinGroupVerticalSpacing = 200;
17    private const int HorizontalGroupDistance = 20;
18    private const int VerticalGroupDistance = 20;
19
20    public ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode> TreeLayoutEngine { get; set; }
21    public ReingoldTilfordLayoutEngine<ISymbolicExpressionTree> GroupsLayoutEngine { get; set; }
22
23    private SymbolicExpressionTreeLayoutAdapter layoutAdapter;
24
25    private Dictionary<ISymbolicExpressionTreeNode, IPrimitive> nodesToPrimitives;
26    private Dictionary<ISymbolicExpressionTree, IPrimitive> treesToGroups;
27
28    private Dictionary<Tuple<IPrimitive, IPrimitive>, Line> primitiveConnections;
29    private Dictionary<Tuple<IPrimitive, IPrimitive>, Line> groupsConnections;
30
31    private ISymbolicExpressionTreeNode currentSelected;
32    private ISymbolicExpressionTreeNode SelectedSubtree {
33      get { return currentSelected; }
34      set {
35        if (Chart == null)
36          Chart = new Chart(0, 0, PreferredSize.Width, PreferredSize.Height);
37
38        if (value == currentSelected) return;
39        var previousSelected = currentSelected;
40        currentSelected = value;
41
42        DisableUpdate();
43        if (previousSelected != null) HighlightSubtree(previousSelected, Color.Black); // un-highlight the previously selected subtree
44        if (currentSelected != null) HighlightSubtree(currentSelected, Color.DeepSkyBlue); // highlight the new selected subtree
45        EnableUpdate();
46        EnforceUpdate();
47      }
48    }
49
50    public ISymbolicExpressionTreeGenealogyGraph GenealogyGraph { get; set; }
51
52    private void ClearDictionaries() {
53      if (nodesToPrimitives == null) nodesToPrimitives = new Dictionary<ISymbolicExpressionTreeNode, IPrimitive>();
54      nodesToPrimitives.Clear();
55
56      if (treesToGroups == null) treesToGroups = new Dictionary<ISymbolicExpressionTree, IPrimitive>();
57      treesToGroups.Clear();
58
59      if (groupsConnections == null) groupsConnections = new Dictionary<Tuple<IPrimitive, IPrimitive>, Line>();
60      groupsConnections.Clear();
61
62      if (primitiveConnections == null) primitiveConnections = new Dictionary<Tuple<IPrimitive, IPrimitive>, Line>();
63      primitiveConnections.Clear();
64    }
65
66    private ISymbolicExpressionTree root;
67    public ISymbolicExpressionTree Root {
68      get {
69        return root;
70      }
71      set {
72        if (value == null)
73          throw new ArgumentNullException();
74
75        if (root == value) return;
76
77        ClearDictionaries();
78        TreeLayoutEngine.Reset();
79        GroupsLayoutEngine.Reset();
80
81        root = value;
82        currentSelected = null;
83
84        if (Chart == null)
85          Chart = new Chart(0, 0, PreferredSize.Width, PreferredSize.Height);
86
87        DisableUpdate();
88        Chart.Group.Clear();
89        var group = LayoutTree(root);
90        group.Ancestor = group;
91        group.Content = root;
92        Chart.Group.Add(group);
93        GroupsLayoutEngine.Root = group;
94        GroupsLayoutEngine.AddNode(group.Content, group);
95        treesToGroups.Add(group.Content, group);
96
97        // highlight the received fragment
98        var graphNode = GenealogyGraph.GetGraphNodes(root).First();
99        if (graphNode.InEdges != null) {
100          var arc = graphNode.InEdges.Last(x => x.Source != x.Target);
101          var fragment = (IFragment)arc.Data;
102          if (fragment != null && fragment.Root != null) {
103            HighlightSubtree(fragment.Root, Color.Orange);
104          }
105        }
106
107        EnableUpdate();
108        EnforceUpdate();
109      }
110    }
111
112    public ExtendedSymbolicExpressionTreeCanvas() {
113      TreeLayoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode> { MinHorizontalSpacing = HDistance + HSize, MinVerticalSpacing = VDistance + VSize };
114      layoutAdapter = new SymbolicExpressionTreeLayoutAdapter();
115      GroupsLayoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTree> { MinHorizontalSpacing = MinGroupHorizontalSpacing, MinVerticalSpacing = MinGroupVerticalSpacing };
116      if (Chart == null)
117        Chart = new Chart(0, 0, PreferredSize.Width, PreferredSize.Height);
118      nodesToPrimitives = new Dictionary<ISymbolicExpressionTreeNode, IPrimitive>();
119      treesToGroups = new Dictionary<ISymbolicExpressionTree, IPrimitive>();
120      groupsConnections = new Dictionary<Tuple<IPrimitive, IPrimitive>, Line>();
121      primitiveConnections = new Dictionary<Tuple<IPrimitive, IPrimitive>, Line>();
122    }
123
124    /// <summary>
125    /// Draws a symbolic expression tree using HeuristicLab.Visualization primitives and the ReingoldTilford layout algorithm.
126    /// </summary>
127    /// <param name="tree">The symbolic expression tree</param>
128    /// <returns>An IChart containing a group of primitives representing the tree.</returns>
129    private PrimitiveGroup LayoutTree(ISymbolicExpressionTree tree) {
130      var group = LayoutTree(tree.Root.GetSubtree(0).GetSubtree(0));
131      group.Content = tree;
132      return group;
133    }
134
135    // this function is used by the SymbolicExpressionTreeLayoutAdapter
136    private ILayoutNode<ISymbolicExpressionTreeNode> ConvertFunction(ISymbolicExpressionTreeNode node) {
137      ILayoutNode<ISymbolicExpressionTreeNode> layoutNode;
138      if (node.SubtreeCount == 0) {
139        layoutNode = new LabeledRectangle(Chart, 0, 0, HSize, VSize) { Text = node.ToString(), Font = new Font(FontFamily.GenericSansSerif, 12) };
140      } else {
141        layoutNode = new LabeledEllipse(Chart, 0, 0, HSize, VSize) { Text = node.ToString(), Font = new Font(FontFamily.GenericSansSerif, 12) };
142      }
143      // layoutNode.Children are not initialized here, but when the adapter expands the tree
144      layoutNode.Ancestor = layoutNode;
145      layoutNode.Content = node;
146      return layoutNode;
147    }
148
149    private PrimitiveGroup LayoutTree(ISymbolicExpressionTreeNode treeRoot) {
150      if (treeRoot == null) throw new ArgumentNullException();
151
152      var layoutNodes = layoutAdapter.Convert(treeRoot, ConvertFunction).ToList(); // returns a list of layoutNodes in breadth order (relative to the tree traversal)
153      TreeLayoutEngine.Reset();
154      var group = new PrimitiveGroup(Chart);
155      // add primitives (rectangles and ellipses corresponding to terminal/function nodes)
156      foreach (var layoutNode in layoutNodes) {
157        var brush = new SolidBrush(Color.Transparent);
158        var pen = new Pen(Color.Black);
159        var fontBrush = new SolidBrush(pen.Color);
160        var treeNode = layoutNode.Content;
161        layoutNode.Number = layoutNode.Parent == null ? 0 : layoutNode.Parent.Content.IndexOfSubtree(layoutNode.Content);
162        var primitive = (IPrimitive)layoutNode;
163        primitive.Brush = brush;
164        primitive.Pen = pen;
165        if (treeNode.SubtreeCount == 0) {
166          var rectangle = (LabeledRectangle)primitive;
167          rectangle.FontBrush = fontBrush;
168        } else {
169          var ellipse = (LabeledEllipse)primitive;
170          ellipse.FontBrush = fontBrush;
171        }
172        TreeLayoutEngine.AddNode(treeNode, layoutNode);
173        group.Add(primitive);
174        nodesToPrimitives.Add(treeNode, primitive);
175      }
176      TreeLayoutEngine.Root = (ILayoutNode<ISymbolicExpressionTreeNode>)nodesToPrimitives[treeRoot];
177      TreeLayoutEngine.CalculateLayout(); // calculate X,Y coordinates for each layout node
178
179      foreach (var layoutNode in layoutNodes) {
180        var primitive = (RectangularPrimitiveBase)layoutNode;
181        var lowerLeft = new PointD(layoutNode.X, layoutNode.Y);
182        primitive.SetPosition(lowerLeft, lowerLeft + new Offset(primitive.Size));
183      }
184      // connect nodes with lines
185      foreach (var layoutNode in layoutNodes) {
186        var primitive = (RectangularPrimitiveBase)layoutNode;
187        var pen = new Pen(Color.Black);
188        var node = layoutNode.Content;
189        if (node.SubtreeCount == 0) continue;
190        foreach (var subtree in node.Subtrees) {
191          var subtreePrimitive = (RectangularPrimitiveBase)nodesToPrimitives[subtree];
192          var start = new PointD(primitive.UpperRight.X - primitive.Size.Width / 2f, primitive.UpperRight.Y);
193          var end = new PointD(subtreePrimitive.LowerLeft.X + subtreePrimitive.Size.Width / 2f, subtreePrimitive.LowerLeft.Y);
194          var line = new Line(Chart, start, end, pen);
195          group.Add(line);
196          primitiveConnections.Add(new Tuple<IPrimitive, IPrimitive>(primitive, subtreePrimitive), line);
197        }
198      }
199      // once the coordonates for each primitive are updated according to the calculated layout, we update the bounds of the group (LowerLeft and UpperRight)
200      group.UpdateBounds();
201      return group;
202    }
203    /// <summary>
204    /// Handler for the user click event inside the ExtendedSymbolicExpressionTreeCanvas. When the user clicks, the following things should happen:
205    /// 1) The group of primitives containing the clicked screen point is identified
206    /// 2) The corresponding symbolic expression tree is retrieved from the groupsToTreesDictionary
207    /// 3) The corresponding genealogy graph node is retrieved from the GenealogyGraph
208    /// 4) The parents and the fragment are retrieved from the graph
209    /// 5) Both parents are laid out using the symbolic expression tree layout engine and the resulting groups of primitives are added to the canvas
210    /// 6) The fragment is highlighted in the root parent and in the other parent
211    /// </summary>
212    /// <param name="sender"></param>
213    /// <param name="e"></param>
214    protected override void pictureBox_MouseUp(object sender, System.Windows.Forms.MouseEventArgs e) {
215      // STEP 1: Get the primitives and the group
216      var primitives = Chart.GetAllPrimitives(e.Location).Where(p => p is PrimitiveGroup).ToList();
217      if (primitives.Count == 0) return;
218      if (primitives.Count > 1) throw new Exception("Groups/trees should not overlap."); // in the extended canvas, the PrimitiveGroups (each representing a symbolic expression tree) should not overlap
219      var selectedGroup = (PrimitiveGroup)primitives[0];
220      var selectedPrimitive = selectedGroup.GetAllPrimitives(Chart.TransformPixelToWorld(e.Location)).First(p => p is ILayoutNode<ISymbolicExpressionTreeNode>); // similarly with the above condition, there should only be one primitive in that location
221      // STEP 2: Get the selected tree and the selected subtree
222      SelectedSubtree = ((ILayoutNode<ISymbolicExpressionTreeNode>)selectedPrimitive).Content;
223      var selectedTree = ((ILayoutNode<ISymbolicExpressionTree>)selectedGroup).Content;
224      // STEP 3: Get the genealogy graph node, the parents and the fragment
225      var graphNode = GenealogyGraph.GetGraphNodes(selectedTree).First(); // get the GenealogyGraphNode corresponding to the tree
226      var parentVertices = graphNode.InEdges.Select(edge => (SymbolicExpressionTreeGenealogyGraphNode)edge.Source).ToList();
227
228      DisableUpdate();
229
230      foreach (var edge in graphNode.InEdges) {
231        var parentVertex = (SymbolicExpressionTreeGenealogyGraphNode)edge.Source;
232        var parent = parentVertex.SymbolicExpressionTree;
233        if (treesToGroups.ContainsKey(parent)) continue;
234        var childGroup = LayoutTree(parent); // from the layout perspective, roles are reversed and genealogical parents become layout children
235        treesToGroups.Add(parent, childGroup);
236        Chart.Group.Add(childGroup);
237        if (selectedGroup.Children == null) selectedGroup.Children = new List<ILayoutNode<ISymbolicExpressionTree>>();
238        selectedGroup.Children.Add(childGroup);
239        childGroup.Parent = selectedGroup;
240        childGroup.Level = childGroup.Parent.Level + 1;
241        childGroup.Number = childGroup.Parent.Children.Count - 1;
242        childGroup.Ancestor = childGroup;
243        childGroup.Content = parent;
244        GroupsLayoutEngine.AddNode(childGroup.Content, childGroup);
245      }
246      var parents = parentVertices.Select(x => x.SymbolicExpressionTree).ToList();
247      // highlight the fragment
248      if (graphNode.InEdges.Count == 2) {
249        // highlight the fragment
250        var fragment = (IFragment)graphNode.InEdges.Last().Data;
251        if (!(fragment == null || fragment.Root == null)) {
252
253          var subtree0 = parents[0].IterateNodesPrefix().ElementAt(fragment.Index);
254          HighlightSubtree(subtree0, Color.Red);
255
256          var subtree1 = parents[1].IterateNodesPrefix().ElementAt(fragment.OldIndex);
257          HighlightSubtree(subtree1, Color.LimeGreen);
258        }
259      }
260      // layout the groups
261      var groups = Chart.Group.Primitives.Where(p => p is PrimitiveGroup).Cast<PrimitiveGroup>().ToList();
262      var maxSize = new SizeF(groups.Max(g => g.Size.Width), groups.Max(g => g.Size.Height));
263      GroupsLayoutEngine.MinHorizontalSpacing = maxSize.Width + HorizontalGroupDistance;
264      GroupsLayoutEngine.MinVerticalSpacing = maxSize.Height + VerticalGroupDistance;
265
266      GroupsLayoutEngine.CalculateLayout();
267      foreach (var group in Chart.Group.Primitives.Where(p => p is PrimitiveGroup).Cast<PrimitiveGroup>()) {
268        group.Move(new PointD(group.X, group.Y) - group.LowerLeft);
269      }
270      // draw or update (start,end) coordinates of group connections
271      foreach (var group in Chart.Group.Primitives.Where(p => p is PrimitiveGroup).Cast<PrimitiveGroup>()) {
272        if (group.Children == null) continue;
273        var start = new PointD(group.UpperRight.X - group.Size.Width / 2, group.UpperRight.Y);
274        foreach (var childGroup in group.Children.Cast<PrimitiveGroup>()) {
275          var tuple = new Tuple<IPrimitive, IPrimitive>(group, childGroup);
276          var childRoot = (RectangularPrimitiveBase)nodesToPrimitives[childGroup.Content.Root.GetSubtree(0).GetSubtree(0)];
277          var end = new PointD(childRoot.LowerLeft.X + childRoot.Size.Width / 2, childRoot.LowerLeft.Y);
278          if (groupsConnections.ContainsKey(tuple)) {
279            var line = groupsConnections[tuple];
280            line.SetPosition(start, end);
281          } else {
282            var line = new Line(Chart, start, end) { Pen = new Pen(Color.Black) };
283            Chart.Group.Add(line);
284            groupsConnections.Add(tuple, line);
285          }
286        }
287      }
288
289      EnableUpdate();
290      EnforceUpdate();
291
292      base.pictureBox_MouseUp(sender, e);
293    }
294    // highlight a given subtree with the specified color
295    public void HighlightSubtree(ISymbolicExpressionTreeNode subtree, Color color) {
296      foreach (var node in subtree.IterateNodesBreadth()) {
297        var primitive = nodesToPrimitives[node];
298        primitive.Pen.Brush = new SolidBrush(color);
299      }
300    }
301    // the (0,0) point of the HeuristicLab.Visualization.Chart is at the bottom left corner of the screen, while the (0,0) point of the layout engine
302    // and of the actual user control is at the top left corner. so we have to vertically flip everything to maintain correct orientation.
303    private void FlipVertical() {
304      foreach (var primitive in Chart.Group.Primitives) {
305        var group = primitive as PrimitiveGroup;
306        if (group != null) {
307          foreach (var groupPrimitive in group.Primitives) {
308            var rp = groupPrimitive as RectangularPrimitiveBase;
309            if (rp != null) {
310              rp.SetPosition(rp.LowerLeft.X, Height - rp.UpperRight.Y, rp.UpperRight.X, Height - rp.LowerLeft.Y);
311            } else {
312              var lp = groupPrimitive as LinearPrimitiveBase;
313              if (lp != null) {
314                lp.SetPosition(lp.Start.X, Height - lp.Start.Y, lp.End.X, Height - lp.End.Y);
315              }
316            }
317          }
318        } else {
319          var lp = primitive as LinearPrimitiveBase;
320          if (lp != null) {
321            lp.SetPosition(lp.Start.X, Height - lp.Start.Y, lp.End.X, Height - lp.End.Y);
322          }
323        }
324      }
325    }
326    // some convenience methods for the lazy (enabling, disabling updates for the Chart)
327    private void EnableUpdate() {
328      Chart.UpdateEnabled = true;
329    }
330    private void DisableUpdate() {
331      Chart.UpdateEnabled = false;
332    }
333    private void EnforceUpdate() {
334      DisableUpdate();
335      FlipVertical();
336      EnableUpdate();
337      Chart.EnforceUpdate();
338    }
339  }
340}
Note: See TracBrowser for help on using the repository browser.