← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/AddIns/Debugger/Debugger.AddIn/Visualizers/Graph/Layout/Tree/TreeLayout.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/AddIns/Debugger/Debugger.AddIn/Visualizers/Graph/Layout/Tree/TreeLayout.cs
 
1
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
 
2
// This code is distributed under the BSD license (for details please see \src\AddIns\Debugger\Debugger.AddIn\license.txt)
 
3
 
 
4
using System;
 
5
using System.Collections.Generic;
 
6
using System.Windows;
 
7
using Debugger.AddIn.Visualizers.Graph.Drawing;
 
8
using System.Linq;
 
9
 
 
10
namespace Debugger.AddIn.Visualizers.Graph.Layout
 
11
{
 
12
        /// <summary>
 
13
        /// Calculates layout of <see cref="ObjectGraph" />, producing <see cref="PositionedGraph" />.
 
14
        /// </summary>
 
15
        public class TreeLayout
 
16
        {
 
17
                static readonly double NodeMarginH = 30;
 
18
                static readonly double NodeMarginV = 30;
 
19
                static readonly double MarginTop = 0;
 
20
                static readonly double MarginBottom = 0;
 
21
                
 
22
                
 
23
                GraphEdgeRouter edgeRouter = new GraphEdgeRouter();
 
24
                /// <summary>
 
25
                /// The produced layout is either a horizontal or vertical tree.
 
26
                /// </summary>
 
27
                public LayoutDirection LayoutDirection { get; private set; }
 
28
                
 
29
                public TreeLayout(LayoutDirection layoutDirection)
 
30
                {
 
31
                        this.LayoutDirection = layoutDirection;
 
32
                }
 
33
                
 
34
                /// <summary>
 
35
                /// Calculates layout for given <see cref="ObjectGraph" />.
 
36
                /// </summary>
 
37
                /// <param name="objectGraph"></param>
 
38
                /// <returns></returns>
 
39
                public PositionedGraph CalculateLayout(ObjectGraph objectGraph, Expanded expanded)
 
40
                {
 
41
                        var positionedGraph = BuildPositionedGraph(objectGraph, expanded);
 
42
                        CalculateLayout(positionedGraph);
 
43
                        this.edgeRouter.RouteEdges(positionedGraph);
 
44
                        
 
45
                        return positionedGraph;
 
46
                }
 
47
                
 
48
                // Expanded is passed so that the correct ContentNodes are expanded in the PositionedNode
 
49
                PositionedGraph BuildPositionedGraph(ObjectGraph objectGraph, Expanded expanded)
 
50
                {
 
51
                        var positionedNodeFor = new Dictionary<ObjectGraphNode, PositionedNode>();
 
52
                        var positionedGraph = new PositionedGraph();
 
53
                        
 
54
                        // create empty PositionedNodes
 
55
                        foreach (ObjectGraphNode objectNode in objectGraph.ReachableNodes) {
 
56
                                var posNode = new PositionedNode(objectNode, expanded);
 
57
                                posNode.MeasureVisualControl();
 
58
                                positionedGraph.AddNode(posNode);
 
59
                                positionedNodeFor[objectNode] = posNode;
 
60
                        }
 
61
                        
 
62
                        // create edges
 
63
                        foreach (PositionedNode posNode in positionedGraph.Nodes)
 
64
                        {
 
65
                                foreach (PositionedNodeProperty property in posNode.Properties) {
 
66
                                        if (property.ObjectGraphProperty.TargetNode != null) {
 
67
                                                ObjectGraphNode targetObjectNode = property.ObjectGraphProperty.TargetNode;
 
68
                                                PositionedNode edgeTarget = positionedNodeFor[targetObjectNode];
 
69
                                                property.Edge = new PositionedEdge {
 
70
                                                        Name = property.Name, Source = property, Target = edgeTarget
 
71
                                                };
 
72
                                        }
 
73
                                }
 
74
                        }
 
75
                        positionedGraph.Root = positionedNodeFor[objectGraph.Root];
 
76
                        return positionedGraph;
 
77
                }
 
78
 
 
79
                void CalculateLayout(PositionedGraph positionedGraph)
 
80
                {
 
81
                        // impose a tree structure on the graph
 
82
                        HashSet<PositionedEdge> treeEdges = DetermineTreeEdges(positionedGraph.Root);
 
83
                        // first layout pass
 
84
                        CalculateSubtreeSizesRecursive(positionedGraph.Root, treeEdges);
 
85
                        // second layout pass
 
86
                        CalculateNodePosRecursive(positionedGraph.Root, treeEdges, MarginTop, MarginBottom);
 
87
                }
 
88
                
 
89
                
 
90
                HashSet<PositionedEdge> DetermineTreeEdges(PositionedNode root)
 
91
                {
 
92
                        var treeEdges = new HashSet<PositionedEdge>();
 
93
                        
 
94
                        var seenNodes = new HashSet<PositionedNode>();
 
95
                        var q = new Queue<PositionedNode>();
 
96
                        q.Enqueue(root);
 
97
                        seenNodes.Add(root);
 
98
                        
 
99
                        while (q.Count > 0) {
 
100
                                var node = q.Dequeue();
 
101
                                foreach (var property in node.Properties) {
 
102
                                        var edge = property.Edge;
 
103
                                        if (edge != null && edge.Target != null) {
 
104
                                                if (!seenNodes.Contains(edge.Target)) {
 
105
                                                        treeEdges.Add(edge);
 
106
                                                        seenNodes.Add(edge.Target);
 
107
                                                        q.Enqueue(edge.Target);
 
108
                                                }
 
109
                                        }
 
110
                                }
 
111
                        }
 
112
                        return treeEdges;
 
113
                }
 
114
                
 
115
                void CalculateSubtreeSizesRecursive(PositionedNode root, HashSet<PositionedEdge> treeEdges)
 
116
                {
 
117
                        double subtreeSize = 0;
 
118
                        foreach (var child in TreeChildNodes(root, treeEdges)) {
 
119
                                CalculateSubtreeSizesRecursive(child, treeEdges);
 
120
                                // just sum up the sizes of children
 
121
                                subtreeSize += child.SubtreeSize;
 
122
                        }
 
123
                        root.SubtreeSize = Math.Max(GetLateralSizeWithMargin(root), subtreeSize);
 
124
                }
 
125
 
 
126
 
 
127
                /// <summary>
 
128
                /// Given SubtreeSize for each node, positions the nodes, in a left-to-right or top-to-bottom layout.
 
129
                /// </summary>
 
130
                /// <param name="node"></param>
 
131
                /// <param name="lateralStart"></param>
 
132
                /// <param name="mainStart"></param>
 
133
                void CalculateNodePosRecursive(PositionedNode node, HashSet<PositionedEdge> treeEdges, double lateralBase, double mainBase)
 
134
                {
 
135
                        double childsSubtreeSize = TreeChildNodes(node, treeEdges).Sum(child => child.SubtreeSize);
 
136
                        double center = TreeEdges(node, treeEdges).Count() == 0 ? 0 : 0.5 * (childsSubtreeSize - (GetLateralSizeWithMargin(node)));
 
137
                        if (center < 0) {
 
138
                                // if root is larger than subtree, it would be shifted below lateralStart
 
139
                                // -> make whole layout start at lateralStart
 
140
                                lateralBase -= center;
 
141
                        }
 
142
                        
 
143
                        SetLateral(node, GetLateral(node) + lateralBase + center);
 
144
                        SetMain(node, mainBase);
 
145
                        
 
146
                        double childLateral = lateralBase;
 
147
                        double childsMainFixed = GetMain(node) + GetMainSizeWithMargin(node);
 
148
                        foreach (var child in TreeChildNodes(node, treeEdges)) {
 
149
                                CalculateNodePosRecursive(child, treeEdges, childLateral, childsMainFixed);
 
150
                                childLateral += child.SubtreeSize;
 
151
                        }
 
152
                }
 
153
 
 
154
                IEnumerable<PositionedEdge> TreeEdges(PositionedNode node, HashSet<PositionedEdge> treeEdges)
 
155
                {
 
156
                        return node.Edges.Where(e => treeEdges.Contains(e));
 
157
                }
 
158
 
 
159
                IEnumerable<PositionedNode> TreeChildNodes(PositionedNode node, HashSet<PositionedEdge> treeEdges)
 
160
                {
 
161
                        return TreeEdges(node, treeEdges).Select(e => e.Target);
 
162
                }
 
163
 
 
164
                #region Horizontal / vertical layout helpers
 
165
 
 
166
                double GetMainSizeWithMargin(PositionedNode node)
 
167
                {
 
168
                        return (this.LayoutDirection == LayoutDirection.LeftRight) ? node.Width + NodeMarginH : node.Height + NodeMarginV;
 
169
                }
 
170
 
 
171
                double GetLateralSizeWithMargin(PositionedNode node)
 
172
                {
 
173
                        return (this.LayoutDirection == LayoutDirection.LeftRight) ? node.Height + NodeMarginV : node.Width + NodeMarginH;
 
174
                }
 
175
 
 
176
                double GetMain(PositionedNode node)
 
177
                {
 
178
                        return (this.LayoutDirection == LayoutDirection.LeftRight) ? node.Left : node.Top;
 
179
                }
 
180
 
 
181
                double GetLateral(PositionedNode node)
 
182
                {
 
183
                        return (this.LayoutDirection == LayoutDirection.LeftRight) ? node.Top : node.Left;
 
184
                }
 
185
 
 
186
                void SetMain(PositionedNode node, double value)
 
187
                {
 
188
                        if (this.LayoutDirection == LayoutDirection.LeftRight) {
 
189
                                node.Left = value;
 
190
                        } else {
 
191
                                node.Top = value;
 
192
                        }
 
193
                }
 
194
 
 
195
                void SetLateral(PositionedNode node, double value)
 
196
                {
 
197
                        if (this.LayoutDirection == LayoutDirection.LeftRight) {
 
198
                                node.Top = value;
 
199
                        } else {
 
200
                                node.Left = value;
 
201
                        }
 
202
                }
 
203
 
 
204
                #endregion
 
205
        }
 
206
}