Tree visualization

Information about Tree visualization

Published on December 1, 2007

Author: Nevada

Source: authorstream.com

Content

Tree Drawing Algorithms and Visualization Methods:  Tree Drawing Algorithms and Visualization Methods Kai (Kevin) Xu Slide2:  Course website: http://www.cs.usyd.edu.au/~visual/comp4048/ Assignments: Paper presentation Visualization project Outline:  Outline Tree drawing algorithms Tree visualisation Tree Drawing Algorithm:  Tree Drawing Algorithm Terminology Layered Drawing Radial Drawing HV-Drawing Recursive Winding Terminology:  Terminology Tree: Acyclic graph Rooted tree Root: a distinguished vertex in tree Usually treated as a directed graph: all edges oriented away from the root Direct edge u->v: u is the parent of v and v is the child of u Leaf: no child Ordered tree: rooted tree with an ordering for the children of every vertex Terminology:  Terminology Binary tree: rooted tree with every node has at most two children Left and right child One child, either left or right Subtree rooted at v: the subgraph induced by all vertices that have v as their “ancestor” Binary tree: left and right subtree Depth of a vertex: number of edges between it and the root Height of a tree: maximum depth Tree Drawing Algorithm:  Tree Drawing Algorithm Terminology Layered Drawing Radial Drawing HV-Drawing Recursive Winding A Rather Simple Layering Algorithm:  A Rather Simple Layering Algorithm Placing vertex with depth i into layer Li Root in the top layer L0. y-coordinate decided. Ordering vertices in each layer Keep the left-right order of two vertices the same as their parents to avoid crossings. Compute the x-coordinate. Requirement 1: placing the parent in the horizontal span of its children (possibly in a central position). Requirement 2: sometimes the ordering of the children is fixed. Horizontal coordinate assignment:  Horizontal coordinate assignment Solution 1: using in-order traversal Set the x-coordinate as vertex rank in in-order traversal Problems: Much wider than necessary Parent is not centered with respect to children An Improved Layered Tree Drawing Algorithm:  An Improved Layered Tree Drawing Algorithm Divide and conquer Divide step: recursively apply the algorithm to draw the left and right subtrees of T. Conquer step: move the drawings of subtrees until their horizontal distance equals 2. place the root r vertically one level above and horizontally half way between its children. If there is only one child, place the root at horizontal distance 1 from the child. Layered Drawing: Binary Tree:  Layered Drawing: Binary Tree Two traversals step 1. post-order traversal For each vertex v, recursively computes the horizontal displacement of the left & right children of v with respect to v. step 2. pre-order traversal Computes x-coordinates of the vertices by accumulating the displacements on the path from each vertex to the root. Post-Order Traversal:  Post-Order Traversal left (right) contour: the sequence of vertices vi such that vi is the leftmost (rightmost) vertex of T with depth i After we process v, we maintain the left and right contour of the subtree rooted at v as a linked list. In the conquer step, we need to follow the right contour of the left subtree and the left contour of the right subtree Left and Right Contour of Subtree:  Left and Right Contour of Subtree Compute the left and right contour of vertex v: scan the right contour of the left subtree (T’) and the left contour of the right subtree (T’’ ) accumulate the displacements of the vertices on the left & right contour keep the max cumulative displacement at any depth Three cases: case 1: height(T’) = height(T’’) case 2: height(T’) < height(T’’) case 3: height(T’) > height(T’’) Left and Right Contour of Subtree:  Left and Right Contour of Subtree L(T) (R(T)): left (right) contour of the subtree T rooted at v case 1: height(T’) = height(T’’) L(T) = L(T’) + v R(T) = R(T’’) + v case 2: height(T’) < height(T’’) R(T) = R(T’’) + v L(T) = v+ L(T’) + {part of L(T’’) starting from w} h’: depth of T’ w: the vertex on L(T’’) whose depth = h’+1 case 3: height(T’) > height(T’’) : similar to case2 Layered Drawing:  Layered Drawing Two traversals step 1. post-order traversal step 2. pre-order traversal Computes x-coordinates of the vertices by accumulating the displacements on the path from each vertex to the root. Time Complexity:  Time Complexity Pre-order traversal (step 2): linear Post-order traversal (step 1): Linear, but why? it is necessary to travel down the contours of two subtrees T’ and T’’ only as far as the height of the subtree of lesser height the time spent processing vertex v in the post-order traversal is proportional to the minimum heights of T’ and T” The sum is no more than the number of vertices of the tree Can be visualized by connecting vertices with same depth Hence, the algorithm runs in linear time Drawing Width and Area:  Drawing Width and Area Local horizontal compaction at each conquer step does not always compute a drawing of minimal width can be solved in polynomial time using linear programming Area: O(n2) Generalization:  Generalization generalization to rooted trees reasonable drawing root is placed at the average x-coordinates of its children small imbalance problem: The picture show the result when the algorithm works from left to right. Tree Drawing Algorithm:  Tree Drawing Algorithm Terminology Layered Drawing Radial Drawing HV-Drawing Recursive Winding Radial Drawing:  Radial Drawing A variation of layered drawing Root at the origin Layers are concentric circles centered at the origin Usually draw each subtree in an annulus wedge W Wedge Angle:  Wedge Angle Choose wedge angle to be proportional to the leave number in the subtree Problem: edge intersecting with level circle Wedge angle:  Wedge angle To guarantee planarity, define convex subset F of the wedge. The tangent to circle ci through v meet circle ci+1 at a and b The unbounded region F formed by the line segment ab and the rays from origin through a and b is convex The final wedge angle is the lesser between the angle of F and angle proportional to number of leaves. Time and Area:  Time and Area Time: Linear Area Polynomial Equal distance between circles Tree height: h Maximum child number: dM Area: O(h2dM2) First circle has perimeter as least dM (minimum distance between two vertices is 1) It’s radius is O(dM) The radius of final circle is O(hdM) Radial Drawing:  Radial Drawing Used for free trees (tree without a root) Select a root minimize tree height Can be found in linear time using simple recursive leaf pruning algorithm One or two centers Variations: choice of root, radii of the circles, how to determine the wedge angle Tree Drawing Algorithm:  Tree Drawing Algorithm Terminology Layered Drawing Radial Drawing HV-Drawing Recursive Winding HV-Drawing – Binary Tree:  HV-Drawing – Binary Tree HV-drawing of a binary tree T: straight-line grid drawing such that for each vertex u, a child of u is either horizontally aligned with and to the right of u, or vertically aligned with and below u the bounding rectangles of the subtrees of u do not intersect Planar, straight-line, orthogonal, and downward Divide & Conquer Method:  Divide & Conquer Method Divide: recursively construct hv-drawings for the left & right subtrees Conquer: perform either a horizontal combination or a vertical combination The height & width are each at most n-1 Right-Heavy-HV-Tree-Drawing:  Right-Heavy-HV-Tree-Drawing 1. Recursively construct drawing of the left & right subtrees 2. Using only horizontal combination, place the subtree with the largest number of vertices to the right of the other one. height of the drawing is at most logn Right-Heavy-HV-Tree-Drawing:  Right-Heavy-HV-Tree-Drawing HV-drawing (downward, planar, grid, straight-line and orthogonal) Width is at most n-1 Height is at most logn The larger subtree is always placed to the right The size of parent subtree is at least twice the size of vertical child subtree area O(nlogn) Area-Aspect Ratio:  Area-Aspect Ratio Right-Heavy-HV-Tree-Draw Good area bound, but bad aspect ratio Better aspect ratio: use both vertical and horizontal combinations Alternating the combination Odd level: horizontal, even level: vertical O(n) area and constant aspect ratio Optimization and Extension:  It is possible to construct an HV-drawing of a binary tree that is optimal with respect to area or perimeter in O(n2) time. Use dynamic programming approach Right-Heavy-HV-Tree-Drawing can be extended to general rooted tree Downward, planar, grid, straight-line Area O(nlogn) Width is at most n-1 Height is at most logn Optimization and Extension Tree Drawing Algorithm:  Tree Drawing Algorithm Terminology Layered Drawing Radial Drawing HV-Drawing Recursive Winding Recursive Winding:  Recursive Winding Similar to HV-drawing For binary tree Produce planar downward straight-line grid drawing Constant aspect ratio Almost linear area Recursive Winding:  Recursive Winding Input: a binary tree with n vertices and l leaves. n=2l-1 For a vertex v: left(v): left child; right(v): right child T(v): subtree rooted at v l(v): number of leaves in T(v) Recursive winding tree drawing H(l): height of the drawing of T with l leaves W(l): width of the drawing of T with l leaves t(l): running time Recursive Winding Tree Drawing:  Recursive Winding Tree Drawing Arrange the tree so that l(left(v)) ≤ l(right(v)) at every vertex v; Give a parameter A>1,if l≤A, then draw the tree using right-heavy-HV-tree; H(l) ≤log2l, W(l)≤A, and t(l)=O(A); If l>A, define a sequence {vi}: v1 is the root and vi+1=right(vi) for i=1,2,…; Let k≥1 be an index with l(vk)>l-A and l(vk+1)≤ l-A. Such a k can be found in O(k) time, since l(v1), l(v2), … is a strictly decreasing order Recursive Winding Tree Drawing:  Recursive Winding Tree Drawing Let Ti=T(left(vi)) and li=l(left(vi)) for i=1,…,k-1 Let T’=T(left(vk)), T’’=T(right(vk)), l’=l(left(vk)), and l’’=l(right(vk)) Note that l’≤ l’’, since T is right heavy l1 + … + lk-1 = l - l(vk) < A Max{l’,l’’}= l(vk+1)≤ l-A … vk T’ T’’ Recursive Winding Tree Drawing:  Recursive Winding Tree Drawing If k=1, T’ and T’’ are drawn recursively below v1; If k=2, T1 is drawn with right-heavy-HV-tree, while T’ and T’’ are drawn recursively; If k=3, T1,…Tk-2 are drawn from left to right with right-heavy-HV-tree. Tk-1 is drawn right-heavy-HV-tree and then reflected around y-axis and rotated by π/2. T’ and T’’ are drawn recursively below and then reflected around y-axis so that their roots are placed at upper right-hand corners. (This is the “recursive winding”) Recursive Winding Tree Drawing:  Recursive Winding Tree Drawing Bounds: H(l) ≤ max{H(l’) + H(l’’) + log2A + 3, lk-1-1} W(l) ≤ max{W(l’) + 1, W(l’’), l1+…+lk-2} + log2lk-1 + 1 t(l) ≤ t(l’) + t(l’’) + O(l1+ … + lk-1 + 1) Because L1 + … + lk-1 = l-l(vk) < A, H(l) ≤ max{H(l’) + H(l’’) + O(logA), A} W(l) ≤ max{W(l’), W(l’’), A} + O(log2A) t(l) ≤ t(l’) + t(l’’) + O(A) Because Max{l’,l’’}= l(vk+1)≤ l-A, W(l) = O(l/A·logA + A) Recursive Winding Tree Drawing:  Recursive Winding Tree Drawing The running time is O(n); By setting A as A = √(l·log2l), the height and width of the drawing are both O(√nlogn). An example Tree Visualization:  Tree Visualization While tree drawing algorithm is more theoretical, tree visualization is more applied. We will see examples of different tree visualization methods. Indented Layout:  Indented Layout Places all items along vertically spaced rows Uses indentation to show parent child relationships Example: Windows explorer Problems: Only showing part of the tree Bad aspect ratio (not space efficient) But still the most popular one!? Dendrogram:  Dendrogram Essentially a layered drawing with bended orthogonal edges Layering are done according to the leaves: All the leaves are on the same layer Now commonly used in bioinformatics to represent The result of hierarchical clustering Phylogenetic trees More on this in the “biological networks” lecture Balloon trees:  Balloon trees A variation of radial layout children are drawn in a circle centered at their parents. Effective on showing the tree structure At the cost of node details Hyperbolic Tree:  Hyperbolic Tree Simulate the distortion effect of fisheye lens Enlarge the focus and shrink the rest Focus+context Interaction technique; can be combined with different layout. 3D hyperbolic tree: projecting a graph one a sphere produces a similar distortion effect This example also uses balloon tree drawing. 3D tree visualization - Cone tree:  3D tree visualization - Cone tree Cone trees are a 3D extension of the 2D layered tree drawing method. Parent at the tip of a cone, and its children spaced equally on the bottom circle of the cone Either horizontal or vertical The extension to 3D does not necessarily means more information can be displayed Occlusion problem Couple with interaction is essential More on this in the “graph visualization evaluation” lecture Other 3D tree visualizations:  Other 3D tree visualizations 3D poly-plane tree visualization Put subtrees on planes arrange these planes in 3D to reduce occlusion In this example, layered drawing is used within each plane 3D layered tree Only one cone Layers are the parallel circles on the surface Example: color indicate the layer Space-filling methods - Treemap:  Space-filling methods - Treemap Treemap use containment to show the hierarchy. It partitions the space recursively according to the size of subtrees It is space-efficient compare to node-link diagram It is effective in showing the leaf nodes; on the other size, it is difficult to see the non-leave nodes Variations of treemap:  Variations of treemap Cushion treemap Use shading to help identify the levels in a treemap Voronoi treemap Similar idea but uses voronoi diagram as partition The space does not have to be rectangle. Beamtree:  Beamtree A variation of treemap in 3D. Using overlap instead of nesting to show the hierarchy 3D version: representing each node as a beam A bigger example Space-filling tree layout:  Space-filling tree layout Try to use as much screen space as possible Layout a tree according to the recursive partition of the screen space The area allocated to a subtree is proportional to its size. A bigger example: 55000 nodes Use all the screen space Not very effective on showing the tree structure Other space filling methods - Icicle Trees:  Other space filling methods - Icicle Trees Edges implied by adjacency and spatial relationship. icicle tree in the infovis toolkit (jean-daniel fekete) Information slice and Sunburst Diagrams:  Information slice and Sunburst Diagrams Information slice also a space-filling visualization method. Radial version of icicle trees. Node size is proportional to the angle swept by a node. Sunburst With extra focus+context Details are shown outside or inside the ring Elastic hierarchies:  Elastic hierarchies hybrid of node-link diagrams and treemaps Using node-link diagram inside a treemap produces lots of crossings TreeViewer:  TreeViewer Visualizes trees in a form that closely resembles botanical trees The root is the tree stem Non-leave nodes are branches Leave nodes are “bulbs” at the end of branches Example: Unix home directory. Collapsible Cylindrical Trees:  Collapsible Cylindrical Trees Telescope metaphor: A set of nested cylinders A cylinder is constructed for the children of a node, and it has a smaller radius. This cylinder is nested and hidden within the cylinder contain the parent It can be pulled out to the right of theparent cylinder or collapsed as necessary. only one path of the hierarchy is visible at once represented by a number of ever decreasing cylinders All cylinders of level 1 nodes are shown in a horizontal fashion, like being put on a stick.

Related presentations


Other presentations created by Nevada

COAL
12. 12. 2007
0 views

COAL

Kate lance
28. 11. 2007
0 views

Kate lance

Leishmania
23. 12. 2007
0 views

Leishmania

Career at Michelin Info v2
02. 10. 2007
0 views

Career at Michelin Info v2

mtc allergens
04. 10. 2007
0 views

mtc allergens

Cody Model CRM
08. 11. 2007
0 views

Cody Model CRM

sustainability
26. 11. 2007
0 views

sustainability

crises rebirth
11. 12. 2007
0 views

crises rebirth

20061128 Task 6 PPT Sample
12. 12. 2007
0 views

20061128 Task 6 PPT Sample

ww1
26. 10. 2007
0 views

ww1

ROMAN VALUES
29. 10. 2007
0 views

ROMAN VALUES

lecture 2a
30. 10. 2007
0 views

lecture 2a

module a e
01. 11. 2007
0 views

module a e

Mod11 Pump Types and Selection
06. 11. 2007
0 views

Mod11 Pump Types and Selection

IWM2 1 IR
14. 11. 2007
0 views

IWM2 1 IR

radio microwave
14. 11. 2007
0 views

radio microwave

Alexander the Great
14. 12. 2007
0 views

Alexander the Great

LongfellowsMarsRev1
05. 11. 2007
0 views

LongfellowsMarsRev1

NN sleep lecture
28. 11. 2007
0 views

NN sleep lecture

boylan kolchin
29. 11. 2007
0 views

boylan kolchin

70s
24. 12. 2007
0 views

70s

Lecture7 ConnectingLANs
30. 12. 2007
0 views

Lecture7 ConnectingLANs

FormsofResistance 002
17. 12. 2007
0 views

FormsofResistance 002

Political Leadership
31. 12. 2007
0 views

Political Leadership

salinity
01. 01. 2008
0 views

salinity

IAPORK Capturing Incentives
03. 01. 2008
0 views

IAPORK Capturing Incentives

OpenGL Feb2006
03. 01. 2008
0 views

OpenGL Feb2006

emergence
24. 10. 2007
0 views

emergence

PIColloquium v4
15. 11. 2007
0 views

PIColloquium v4

02 skog
07. 01. 2008
0 views

02 skog

MitesPoster
07. 01. 2008
0 views

MitesPoster

Micro BlackHoles rome
31. 10. 2007
0 views

Micro BlackHoles rome

Notable People in VA History
17. 12. 2007
0 views

Notable People in VA History

bia managing it assets external
20. 02. 2008
0 views

bia managing it assets external

EI John Kenkel March 2007
05. 03. 2008
0 views

EI John Kenkel March 2007

Dali
01. 10. 2007
0 views

Dali

plaquette SNE finale
14. 03. 2008
0 views

plaquette SNE finale

ApsecProgHighlights
27. 03. 2008
0 views

ApsecProgHighlights

Simon12sept
30. 03. 2008
0 views

Simon12sept

OverviewRetailIndust ry
13. 04. 2008
0 views

OverviewRetailIndust ry

2 Japanese Theater
22. 11. 2007
0 views

2 Japanese Theater

climbing robots
04. 01. 2008
0 views

climbing robots

Class4
02. 01. 2008
0 views

Class4

fbmm 30th tour directions 102307
23. 11. 2007
0 views

fbmm 30th tour directions 102307

CASPUR Slab 0603
30. 10. 2007
0 views

CASPUR Slab 0603

7 3 Youngsoo Seo
28. 11. 2007
0 views

7 3 Youngsoo Seo

05 moulin
20. 11. 2007
0 views

05 moulin